Algorithm/알고리즘 접근법 정리4 최단거리 개념 및 문제 접근 방법 0. 개요 - 최단 거리 알고리즘은 그래프 탐색 알고리즘 중 하나이다. - 최단 거리 알고리즘의 종류와 개념 그리고 문제 접근 방법에 대해서 알아보자. 1. 최단 거리 개념과 종류 a) 최단 거리의 의미 - 최단 거리 문제에서 최단 거리는 다음 2가지 경우 중 하나에 해당한다. → 지나온 간선(edge)의 개수가 가장 적은 경로를 찾는 경우 (가중치가 없는 그래프) → 지나온 간선(edge)의 가중치(weight) 합이 가장 작은 경로를 찾는 경우 (가중치가 있는 그래프) b) 최단 거리의 종류 - 최단 거리 문제는 기본적으로 시작점과 도착점이 주어진다. - 시작점과 도착점을 기준으로 최단 경로(간선의 개수 또는 간선 가중치의 합)를 구하는 것이 문제의 핵심이다. - 시작점과 도착점의 구성 방식에 따라서.. 2022. 7. 18. DFS/BFS 개념 및 문제 접근 방법 0. 개요 - DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. - DFS와 BFS가 어떻게 다른지, 언제 사용되는지 알아보자. 1. DFS(Depth First Search) a) DFS의 탐색 방법 - DFS는 다음과 같은 탐색 순서를 갖는다. - DFS는 하나의 방향을 결정하면 그 방향을 따라 끝까지 도달한다. ▶ 트리의 경우, 왼쪽에 위치한 노드를 우선적으로 탐색한다. ▶ 그래프의 경우, 가중치 또는 특정 기준을 따라 탐색 방향의 우선순위를 결정한다. - 위의 그림을 토대로 DFS는 다음과 같은 탐색 순서를 갖는다. ▶ 0번을 시작으로 왼쪽에 위치한 노드를 우선적으로 탐색한다. (0 ~ 3번 노드로 탐색) ▶ 3번 노드가 끝이므로 이전 단계로 돌아간다. (1번 노드로 돌아감) ▶ 1번 노드에서.. 2022. 7. 5. DP(동적 계획법) 개념 및 문제 접근 방식 0. 개요 - DP(동적 계획법)은 어떤 공식이나 특정 형태가 아닌 방법론에 가까운 개념으로써의 알고리즘이다. - 그래서 이론적으로 DP를 이해하기는 쉽지만, 문제에 적용하기가 쉽지 않다. - 필자가 그랬기에, DP 개념과 문제 접근 방식을 이해하기 쉽게 설명해보려 한다. 1. DP(동적 계획법)란? - DP에 대해 검색해보면 다음과 같은 대표적인 표현이 등장한다. → "하나의 큰 문제를 작은 문제로 나누고, 그 작은 문제를 해결하여 큰 문제의 답을 도출해내는 기법" → "작은 문제를 해결하는 과정에서 중복되는 연산을 수행하지 않는 기법" - 도대체 이게 무슨 말일까? - 피보나치 문제를 예시로 DP의 특징과 문제 접근 방식에 대해 알아보자. 2. DP 문제 접근 방식 - 피보나치 문제를 이용하여 DP .. 2022. 6. 20. 재귀 함수의 개념 및 문제 접근방식 0. 개요 - 최근 Tree 문제를 풀기 시작하면서 재귀 함수를 사용한 풀이를 많이 접했다. - 재귀 함수(= Recursion)를 사용하면 연산 속도도 빠르고 작성하는 코드 또한 간결해진다. - 그래서 Recursion을 제대로 알고 사용하고 싶지만, 감이 잡힐 것 같으면서도 잡히지 않는다. - 이와 같은 이유로 Recursion을 정복하고 싶다는 생각에 이번 포스팅을 작성한다. - 나와 같이 Recursion에 어려움을 겪는 분들에게 도움이 되기를 바란다. 1. Recursion 이란? - Recursion은 함수 내부에서 자기 자신을 다시 호출하는 형태를 가진 함수를 말한다. 2. 재귀 함수 작성 규칙 - 재귀 함수를 작성할 때 지켜야 하는 2가지 규칙이 있다. a) Base case(반복을 멈추는.. 2022. 3. 11. 이전 1 다음
