정보 기술 놀이터

최단 경로(Shortest Path)는 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 흔히 알고 있는 최단 경로 알고리즘은 다익스트라(Dijkstra)입니다. 플로이드 워셜(Floyd-Warshall) 알고리즘 등도 존재하지만, 본 포스팅에서는 다익스트라만 다루겠습니다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류되며, 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하는 것입니다. 다익스트라 알고리즘 과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 5. 위 과정에서 3번과 4번을 반복 위와 같이 노드와 노드 간 거리(..

현실 세계에는 컴퓨터를 활용하더라도 최적의 해를 구하기에 시간이나 메모리 공간이 매우 많이 필요한 문제가 있습니다. 따라서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 합니다. 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 향상시킬 수 있는 방법이 있습니다. 그 중 하나가 바로 다이나믹 프로그래밍(Dynamic Programming)입니다. 다이나믹 프로그래밍은 동적 계획법이라고도 불리며, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(Top-Down)과 보텀엄(Bottom-Up) 2가지 방식이 있습니다. 다이나믹 프로그래밍은 다음의 조건을 만족하는 문제를 해..

이진 탐색(Binary Search)는 말 그대로 반으로 쪼개면서 탐색하는 방법입니다. 이 때, 이진 탐색 대상(리스트은 반드시 정렬되어 있어야만 사용할 수 있습니다. 이진 탐색은 순차 탐색과 달리 시작점, 끝점, 중간점 변수 3개를 이용합니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정입니다. 정렬된 데이터에서 이진 탐색 방법으로 숫자 4를 찾는 과정은 다음과 같습니다. 순차 탐색은 처음부터 끝까지 탐색하기 때문에 시간복잡도는 O(N)이지만, 이진 탐색은 단계마다 2로 나누므로 시간복잡도는 O(LogN)입니다. 코딩테스트에서는 보통 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제를 접근해야 주어진 시간안에 해결할 수 있습니다. 이..

정렬(Sorting)은 데이터를 어떠한 기준에 따라서 순서대로 나열하는 것입니다. 정렬 알고리즘은 가장 기본이 되는 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 버블 정렬(Bubble Sort)부터 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort), 계수 정렬(Count Sort) 등 매우 다양합니다. 코딩테스트에서는 Python 기본 정렬 라이브러리를 사용하면 충분히 빠른 시간내에(O(NlogN)) 정렬을 수행할 수 있습니다. 따라서, 정렬 라이브러리 사용 예제 몇 가지를 확인해 보겠습니다. def solution(arr): sorted_arr = arr.copy() sorted_arr.sort() # sorted_arr.sort(reverse=Tru..

탐색(Search)은 보통 많은 양의 데이터중에서 원하는 데이터를 찾는 것을 의미합니다. 프로그래밍에서는 그래프, 트리 등의 자료구조(Data structure)를 이용하여 탐색을 구현합니다. 탐색 방법 중 대표적인 것이 바로 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)입니다. DFS와 BFS를 구현하는 자료구조인 스택(Stack), 큐(Queue), 그래프(Graph)와 재귀 함수(Recursive Function)에 대한 설명은 생략하겠습니다. DFS는 그래프 탐색 과정에서 최대한 깊숙이 들어가서 노드를 방문한 후(리프 노드까지), 다시 돌아가 탐색하는 알고리즘입니다. DFS의 동작 과정은 다음과 같습니다. 1. 탐색 ..

구현(Implementation)은 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램 코드로 작성하는 것을 말합니다. 어떤 문제를 풀더라도 프로그램 코드 작성은 필수이기 때문에 구현 문제 유형은 모든 범위의 문제 유형을 포함하고 있습니다. 따라서, 대부분 구현 문제에 대한 별도의 유형을 정하기 어렵습니다. 보통 구현 문제는 풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 것들입니다. 결국 구현 문제는 자신의 프로그래밍 피지컬로 승부를 봐야합니다. 구현 문제를 잘 풀어내기 위해서는 자신의 주언어 라이브러리 사용법을 잘 숙지해야 합니다. 예를 들어 리스트에서 순열을 구해야 하는 문제를 만난다면 itertools 라이브러리로 쉽게 구현할 수 있습니다. 하지만 이것을 몰랐다면 많은 시간이 필요할 것입니다. 하..

그리디(Greedy)는 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘으로, 단순하지만 강력한 문제 해결 방법입니다. 즉, 그리디 알고리즘은 매 순간 가장 좋아 보이는 것을 선택하기 때문에 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다. 그리디 알고리즘을 이용한 문제 출제는 폭이 매우 넓기 때문에, 다익스트라(Dijkastra) 알고리즘과 같은 특별한 경우를 제외하고는 단순 암기를 통해 모든 문제를 해결하기는 어렵습니다. 따라서, 그리디 알고리즘이 적용 가능한 문제인지 아닌지 판단하고 실제로 풀어낼 수 있는 능력이 중요합니다. 참고로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같이 기준에 따라 선택하는 내용이 나온다면 보통 그리디 알고리즘으로 해결할 수 있습니다. ..