순차 탐색 리스트 A에 n개의 수가 저장되어 있을 때, 어떤 수 X가 A에 저장되어 있는지 알고 싶다. X가 A에 없는 경우 A의 첫번째 원소부터 마지막 원소까지 모든 수를 살펴봐야 하므로 n번의 비교가 반드시 필요하고, 이에 따른 시간 복잡도는 O(n)이다. 이와 같이 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이 바로 순차 탐색이다. 이진 탐색 하지만, 만약 A의 수들이 오름차순으로 정렬된 상태라면 더 적은 비교를 통해 X를 찾을 수 있다. 바로 이진탐색을 이용하는 것이다. 이진 탐색이란 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 탐색 범위가 매우 큰 문제가 주어질 때, 이진 탐색을 이용하면 문제를 효율적으로 해결할 수 ..
1. 최단 경로의 이해 먼저 최단 경로의 기본 성질에 대해 파악해보자. u → v : 노드 u에서 노드 v로의 하나의 엣지로 구성된 경로 s ⇝ v : 노드 s에서 v로의 경로를 표 시하고, 중간에 여러 노드가 존재 가능 s ⇝ u → v 인 경우, 이 경로에서 u는 v의 predecessor 또는 parent이다 만약 s ⇝ u → v 가 s에서 v로의 최단 경로 중 하나라면, s ⇝ u 역시 s에서 u까지의 최단 경로 중 하나이다. s에서 v까지의 여러 경로 중에서 u를 통해 v에 도달하는 경로중에 최단 경로가 있다는 의미이고, s ⇝ u를 먼저 계 산하여 알고 있다면, s ⇝ u → v는 쉽게 계산할 수 있다. dist[v] = "s에서 v까지의 최단 경로의 길이"라고 정의하면 다음과 같은 식이 성..
그래프 순회란? 그래프 순회란 그래프 탐색(Search)라고도 일컫으며 그래프의 각 정점을 방문하는 과정을 의미하며, 크게 깊이 우선 탐색(DFS, Depth-First Search)과 너비 우선 탐색(BFS, Breadth-First Search)으로 나뉜다. DFS는 주로 스택이나 재귀로 구현하며 백트래킹 알고리즘에 사용된다. 반면에 BFS는 주로 큐로 구현하며 그래프의 최단 경로를 구하는 문제 등에 사용된다. 깊이 우선 탐색(DFS) 일반적으로 DFS는 스택으로 구현하며, 재귀를 이용하면 좀 더 간단하게 구현할 수 있다. 실제로 코딩 테스트에서는 재귀를 이용한 구현이 더 선호되는 편이다. 재귀적 구조로 구현 먼저 재귀 구조로 DFS를 구현해보자. 슈도코드는 다음과 같다. RecursiveDFS(v)..
동적 계획법 푸는 방법 (DP 풀이) 알고리즘 중 하나인 동적 계획법, 사실 알고리즘 자체보다는 순발력을 요하는 경우가 잦아 많은 연습이 필요한 알고리즘이다. 이러한 동적 계획법에 대해 소개하고 어떻게 풀이해야 하는지에 대한 글이 있어 소개하고자 한다. 결론은 많은 연습과 직관이지만, 풀이 단계를 체계적으로 나누고 실제로 적용해봄에 의의가 있다고 생각된다. (원문: www.geeksforgeeks.org/solve-dynamic-programming-problem/) 동적 계획법(DP, Dynamic Programming)은 다항식 시간의 특정 유형의 문제를 해결하는 기술이다. 동적 계획법은 지수 시간의 브루트 포스 방식보다 빠르며 정확하다. 동적 계획법을 풀기 위해선 선행 학습되어야 할 내용들이 있다...
