without haste but without rest

너비 우선 탐색(BFS) (레이아웃이 PC 에 최적화 되어있습니다.) BFS 알고리즘은 탐색하는 노드가 속한 레벨을 전부 탐색하고 다음 레벨로 넘어간다. 즉 형제 노드를 전부 탐색하고 자식노드로 내려간다. DFS의 경우 큐와 스택 두가지를 활용했는데, BFS는 큐로 구현한다. 위 그래프를 딕셔너리 형태로 표현하면 다음과 같다. graph = dict() graph[0] = [1, 2] graph[1] = [0, 3, 4] graph[2] = [0, 5, 6] graph[3] = [1] graph[4] = [1] graph[5] = [2] graph[6] = [2] res는 최종적으로 반환할 리스트이며 visit은 탐색할 노드들이 담길 리스트다. 가장 먼저 시작 노드인 0이 res 리스트에 추가된다. 다음..

깊이 우선 탐색(DFS) (레이아웃이 PC 에 최적화 되어있습니다.) 깊이 우선 탐색 알고리즘은 말 그대로 깊이를 우선순위로 두고 탐색한다. 위 이미지에서 우측의 DFS 알고리즘은 0 → 1 → 3 → 4 → 2 → 5 → 6 순서로 탐색을 한다. (이때 0에서 1, 2로 가는 순서는 상관 없다. 따라서 0 → 2 → 6 → 5 → 1 → 4 → 3으로도 탐색할 수 있다.) 위 그래프 구조를 파이썬 딕셔너리 형태로 표현하면 아래와 같다. graph = dict() graph[0] = [1, 2] graph[1] = [0, 3, 4] graph[2] = [0, 5, 6] graph[3] = [1] graph[4] = [1] graph[5] = [2] graph[6] = [2] 0에서 1로 움직이고 1에서는..

병합 정렬(Merge Sort) 병합 정렬은 배열을 좌, 우로 나누고, 나눈 배열을 정렬하고 다시 붙인다. 이 과정을 반복한다. 퀵 소트와 마찬가지로 재귀 용법을 활용하는 알고리즘이다. 위키피디아에서 제공하는 이미지가 더 도움이되는 것 같다. 아래 코드 과정을 일일히 손으로 써보면 위와 같은 구조로 진행됨을 확인할 수 있다. (*재귀를 정확히 이해해야 코드를 이해할 수 있다.) [python] 알고리즘 - 재귀 용법(Recursive Call) 재귀 용법(Recursive Call) 이미지를 보면 프로그램 속에서 프로그램을 실행했다. 다시 프로그램 속의 프로그램 속에서 프로그램을 실행했다. 이게 재귀다. 함수 안에서 다시 똑같은 함수를 불러와서 재사용한다... jinyes-tistory.tistory.c..

퀵 정렬(Quick Sort) 퀵소트는 반복문을 하나만 쓰기 때문에 시간복잡도 면에서 더 우수한 성능을 기대를 할 수 있다. 위 (이미지를 보다. 코드를 먼저 보는 게 더 나을 수도 있다. 보기와는 달리 정말 간단하다. 코드를 이해하면 이게 왜 빠를 수밖에 없는지 바로 이해된다.) gif 이미지에서 8을 첫번째 피벗으로 선택한다. 이때 작은 데이터와 큰 데이터를 구분하고 8의 왼쪽과 오른쪽에 붙인다. 다음으로 5를 선택하고 반복한다. (노란색이 피벗이다.) 포인트는 재귀(Recursive)를 사용한다는 것이다. 1. 배열에서 Pivot(기준점, 중심)을 정한다. 2. 피벗 보다 작은 데이터들은 left 리스트로, 큰 값은 right 리스트로 이동한다. 3. 이 과정을 재귀로 반복 시키면서 붙인다. #Qu..

삽입 정렬(Insrtion Sort) 삽입 정렬 역시 이중 루프로 구현할 수 있다. 가장 바깥 루프는 배열의 데이터를 순차적으로 선택하는 역할이며 안쪽 루프는 실질적으로 데이터를 비교하고 자리를 교체하는 역할을 수행한다. 1회 루틴 과정 -> 바깥 포 문은 배열의 인덱스를 오름차순으로 선택해 나간다. 이때 바깥 포문이 다음 데이터로 넘어가기 전에 안쪽 포 문은 현재 선택한 데이터를 배열 속에서 역방향으로 비교한다. 만약 이전 값이 현재 선택한 데이터 보다 큰 경우 두 데이터의 인덱스를 교체한다. 이를 반복한다. 위 이미지를 참고하면 쉽게 이해할 수 있다. #Insertion Sort def Insertion_Sort(array): for a in range(1, len(array)): for b in r..