본문 바로가기
728x90

기타/algorithm

 (14)
최소 신장 트리 - 크루스칼 알고리즘 크루스칼 알고리즘이란? 가장 적은 비용으로 모든 노드를 연결하는 알고리즘입니다. 최소 비용 신장 트리를 만들 때 사용합니다. 예제 위의 그림은 노드가 5개 간선이 6개인 그래프를 나타낸 것입니다. 이들을 연결하는 가장 효율적인 선의 개수는 노드 개수-1=4개입니다. 4개를 어떤 조합으로 선택하면 가장 효율적인 연결이 되는지 알 수 있는 것이 크루스칼 알고리즘입니다. 알고리즘 1. 간선의 거리를 오름차순으로 정리하고 짧은 순서대로 그래프에 포함시킨다. 2. 사이클이 발생하는지 체크하고 발생한다면 해당 간선을 포함하지 않는다. 위의 그림이 사이클입니다. 1,2,3이 모두 연결되어 있지요. 1,2 그리고 2,3 사이에만 간선이 있어도 같은 그래프가 되는데 굳이 간선 하나를 더 사용할 필요는 없겠죠. 간선 길이..
합집합(union find) 알고리즘 합집합 알고리즘(union-find)은 대표적인 그래프 알고리즘으로 여러 개의 노드가 존재할 때 두 개의 노드를 선택해 이들이 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 예를 통해 살펴보도록 하죠. 이런 노드들 각각의 부모 노드를 배열로 나타내면 다음과 같습니다. 1 : [1](가장 상위의 노드이므로 같은 숫자가 들어갑니다.) 2 : [1] 3 : [2] 4 : [4] 5 : [5] 여기서 3의 가장 상위에 있는 노드는 1인데 2가 들어가 있습니다. 3에 1을 넣어주기 위해 재귀 함수를 사용합니다. 3의 상위 노드 2의 상위 노드가 무엇인지 계속해서 찾아나갑니다. 그리고 자신의 상위 노드로 갖는 1에 도달하면 그 값을 3의 상위 노드 값으로 변경해줍니다. 3 : [1] 1, 2, 3은 부모가 ..
[알고리즘] BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 비교 너비 우선 탐색은 가까운 것 위주로 탐색합니다. 최단경로를 찾아줍니다. 미로 찾기에서 많이 사용됩니다. 너비 우선 탐색을 구현하기 위해서는 fist in first out 자료구조인 큐를 사용해 구현할 수 있습니다. 예시를 통해 함께 살펴보죠. 큐에 노드 1을 넣어줍니다. [1] 1을 방문 처리해줍니다. 큐에서 1을 꺼냅니다. [] 1과 연결된 노드 중 방문하지 않은 2,3을 큐에 넣어줍니다. [2,3] 큐에서 2를 꺼냅니다. [3] 2와 연결된 노드 중 방문하지 않은 4,5를 큐에 넣어줍니다. [3,4,5] 큐에서 3을 꺼냅니다. [4,5] 3과 연결된 노드 중 방문하지 않은 6,7을 큐에 넣어줍니다. [4,5,6,7] 큐에서 4를 꺼냅니다. [5,6,7] 4와 연결된 노드 중 방문하지 않은 노드가 없..
깊이 우선 탐색 알고리즘(DFS) 깊이 우선 탐색은 깊은 것을 우선적으로 탐색하는 알고리즘입니다. last in first out구조의 스택을 사용해 구현할 수 있습니다. 우선 1을 방문 처리해 스택에 넣어줍니다. 스택에서 최상단 노드를 확인하고(여기서는 1이겠죠.) 연결된 노드가 있다면 그 노드를 스택에 넣어줍니다. 만약 방문하지 않은 연결된 노드가 없다면 마지막으로 들어온 것부터 하나하나 꺼내면서 위의 과정을 반복합니다. 이 과정을 연결된 모든 노드를 한 번씩 살펴볼 때까지 반복합니다. 1에 방문합니다. 그러면 스택에 1이 들어갑니다. [1] 이제 1과 인접한 수중 가장 작은 2를 방문하고 스택에 넣어줍니다. [2,1] 2와 인접한 수중 가장 작은 3을 방문하고 스택에 넣어줍니다. [3,2,1] 위와 같은 과정을 반복하면 [6,3,2..
[알고리즘] 선형 큐 문제점 및 한계 큐 자료구조는 들어온 것이 먼저 나가는 first in first out 구조입니다. 헷갈리신다면 양쪽이 뚫려있는 원통을 상상해보세요. 양쪽이 뚫려있는 원통에 공을 하나씩 넣으면 먼저 들어온 공이 먼저 나가겠죠. 이런 기본적인 큐 구조를 선형 큐라고 부릅니다. 들어오는 것을 enquene, 나오는 것을 dequene라고 합니다. 선형 큐에는 문제가 있습니다. 삽입과 삭제를 반복하다 보면 앞에 있는 인덱스가 비어있음에도 꽉 찼다고 인식할 수 있습니다. 그렇게 되면 비어있는 공간을 활용할 수 없습니다. 예를 통해 보도록 하죠. 가장 앞을 가르키는 것을 front, 마지막을 rear라고 부릅니다. 오른쪽에서 들어가 왼쪽으로 나간다고 하면 1,2,3이 순서대로 나갈 수 있습니다. front는 1이고 rear에 ..
큐와 덱, 1021번 회전하는 큐 풀이 회전하는 큐 문제를 시도해보았다는 전제하에 문제풀이를 설명하도록 하겠습니다. 문제의 핵심은 원하는 숫자를 빼내는 최적의 횟수를 구하는 것입니다. 최적의 횟수, 조건을 파악하는 것이 매우 중요합니다. 예시를 기반으로 생각해 보았을 때 10 2 2 9 위와 같은 입력이 주어졌을 때 2는 인덱스 1에 위치합니다. 이때는 왼쪽으로 한 칸씩 이동하는 것이 가장 빠르게 2를 빼내는 경로입니다. 리스트는 1~10에서 3,4,5,6,7,8,9,10,1이 됩니다. 이때의 9의 인덱스는 6입니다. 이 때는 오른쪽으로 3번 이동하는 것이 최적의 경로입니다. 답은 5입니다. 위의 예시를 기반으로 생각했을 때 빼내고자 하는 숫자의 인덱스가 리스트의 중간 인덱스보다 클 때는 오른쪽으로 이동해서 빼고 작을 때는 왼쪽으로 이동해 빼..
손익분기점 1712번 백준 풀이 백준 문제에서 1712번에 해당하는 손익분기점 문제 풀이입니다. 문제를 읽어보셨다고 가정하고 설명하도록 하겠습니다. 출력에는 크게 두 가지가 있습니다. 손익분기점을 넘는 판매량, 손익분기점이 존재하지 않을 때의 -1 그렇다면 두가지를 구분하는 조건을 찾아야겠지요. 생각해봅시다. 고정비용은 판매량이 증가한다고 그 자체로 변화가 생기지 않습니다. 반면 가변비용과 가격은 판매량이 증가하면 둘 다 증가합니다. 만약 가변비용이 가격보다 크다면 판매량 증가는 적자를 확대합니다. 가변비용이 100이고 가격이 10이면 한 개씩 판매량이 증가할 때마다 이익은 -90입니다. 때문에 가변비용이 가격보다 작아야 손익분기점이 존재할 수 있습니다. 같을 때는? 이익이 판매량이 1 증가할 때마다 0이 증가므로 고정비용이 줄어들지 ..
파이썬 에러 종류 구문, 런타임 에러 파이썬으로 알고리즘 풀다 보면 여러 가지 에러에 직면합니다. 특히 백준에서 알고리즘을 풀 때 에러가 나오지 않아 애를 먹습니다. 그래서 파이썬 에러 종류에 대해 공부해 보았습니다. 파이썬에는 크게 두 가지 타입의 에러가 있습니다. 구문 에러와 런타일 에러입니다. 1.SyntaxError(구문 에러)입니다. >>> print'hello') SyntaxError: invalid syntax >>> print('dd) SyntaxError: EOL while scanning string literal 괄호가 제대로 처리되지 않았거나 '를 닫아주지 않았을 때 나는 에러입니다. 이밖에도 python의 문법에 맞지 않게 코딩을 했을 때 나옵니다. SyntaxError로 시작하는 에러가 나온다면 문법 오류, 오타를 ..
728x90

티스토리툴바