algorithm

선택 정렬, 추후 삽입 정렬을 다룰 예정인데, 그 전에 우선순위 큐에 대한 이야기를 먼저 할 필요가 있다.우선순위 큐는 알고리즘이 아닌 자료구조이다. 우선순위 큐라는 자료구조를 이용한 정렬(선택 정렬, 삽입 정렬)이 알고리즘이 되겠다.우선순위 큐에 대한 개념은 간단하다

무순리스트 기반 구현인 선택 정렬과 달리 삽입 정렬은 순서리스트에 기반한다. 매를 먼저 맞는,우선순위 큐가 순서리스트로 구성되는 삽입 정렬을 알 아 보 자insert()N회의 insert 작업삽입 시에 최초 O(1) - 마지막 O(N)1 + 2 + ... + (N-1)

힙(heap)이란 힙순서를 가진 완전이진트리의 자료구조다. 힙 구조는 최솟값 혹은 최댓값을 쉽게 추출할 수 있도록 하는 일종의 우선순위 큐다. 하지만, 힙은 느슨한 정렬 상태 정도를 유지한다. 힙의 속성은 부모의 키값이 자식의 키값보다 작거나 같아야 한다.(최소힙

저번 포스트의 힙 자료구조에 이어 힙을 이용한 정렬 알고리즘을 알아보자.위는 힙 정렬 의사 코드다. 힙 정렬 알고리즘은 무순의 리스트를 정렬하는 것을 목표로 한다.먼저 heap을 생성해준다. O(1)(1번째 while) 리스트가 비어질 때까지 원소를 뺀다. O(1)을

합병 정렬은 분할정복(divide-and-conquer)에 기초한 정렬 알고리즘이다. 합병 정렬은 이전 포스트에서 이야기한 힙 정렬과 같이 O(N logN)에 수행된다. 합병 정렬과 힙 정렬은 모두 비교에 기초한 정렬이다. 수행시간은 O(N logN)으로 같다. 하지만

퀵 정렬은 합병 정렬과 마찬가지로 분할정복에 기초한 정렬 알고리즘이다. 이 역시 어떠한 리스트를 2개로 쪼갠 후 정렬하고 합치는 작업을 거친다.다만, 퀵 정렬은 합병 정렬과 달리 pivot이라는 기준점을 사용해 partition한다.합병 정렬은 conquer(정복) 단

이전 포스팅까지 우선순위 큐의 개념부터 시작하여 선택 정렬, 삽입 정렬, 힙 정렬을 알아 보았다. 그리고 분할정복에 기반한 합병 정렬과 퀵 정렬도 공부했다.이들 모두 원소들을 비교하며 정렬하기에 비교 정렬 알고리즘이라고도 한다. 다만, 선택 정렬과 삽입 정렬은 O(N^

사전은 특정 키에 대한 특정 원소가 매핑되는 1대1 쌍 항목들의 모임으로 구성된다. 사전 ADT라 함은 이를 추상 데이터구조로 모델링한 것이다. 지난 정렬 파트에서는 우선순위 큐를 사용하거나 리스트의 데이터 항목들이 key로만 구성된 것을 가정하고 정렬 작업을 수행했다

무순리스트에 대한 사전 탐색은 선형탐색을 사용하고 순서리스트에 대한 사전 탐색은 이진탐색을 사용한다. 해당 포스팅에서는 리스트로 구현한 사전이 아닌 이진트리로 구현한 사전 탐색 방법을 알아볼 것이다. 이진트리를 구현하는 방식에 따라 탐색 트리를 이진탐색트리, AVL 트

탐색 트리로 구현하는 BST의 주요 메서드는 트리의 높이에 메서드의 성능이 좌지우지된다. 포스팅에서 다룰 AVL Tree(자가 균형 BST)도 트리의 높이에 따라 탐색, 삽입, 삭제의 성능이 결정되는 것은 마찬가지다. 이름에서 알 수 있듯이 BST와의 차이점은 트리

100명의 신입생을 데리고 MT를 갔다. 예약한 숙소는 3개일 때, 학생회장은 어떻게 방을 배정해야 할까?

그래프는 활용 예시를 떠올리기 가장 쉬운 ADT라고 생각한다. 지하철 노선, SNS 망, 공항 항로 등 그래프를 쉽게 접할 수 있다.그래프라는 이름에서 x, y 축의 무언가를 떠올릴 수 있지만 그래프 ADT는 네트워크 모델이라고 생각해야 한다. 이번 포스팅에서는 이후

해당 포스팅부터는 그래프 알고리즘을 배운다. 그 첫 번째로 그래프를 순회하는 방법을 알아보자.트리 구조에서 전위, 중위 순회 역시 트리 내의 모든 노드를 어떠한 순서로 방문한다. 그래프 순회 마찬가지로 그래프의 정점과 간선들을 방문하는 절차를 말한다. 그래프 순회에서는

dfs가 선위 순회와 비슷하다면 bfs는 레벨 순회와 유사하다. bfs는 순회 출발 정점의 부착간선들부터 우선 방문하는 것이 bfs와의 차이점이다. bfs는 dfs가 해결하는 문제들과 매우 비슷하다.bfs는 외부 메모리를 사용하고 dfs와 달리 재귀 호출을 하지 않는다

digraph는 directed graph의 준말로 방향간선 그래프를 뜻한다. 앞 포스팅의 dfs, bfs는 무방향간선 그래프를 가정하고 설명했다. digraph는 무방향간선 그래프의 성격과 조금 차이가 있다.방향간선 그래프의 정점 개수 n, 간선 개수 m에 대해 그래

이전 포스팅 digraph에서 이행적 폐쇄를 설명하면서 dp를 잠깐 언급했다. 동적계획볍(Dynamic Programming, DP)은 divide-conquer와 같이 알고리즘 설계 기법 중 하나다. digraph의 이행적 폐쇄를 모두 구하기 위해 모든 정점에 대한

📌 airtel 예제 dp에 대한 부족한 이해를 위해 참고서의 예제를 가져왔다. 에어텔 문제는 전형적인 그래프 문제는 아니지만 dp를 이용해 문제를 해결하고자 한다. 뿐만 아니라 분할정복 해결과의 비교를 통해 dp의 수행 효율을 알아본다. > 배경 n개의 도시가 있

최소신장트리(Minimum Spanning Tree, MST)는 그래프의 간선 가중치의 총합이 최소가 되는 신장트리다.

이번 포스팅은 저번 Prim 알고리즘에 이어서 탐욕법을 사용해 mst를 구하는 Kruskal 알고리즘과 Boruvka 알고리즘을 학습한다. Kruskal 알고리즘 크루스칼 알고리즘 역시 탐욕법에 기초한다. 크루스칼 알고리즘은 그래프 모든 정점에 대해 각각의 부분

최단경로

이번 포스팅은 다익스트라 알고리즘에 이어서 벨만포드 알고리즘으로 그래프 내 최단 경로를 찾는 방법을 배운다.벨만포드 알고리즘은 다익스트라와 달리 음의 가중치를 허용하고 양방향이 아닌 방향 간선을 전제한다. 총 V-1회의 반복 라운드를 거치고 각 라운드에서 그래프 내 모

최단 경로 포스팅 3번째는 DAG에서 최단 경로를 찾는 방법을 알아본다. DAG은 Directed Acycle Graph의 준말로 싸이클이 없는 방향그래프를 의미한다. 그래프가 DAG인 경우 다익스트라나 벨만포드 알고리즘보다 더 빠른 속도로 최단 경로를 구할 수 있다.

이전까지의 다익스트라, 벨만포드, DAG 최단 경로 알고리즘은 모든 쌍이 아닌 단일점에서 출발하는 최단 경로를 구하는 알고리즘이다. 최단 경로 포스팅의 마지막은 그래프의 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘을 학습한다. 음의 가중치가 없다면 다익스트라 알고리즘