0-1 BFS 0-1 bfs는 가중치가 0과 1만 있는 최단 경로 문제를 말한다. 시간복잡도는 O(V+E) (V는 노드, E는 간선)으로, 조건을 만족하는 경우 다익스트라 알고리즘보다 더 효율적으로 작동한다. 일반적인 BFS 탐색과 동일하지만, 가중치가 0인 정점이 존재하기 때문에 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 한다. 즉, 결과 값이 방문 횟수의 최소가 아닌 가중치가 최소인 경우를 찾기 때문에 가중치가 낮은 경로부터 탐색해야 한다. 0-1 BFS 동작 1. 덱의 front에서 현재 노드를 꺼낸다. 2. 연결된 인접 노드를 살펴본다. 3. 현재까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다. 4. 노드..
자료구조 및 알고리즘
다익스트라 알고리즘 다익스트라 알고리즘은 가중치가 양수만 존재하는 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘 중의 하나이다. 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복한다. 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다고 한다. 참고로, 그래프 알고리즘 중 최소 비용을 구하는 데는 다익스트라 알고리즘 외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등이 있다. 동작 단계 1. 출발 노드와 도착 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 현재 위치한 도드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드..
Heap 1. 힙은 완전이진트리를 기본으로한 자료구조로, O(logN)의 시간복잡도를 가지고 있다. 2. 여러 개의 값 중 최대값, 최소값을 빠르게 찾아내도록 만들어진 자료구조이다. 우선순위 큐 구현 시에 사용한다. 3. 힙은 반정렬 상태(느슨한 정렬 상태)를 유지한다. 이를테면 최소힙일 때, 작은 값이 상위 레벨에 있고 큰 값이 하위 레벨에 있다는 정도. 4. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류 최대힙 부모노드의 키 값이 자식노드의 키값보다 항상 크거나 같 힙. 최대 힙에서는 루트 노드에 이는 값이 제일 크므로 최대값을 찾는데 소요되는 연산의 시간복잡도는 O(1)이다. 그리고 완전 이진 트리이기 때문에 배열을 사용하여 효율적으로 관리할..
파라메트릭 서치 파라메트릭 서치는 최적화 문제를 결정문제로 바꾸어 해결하는 기법, 즉 주어진 상황에서 최소값, 최대값 등의 값을 구하는 문제를 그 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바꾸어 해결하는 기법이다. 이 기법에 의하면 중간점의 값은 시간이 지날수록 최적화된 값이 되기 때문이다. 이를테면 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제이다. 파라메트릭 서치와 이진 탐색은 비슷하게 생겼는데, 활용에 있어서 차이가 조금 있다. 이진탐색은 정렬된 주어진 값 중에서 원하는 값을 찾는 알고리즘이다. (이진탐색 알고리즘을 사용하는 것에 있어 정렬은 전제조건이다.) 순차탐색을 했을 때 시간이 너무 오래걸릴 것 같으면 (ex. 탐색할 것이 몇 억을 넘어갈 경우) 이진탐색을 선..
이진탐색 이진탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법이다. 시작점 끝점을 이용해 탐색범위를 결정한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 logn에 비례한다. O(logN)을 보장해준다. 이진탐색은 위치를 나타내는 변수 3개를 이용한다. 시작점, 중간점, 끝점 -> 중간점이 실수인 경우, 버림한다. 중간값에 있는 데이터와 찾고자하는 값을 비교한 후, 크냐 작으냐에 따라 중간점 + 1, 중간점 - 1 값을 시작점 또는 끝점으로 변경한 후 다시 중간점을 찾는다. 이후 값을 찾거나 탈출조건에 해당할 때까지 위 과정을 반복한다. 구현 방법 반복문, 재귀함수 기억해야 할 것 이진탐색은 정렬된 리스트에서만 사용가능한 알고리즘이다. 따라서 이진탐색을..
계수정렬 특정 조건이 부합할 때만 사용할 수 있는 정렬이지만, 매우 빠른 정렬 알고리즘이다. 조건 1. 최소값과 최대값의 차이가 100만 이하일 경우 2. 데이터가 양의 정수일 경우 3. (+데이터 크기가 많이 중복되어 있을 경우) 특징 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 사용할 수 없다. 모든 범위르 ㄹ담을 수 있는 크기의 리스트를 선언해야하기 때문이다. 계수정렬은 직접 데이터의 값을 비교한 후에 위치를 정렬하는 방식이 아니다. 별도의 리스트 선언 후, 그 안에 정렬에 대한 정보를 담는다. 데이터 범위가 한정되어 있으면 효과적으로 사용할 수 있다. 항상 빠르게 동작하며, 기수정렬과 더불어 가장 빠른 정렬 알고리즘이다. 코드 # 계수정렬 array_1 = [7,5,9,0,3,1,6,2..
퀵정렬 가장 많이 사용되는 정렬 알고리즘 중 하나. 퀵정렬과 병합정렬 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 된다. 퀵정렬 Idea 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까? 퀵정렬은 기준(Pivot, 피벗)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵정렬을 구분하는데, 여기서는 호어방식을 다룰 것이다. 호어방식 리스트에서 첫 번째 데이터를 피벗으로 정한다. 피벗 설정 후 왼쪽에서는 피벗보다 큰 데이터를, 오른쪽에서는 피벗보다 작은 데이터를 찾고 교환한다. 이 과정을 반복하면 정렬이 수행된다. 특정 리스트에서 피벗을 설정하여 정렬을 수행한 후에 ..
삽입정렬 데이터를 적절한 곳에다가 삽입하는 정렬이다. 삽입정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효율적이다. cf. 선택정렬은 현재 데이터의 상태과 상관없이 무조건 모든 원소를 비교한다. 삽입 정렬에서는 특정한 데이터가 삽입될 위치를 선정할 때, 삽입될 데이터보다 작은 값을 만나면 그 위치에서 멈추면 된다. (특정 데이터의 왼쪽 부분은 이미 정렬이 된 상태이기 때문이다.) 인덱스가 0인 데이터는 이미 정렬되어있다고 가정하고 해당 위치에 고정시킨다. 코드 array = [7,5,9,0,3,1,6,2,4,8] for i in range(1, len(array)): for j in range(i, 0, -1): if array[j] < array[j-1]: array[j], arr..
선택정렬 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬. 즉, 가장 작은 것을 선택해 앞으로 보내는 과정을 반복 수행하는 정렬방법이다. 이중 for문을 이용해 구현할 수 있다. 코드 # 선택정렬 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array) # [0,1,2,3,4,5,..
BFS (너비우선탐색) 시작노드에서 시작한 뒤 다음 깊이로 진행하기 전 출발점에서 발생한 모든 분기를 탐색한 후, 다음 레벨로 진입한다. 갈림길의 모든 지점들을 탐색한 뒤 갈림길에서 발생한 모든 갈림길을 다시 순차적으로 탐색하는 모습이 가로로 훑는 모양새이다. DFS의 경우 무한루프나 스택오버플로의 우려가 있었지만, BFS의 경우 모든 경로에 대해 동시에 탐색을 진행하므로 그럴 걱정은 없다. BFS의 특성 1. BFS는 재귀로 구현할 수 없다. 2. 가중치가 없는 그래프에서 두 노드 사이의 최단경로나 임의의 경로를 구하는 데 사용한다. 3. DFS보다 검색에서 유리하다. (DFS는 조건을 만족하는 순회에 초점) 4. 방문한 노드들을 저장한 후 차례대로 꺼내는 FIFO (선입선출) 방식으로 탐색을 진행하기..
