그래프 이론(Graph Theory) 그래프 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조로 인접 행렬(2차원 배열 사용)과 인접 리스트(리스트 사용)를 이용해서 구현할 수 있다. 서로소 집합(Disjoint Sets) 공통 원소가 없는 두 집합이다. 예를 들어 집합 {1, 2}와 집합 {3, 4}는 서로소 관계이다. 반면에 집합 {1, 2}와 집합 {2, 3}은 2라는 공통 원소가 존재하기 때문에 서로소 관계가 아니다. 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조로 아래와 같이 두 종료의 연산을 지원한다. 지원하는 연산 때문에 합치기 찾기(Union Find) 자료 구조라고 불리기도 한다. 찾기(Find): 특정한 ..
최단 경로(Shortest Path) 개요 가장 짧은 경로를 찾는 알고리즘으로 '길 찾기' 문제라고도 부른다. 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 '노드(Node)'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다. 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 알고리즘이 적용된다는 특징이 있어 두 알고리즘의 한 유형으로 볼 수 있다. 컴퓨터공학과 학부에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘으로 총 3가지지만 코딩 테스트에 주로 등장하는 알고리즘에서 벨만 ..
다이나믹 프로그래밍 개요 큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 문제를 해결하는 방향에 따라 두 가지로 나뉘는데 큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운(하향식, Top-Down)방식과 작은 문제부터 차근차근 답을 도출하는 보텀업(상향식, Bottom-Up)이다. 항상 다이나믹 프로그래밍을 사용할 수는 없으며 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 잇다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 피보나치 수열은 위와 같은 조건을 만족하는 대표적인 문제이다. 피보나치 수열은 일반적으로 탑다운 방식으로 구현하면 재귀함수를 보텀업 방식으로 구현할 경우 반복문을 사용한다. 이때 ..
이진탐색 (Binary Search) 탐색 순차 탐색 (Sequential Search): 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 구현이 쉽고 시간이 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 리스트 내에서 특정한 값의 원소가 있는지 확인하거나 특정한 값을 가지는 원소의 개수를 세는 count() 메소드를 사용할 때도 내부적으로 순차 탐색이 수행된다. 최악의 경우 시간 복잡도: O(N) 이진 탐색 (Binary Saerch): 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 데이터를 매우 빠르게 찾을 수 있다는 특징이 있다. 탐색 시 위치를 나타내는 변..
정렬(Sort) 개요 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램 작성 시에 가장 많이 사용되는 알고리즘 중 하나이다. 예를 들어 이진 탐색을 하기 위해서는 전처리 과정으로 정렬이 필요하다. 선택정렬 데이터가 무작위로 여러 개 있을 때 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 방식이다. 가장 원식적인 방법으로 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라고 한다. 선택 정렬의 시간 복잡도는 O(N²)이다. 소스코드는 다음과 같다. imp..
깊이 우선 탐색과 너비 우선 탐색 (DFS & BFS) 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 두 알고리즘을 이해하기 위해서는 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다. 깊이 우선 탐색(DFS, Depth First Search): 동작 원리: 스택 구현 방법: 재귀 함수 사용 탐색 순서: 1 → 2 → 7 → 6 → 8 → 3 → 4 → 5 (1부터 시작하고 작은 순서부터 탐색한다고 가정) 수행 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드..
