Back-End

[필수 알고리즘] 그리디 알고리즘(Greedy Algorithm) 이해

그리디 알고리즘 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란, "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 루트 노드부터 시작하여 거쳐 가는 노드 값의 최대로 구한다면, 값은 5+7+9 = 21로 다음과 같지만 거쳐가는 노드의 경우에서 가장 큰 값(최적의 값만) 구한다면, 값은 5+10+4 = 19 가 된다. 이처럼, 그리디 알고리즘은 최적의 값을 도출해내지 못하지만 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 그리디 알고리즘 기법 활용..

[필수 알고리즘] 이분 탐색(Binary Search) 이해

이분/이진 탐색 Binary Search 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 이진 탐색은 오름차순으로 정렬된 리스트에서 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있다. 이진 탐색 기법 활용 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 사용한다. 이때, 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같다면 종료한다. (..

[필수 알고리즘] 동적계획법 DP (Dynamic Programming) 이해

동적계획법 DP (Dynamic Programming) 동적 계획법은 프로그래밍 대회 문제에 자주 출현하는 알고리즘 기법 중 하나이며, 프로그램이 실행되는 도중, 실행에 필요한 메모리를 기억하여 할당하는 기법을 의미한다. : 큰 문제를 작은 문제로 나눈 뒤, 기억하여 푸는 기법 공간복잡도를 늘리는 대신 시간복잡도는 줄이는 방식이다. 중복되는 부분 문제 피보나치 수열을 예시로 코딩하려고 한다. 점화식이 F(n) = F(n-1) + F(n-2)이기 때문에 단순 재귀 함수로 구현된다. public class fibonacciEx{ static int fibonacci(int n){ if(n == 0) return 0; if(n == 1) return 1; return fibonacci(n - 2) + fibo..

[필수 알고리즘] BFS 너비 우선 탐색 (Queue 구조) 이해

BFS 너비 우선 탐색 (Breadth-First Search) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색한다. 그렇게 되면 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문할 수 있다. Queue를 활용해야만 순서대로 접근이 가능하다. 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다. ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 철수와 영희사이에 존재하는 경로를 찾는 경우 깊이 우선 탐색(DFS)의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름 너비 우선 탐색(BFS)의 경우 - 철수와 가까운 관계부터 탐..

[필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해

DFS 깊이 우선 탐색 (Depth-First Search) 깊이 우선 탐색 (DFS)는 하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 주로, 재귀함수 또는 Stack로 구현할 수 있다. ex) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있다. Stack으로 이해하는 DFS DFS 경로 => A, B, D, G, H, C 시간 복잡도와 장단점 인접 행렬에서의 시간 복잡도: O(V²) ..