최단 거리 알고리즘에는 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 등이 있다. 이 중 다익스트라 최단 경로와 플로이드 워셜 알고리즘이 코딩 테스트에서 가장 많이 등장하는 유형이다. 또한 최단 경로 알고리즘은 그리디와 DP의 한 유형으로 볼 수 있다. 그럼 다익스트라 최단 경로와 와 플로이드 워셜 알고리즘을 알아보자. 📌 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발해 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작하며, 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 다음과 ..
코딩 테스트 문제 중에서 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 엄청나게 증가시킬 수 있는 방법이 있다. 대표적인 방법으로 다이나믹 프로그래밍이 있는데 오늘은 이에 대해서 알아보려고 한다. 📌 다이나믹 프로그래밍이란? 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 즉, 중복되는 연산을 줄이고 메모리를 조금 더 사용해 연산속도를 줄인다는 것이다. 보통 줄여서 DP라고 부르며, 동적계획법이라고 부르기도 한다. 예시를 보며 DP를 좀 더 이해해보자. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다. 다음과 같이 재귀를 이용해 피보나치 수를 구하는 함수를 만들었다고 해보자. int fibo(int x) { i..
📌 이진 탐색이란? 이진 탐색(Binary Search)는 정렬되어 있는 데이터가 있을 때 탐색 범위를 절반씩 좁혀가며 탐색하는 알고리즘이다. 이진 탐색에서는 위치를 나타내는 변수 3개(시작점, 중간점, 끝점)을 사용해, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 이진 탐색은 데이터를 절반씩 줄어들도록 만들기 때문에 시간 복작도가 O(logN)이다. // 재귀 함수로 구현 int binarySearch(vector &arr, int target, int start, int end) { if (start > end) return -1; int mid = (start + end) / 2; if (arr[mid] == target) return mid; else..
오늘은 정렬 알고리즘에 대해 알아보도록 하자. 내림차순은 비교하는 부분에서 부호만 바꿔주면 되기 때문에 오름차순을 기준으로 설명하려고 한다. 📌 선택 정렬 (Selection Sort) 선택 정렬은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해 두 번째 데이터와 바꾸고... 이런 과정을 반복해 정렬하는 방법이다. #include "iostream" using namespace std; int main() { int arr[] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; for (int i = 0; i ..
📌 그래프의 기본 구조 DFS와 BFS를 공부하기 앞서, 그래프의 기본 구조를 먼저 알아보자. 그래프는 노드(Node)와 간선(Edge)로 표현되며, 이때 노드를 정점(Vertex)라고도 한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한, 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 프로그래밍에서는 그래프를 크게 2가지 방식으로 표현할 수 있는데, 코딩 테스트에서도 필요한 개념이니 꼭 숙지하도록 하자. 1. 인접 행렬(Adjacency Matrix) 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같은 예시 그래프가 있다고 했을 때, 이..
📌 구현(Implementation) 이란? 코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 구현 문제는 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이지만, 보통 특별한 알고리즘보다는 문제를 요구사항에 맞춰 코드로 풀어내는 능력 + 프로그래밍 언어의 문법의 정확한 이해를 갖추고 있는지 보는 문제라고 생각하면 될 것 같다. 예시로는 다음과 같은 것들이 있다. 알고리즘은 간단한데 코드가 지나치게 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 사소한 조건 설정이 많은 문제 보통 구현 문제는 사소한 입력 조건 등을 문제에서 명시해주며 문제의 길이가 꽤 긴 편이다. 하지만 고차원적인 ..
📌 그리디 알고리즘이란? 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'으로, 단순하지만 강력한 문제 해결 방법이다. 우리는 특정 문제를 만났을 때, 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로, 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이러한 기준은 정렬 알고리즘으로 만족시킬 수 있으므로 그리디 알고리즘 문제는 정렬과 짝을 이뤄 출제된다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 크다. 그렇기 때문에, 그리디 알고리즘으로 문제의 해결책을 찾았을 때는 그것이..
오늘은 시간 복잡도와 공간 복잡도에 대해서 간단히 알아보고, 코테 문제를 풀 때 알아두면 좋을 내용을 정리해보려고 한다! 📌 시간 복잡도 알고리즘이 얼마나 오래 걸리는지 알 수 있는 척도로, 알고리즘을 위해 필요한 연산의 횟수를 의미한다. 코테 문제에는 '시간 제한'이라는 것이 있다. 여기서 말하는 시간 제한은 문제를 푸는 시간이 아니라, 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는 데까지 걸리는 시간을 의미한다. 그래서, 프로그램을 비효율적으로 작성하면 '시간 초과' 메시지와 함께 오답 처리가 된다. 따라서, 문제를 풀 때 최악의 연산량을 계산해 내가 사용할 수 있는 알고리즘을 고르는 것이 좋다. 아래는 대표적인 시간 복잡도를 나타낸 것이다. 빅오 표기법 명칭 N=1000일..
