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..

재귀 용법(Recursive Call) 이미지를 보면 프로그램 속에서 프로그램을 실행했다. 다시 프로그램 속의 프로그램 속에서 프로그램을 실행했다. 이게 재귀다. 함수 안에서 다시 똑같은 함수를 불러와서 재사용한다. *주의할 점은 항상 종료 조건을 만들어줘야 한다. 무한 루프에 빠진다. # Recursive def recursive(data): if data == 0: return print(data) recursive(data -1) print('Number is ', data) #Test Code recursive(5) 위 코드를 실행하면 아래처럼 출력된다. Number is .. 가 왜 역순으로 출력이 되는지 생각해보면 재귀를 이해하는 데에 도움이 된다.

퀵 정렬(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..

선택 정렬(Selection Sort) 선택 정렬은 배열을 순회 하면서 현재 값보다 작은 값을 찾는 구조다. 위 이미지에서 8에서 시작하여 더 작은 값이 있는지 찾는다. 3이 가장 작으므로 0번 인덱스에 3이 온다. 이때 작은 값들이 오름차순으로 적재되는 것을 생각해야한다. 따라서 2회차부터는 1번 인덱스에서 시작한다. 이제 1번 인덱스인 41에서 순회를 시작한다. 바로 다음 숫자인 21이 더 작으므로 최소값을 담는 임시 변수는 21을 담는다. 다음으로 21과 3을 비교한다. 3이 더 작으므로 임시 변수는 3으로 교체한다. 그 뒤에는 3보다 작은 값이 없으므로 41의 자리인 1번 인덱스는 3으로 교체된다. #Selection Sort def selection_Sort(array): for a in ran..

버블 소트(Bubble Sort) 버블 소트는 배열에서 차례대로 두 데이터들을 비교한다. 이때 앞에 있는 숫자가 뒤에 있는 숫자보다 크다면 자리를 교체한다. 큰 숫자가 차례차례 뒤로 넘어가는 구조다. 한번의 순회가 끝나면 다시 처음부터 값들을 비교한다. 이를 반복하는 것이다. 특징으로는 한번 루틴을 돌 때 마다 가장 큰 값이 뒤로 가므로 비교해야 할 횟수가 줄어든다. 위 이미지에서는 최대 순회 횟수를 채우기 전에 데이터가 모두 정렬됐다. 즉 중간에 더 이상 비교할 필요가 없어졌다. 따라서 소스 코드 내에서 swap이라는 불리언 값을 주었다. 만약 한번의 순회를 거치는 동안 데이터간의 교체가 있는지 없는지를 체크하는 것이다. 교체가 없다면 정렬이 끝났다는 것이므로 반복문을 종료한다. 아래 코드에서 첫번째 ..