without haste but without rest

C 로 그래프를 구현하는 중에 이해를 못하는 상황이 발생했다. 파이썬은 딕셔너리 구조를 이용해서 정말 쉽게 구현했고, 메모리 관리를 따로 안 해줘도 되니까 구조 자체에만 집중할 수 있었다. 온라인 강의를 보면서 굉장히 비효율적인 공부를 하다가, 혼자 그래프를 그려보고 직접 생각하면서 이를 코드로 구현하는 게 역시나 정석인 것 같다고 판단했다. 결론: 노트에 구조를 그려보고, 여기에 맞춰서 코드를 짜는 게 오래 남는다. 코드로 그래프를 구현한다는 것은 사람이 눈으로 인식하는 것과는 차이가 있다. 그래프 구조의 특징은 노드가 가지는 숫자가 노드의 개수보다 크지 않고, 중간에 비는 숫자가 없다. (만약 노드가 갖는 숫자가 1부터 순차적인 숫자가 아니라 중간에 훅 건너 뛰는 경우는 배열의 크기를 늘리는 방법을 ..

너비 우선 탐색(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..