Theory (53) 썸네일형 리스트형 자료구조 - 힙 (Heap) 힙은 부모가 항상 자식보다 작거나 같다 (최소힙)라는 특성을 만족하는 트리 기반의 자료구조입니다. 이번 포스트에서 다룰 힙은 최소힙이고 최소힙은 부모가 항상 자식보다 작기 때문에 트리의 루트가 가장 작은 값을 갖게 됩니다. 반대로 최대힙은 부모가 항상 자식보다 큰 트리가 되겠죠. 힙이라는 자료구조는 J.W.J. 윌리엄스가 1964년 힙 정렬 알고르짐을 고안하면서 파생된 부산물입니다. 보통 배열로 구현하며 다음 그림과 같이 부모와 자식 간의 상하 관계가 정의되어 있고 같은 레벨의 자식들끼리의 좌우 관계는 정의되어 있지 않습니다. 힙은 주로 배열로 구현되며, 위 그림 오른쪽처럼 배열로 표현할 수 있습니다. 루트 노드의 인덱스는 1부터 시작하고 그 다음 레벨 노드의 인덱스는 2,3, 그 다음 레벨 노드의 인덱.. 자료구조 - 스택 (Stack), 큐 (Queue) 스택 (Stack) 과 큐 (Queue) 는 프로그래밍에서 가장 기본적으로 사용하는 고전적인 자료 구조임과 동시에 특히 스택은 거의 모든 애플리케이션을 만들 때 사용됩니다. 스택은 Last In First Out (선입후출) 의 자료구조로 마지막에 들어온 원소가 가장 먼저 추출됩니다. 잔뜩 쌓인 접시를 생각하면 됩니다. 스택의 개념은 자료를 저장하는 자료구조와 동시에 컴퓨터 프로그램의 서브루틴에 대한 정보로 활용됩니다. 가장 마지막에 저장된 커맨드가 실행되는 식이죠. 큐는 스택과 반대로 First In First Out (선입선출) 의 자료구조로 가장 먼저 들어온 원소가 가장 먼저 추출됩니다. 일반적인 대기열을 생각하면 되겠네요. 파이썬에서는 스택과 큐의 자료구조를 따로 제공하지는 않으나 리스트가 관련 .. 다이나믹 프로그래밍 (Dynamic Programming) 다이나믹 프로그래밍 (Dynamic Programming) 은 리차드 벨만 (Richard Bellman) 이 1953년에 고안한 알고리즘입니다. 우리 말로 "동적 계획법" 이지만 동적이라 함은 보통 프로그래밍에서 프로그램이 실행되는 도중에 필요한 메모리를 그때마다 할당하는 기법을 뜻하고 다이나믹 프로그래밍에서는 딱히 큰 의미는 없습니다. 다이나믹 프로그래밍은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해두었다가 나중의 큰 문제의 결과와 합하여 풀이하는 방식입니다. 그럼 어느 경우에 다이나믹 프로그래밍을 주로 사용할까요? 문제가 최적 부분 구조 (Optimal Substructure) 를 가지고, 동일한 작은 문제를 반복적으로 해결해야 하는 경우 (중복되는 부분 문제) 에 적합합니다. 문제가 최.. 이진 탐색 (binary search) 이진 탐색 (혹은 검색, binary search) 는 이미 정렬된 배열에서 타겟을 찾는 검색 알고리즘으로 시간 복잡도가 O(logn)이 소요되는 대표적인 로그 시간 알고리즘입니다. 술자리에서 0부터 100까지의 임의의 숫자를 생각해 놓고 업다운을 통해 숫자를 맞추는 게임이 있습니다. 이때, 하나씩 높여가는 것이 아니라 50 -> 25,75 -> 12,37,87 등 숫자 범위의 절반을 줄여가면서 탐색 범위를 점점 좁히게 되죠. 합병정렬처럼 매번 절반으로 쪼개니 O(logn)의 시간 복잡도가 소요됩니다. 절반으로 탐색 범위를 좁혀 계산 횟수가 log 만큼 줄게 만드는 것은 시간 복잡도 측면에서 굉장히 강력한 성능을 띠게 됩니다. 100까지의 숫자는 7번, 1억까지의 숫자도 27번의 비교로.. 그래프 (2) - 너비우선탐색 (BFS, Breadth First Search) 이번 포스트에서는 너비우선탐색 (BFS, Breadth First Search) 를 살펴보겠습니다. 스택이나 재귀로 구현하는 깊이우선탐색과 달리 너비우선탐색은 First-In First-Out (FIFO) 의 큐 자료구조를 사용해 구현하며, 다익스트라 알고리즘과 같은 최단 경로를 구하는 데 사용됩니다. 코드를 어떻게 구현하게 될까요? 선입선출의 큐를 이용하니 파이썬의 list나 collections 모듈의 deque를 이용할 수 있을 것 같습니다. 깊이우선탐색에서의 스택과 달리 큐는 배열의 첫 번째 원소가 추출되는 구조이니 해당 정점의 인접점들을 모두 방문하고 다음 레벨의 정점을 방문하게 됩니다. 깊이우선탐색과 같은 그래프 예로 코드를 한 번 살펴보겠습니다. graph = {1: [2,3,4], 2: [.. 그래프 (1) - 깊이우선탐색 (DFS, Depth First Search) 정점 (vertex) 와 엣지 (edge) 로 구성된 그래프에서 그래프의 각 정점을 방문하는 그래프 순회에는 깊이우선탐색 (DFS, Depth First Search) 와 너비우선탐색 (BFS, Breadth First Search) 가 있습니다. 이번 포스트에서 살펴볼 그래프 순회 방법은 깊이우선탐색으로 19세기 프랑스의 수학자 찰스 피에르 트레모 (Charles Pierre Tremaux) 가 미로 찾기 문제를 풀다가 고안한 것으로 알려져 있습니다. 깊이우선탐색은 보통 1. 스택, 2. 재귀 로 구현할 수 있으며 코딩 테스트때 그래프 관련 단골 문제로 출제되는 만큼 굉장히 중요한 문제입니다. 먼저 다음 그림과 같은 그래프를 구성해 보겠습니다. 위 그래프에 대해서 각 정점 별 이웃을 담은 인접 리스트를.. 안정 정렬 vs 불안정 정렬 KTX 역에서 도착역과 출발 시간으로 이루어진 다음과 같은 데이터가 있다고 가정해 봅시다. [(대구, 1400), (순천, 1500), (대구, 1430), (부산, 1300), (목포, 1400), (대구, 1500)] 지역명으로 오름차순으로 정렬한다고 했을 때, 다음과 같이 우리는 '대구->목포->부산->순천' 순으로 정렬하면서 대구의 중복된 데이터 3개는 시간 순서대로 그대로 유지되게 하고 싶겠죠. [(대구, 1400), (대구, 1430), (대구, 1500), (목포, 1400), (부산, 1300), (순천, 1500)] 하지만 정렬 방법마다 이렇게 중복된 원소가 본래 순서대로 정렬될 수도 있고 정렬되지 않고 섞일 수도 있습니다. 이번 포스트에서 살펴볼 내용은 안정정렬과 불안정정렬입니다. 안정.. 병합 정렬 / 합병 정렬 (Merge Sort) "분할하여 정복한다" 흔히 "Divide and Conquer"라 알려져 있는 격언은 실제 정치에서 뿐만 아니라 알고리즘에서도 자주 사용하는 norm 입니다. 전체를 한 번에 다 아우르지 않고 다룰 수 있는 작은 부분으로 쪼개면 일이 훨씬 수월해지는 것은 당연한 이치입니다. 이번 포스트에서 다룰 병합 정렬은 퀵 정렬과 더불어 정렬 알고리즘 중 대표적인 "분할 정복" 알고리즘입니다. 역사상 최고의 천재 중 손꼽히는 존 폰 노이만 (John Von Neumann) 이 무려 1945년에 고안한 알고리즘으로 최선/최악의 경우 일정하게 O(nlogn)의 시간 복잡도를 보장하는 알고리즘입니다. 한 번 예를 들어 살펴볼까요? EXAMPLE 병합정렬은 크게 2 가지 스텝으로 이루어져 있습니다. 1. 분할 (Di.. 이전 1 ··· 3 4 5 6 7 다음 목록 더보기
