포시코딩

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색(Breadth First Search:BFS) 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search:DFS) 정점의 자식들을 먼저 탐색하는 방식 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J * 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회한다. DFS 방식: A - B - D - E - F - C - G - H - I - J * 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다. 구현 파이썬에서는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 ..

그래프(Graph)란? 노드(Node)와 간선(Edge)로 이루어진 자료구조. 노드(Node): 위치를 뜻한다. 버텍스(Vertex), 정점이라고도 불림 간선(Edge): 위치 간의 관계를 표시한 선. 노드를 연결한 선으로 링크(link) 또는 브랜치(branch)라고도 한다. 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 노드 참고용어 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 경로 길이(Path Length): 경로를 구성하기 위해 사용된 간선의 수 단순 경로(Simple Path): 처음 정점과 끝 ..

자료구조에서 탐색에 대한 알고리즘을 배운 바 있다. 순차 탐색 해시 이진 탐색 트리 여기에 추가로 이진 탐색에 대해 알아보자 이진 탐색 이분 탐색으로도 불리는 이진 탐색은 '업다운 게임'을 떠올리면 이해하기 쉽다. 30개의 정렬된 원소 중 정확히 70이 든 값을 찾으려면 중간을 까서 이하인지 이상인지 확인하는 방식으로 찾아 나아가면 된다. 순차 탐색에 비해 이진 탐색의 찾는 속도가 훨씬 빠른 것을 볼 수 있다. 이진 탐색은 병합 정렬과 더불어 분할 정복 알고리즘(Divide and Conquer)의 대표적인 예이기도 하다. Divide: 리스트를 두 개의 서브 리스트로 나눈다. Conquer: 검색할 숫자 > 중간 값이면 뒷 부분에서, 반대면 앞 부분에서 검색할 숫자를 찾는다. 코드 def binary_..

병합 정렬(Merge Sort) 분할 정복 알고리즘의 기법을 사용하는 정렬 알고리즘 중 하나 (분할 정복 알고리즘의 대표적인 예 중 하나기도 하다.) 데이터를 잘게 쪼개 정렬한다. Memoization을 사용하지 않음 재귀 용법을 활용 사용방법 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. 구현 재귀 용법으로 데이터를 나누는 함수, 나눠진 데이터를 병합하는 함수 두 단계를 함수로 만들어 사용 def merge_sort(data): return split(data) def split(data): if len(data) lp and len(right) > rp: if left..

퀵 정렬(Quick Sort) 정렬 알고리즘의 꽃 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해 다시 동일 함수를 호출하여 위 작업을 반복 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴한다. 배우기 앞서 기대한 알고리즘 중 하나 파이썬에서 구현 시 아름다울 정도라는데 얼마나 감동할 수 있을지 기대를 잔뜩 하고 들어갔던 것 같다. 크게는 아래 순서를 따라간다. pivot은 보통 제일 앞에걸로 지정 pivot을 기준으로 분류 분리된 left, right를 재귀 함수를 통해 1~2 반복 그렇게 데이터 수가 1개가 될 때 까지 반복한다. 구현 def qsort(l..

동적 계획법(Dynamic Programming, DP) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법 사용 Memoization(메모이제이션)이란? 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용됨 ex) 피보나치 수열 분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 ..

재귀를 활용한 문제들 팰린드롬(Palindrome) 앞뒤 구성이 같은 문자열 ex) 기러기, 토마토, 우영우 재귀 함수를 통해 간단히 구현할 수 있다. 코드 def palindrome(str): if len(str)

힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) * 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 우선순위 큐 import queue data_queue = queue.PriorityQueue() data_queue.put((10, "korea")) data_queue.put((5, 1)) data_queue.put((15, "china")) print(d..

트리 노드와 브랜치로 구성된 사이클을 이루지 않도록 구성한 데이터 구조 * 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node): Child Node가 하나도 없는 노드 Sibling (Brother Node): 동일한 Parent Node를 가..

Chaining 데이터 추가 함수 hash_table = list[0 for i in range(8)] def get_hash(data): return hash(data) def get_address(hash): return hash % 8 def save_data(data, value): hash_key = get_hash(data) hash_address = get_address(hash_key) if hash_table[hash_address] != 0: for i in range(len(hash_table[hash_address])): if hash_table[hash_address][i][0] == hash_key: # 같은 hash의 키로 데이터가 있을 경우 hash_table[hash_add..