knowledge/algorithm

[ 알고리즘 ] 동적 계획법 ( Dynamic Programming, DP )의 이해와 구현 with C++

동적 계획법( Dynamic Programming)이란? 동적 계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 동적 계획법은 구체적인 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다. 동적 계획법은 영문으로 표기하면 Dynamic Programming인데 이름과 달리 다이내믹하진 않고 동적 계획법의 고안자가 멋있어 보여서 이름을 이렇게 지었다고 한다. 이광근 교수는 동적 계획법을 "기억하며 풀기"라고 번역하였다. 동적 계획법을 사용하는 이유 동적 계획법은 일반적인 재귀와 유사하다. 하지만 재귀는 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산을 한다는 점이 동적 계획법과의 큰 차이이다. 이 예로 피보나치수..

[ 알고리즘 ] 투포인터 ( Two Pointer )의 이해 및 구현

투 포인터(Two Pointer)란? 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 두 개의 포인터를 만들어 각각이 가리키는 원소에 의미를 부여해 요구하는 문제를 해결하는 알고리즘 포인터 2개가 같은 방향으로 진행해 나가는 것 , 포인터 2개가 양끝에서 반대로 진행해 나가는 것, 포인터 하나는 한쪽으로 이동하고 다른 포인터는 양쪽으로 이동하는 것 등이 대표적 예시이다. 대표 문제 풀이 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]..

[ 알고리즘 ] DFS ( 깊이 우선 탐색 ) 와 BFS ( 너비 우선 탐색 )의 이해 및 구현

트리나 그래프를 탐색하는 방법은 크게 DFS 알고리즘과 BFS알고리즘 , 두 가지로 나누어진다. 1. DFS ( Depth-First-Search , 깊이 우선 탐색 ) DFS란 시작점부터 다음 분기로 넘어가기 전 해당 분기를 완전히 탐색하는 방법을 말한다. DFS는 재귀함수나 스택으로 구현되며 모든 분기를 탐색하고자 할 때 사용된다. DFS는 아래 서술할 BFS보다 구현은 쉽지만 탐색 속도가 느리다. 2. BFS ( Breadth-First-Search , 너비 우선 탐색 ) BFS란 임의의 노드 ( 주로 root 노드 ) 부터 인접한 노드들을 먼저 탐색하는 방법을 말한다. 즉 시작 정점에서 가까운 노드들부터 먼저 방문하고 멀리 있는 노드는 비교적 나중에 탐색하는 순환 방법이라 할 수 있겠다. BFS는..