1. 알고리즘 설명 다이나믹 프로그래밍(Dynamic Programming, DP) - 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태의 알고리즘이다. dp를 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 2. 연습 문제 BOJ 1463번: 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 테이블 정의하기 d[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 d[12] = ? 3으로 나누거나 (d[12] = d..

1. 알고리즘 설명 시뮬레이션 - BFS나 재귀와 같이 특정 자료구조 혹은 알고리즘에 종속되지 않고 주어진 문제 상황을 구현하면 되는데 이 때 구현이 빡세게 필요한 것들을 통틀어서 시뮬레이션 유형의 문제라고 한다. 2. 연습 문제 1 - 감시 BOJ 15683번: 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. 각 cctv 방향 정하기 2. 정한 방향에 대해 사각 지대의 크기 구하기 두 가지로 나눠서 생각하면 된다. cctv의 방향을 정할 때는 4종류의 방향에 대해 4진법을 사용한다. 나머..

1. 알고리즘 설명 백트래킹 - 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 상태공간트리 - 백트래킹의 모든 후보군의 상태를 나타내는 트리. 2. 연습 문제 1 - N과 M BOJ 15649번: N과 M (1) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 8중 for문으로도 구현 가능하지만 백트레킹을 이용하면 더 좋다. #include #define MAX 10 using namespace std; int n,m; int arr[MAX]; bool isused[MAX]; void f..

1. 알고리즘 설명 재귀 - 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 재귀로 N부터 1까지 출력하는 함수 & 1부터 N까지의 합을 구하는 함수 void func1(int n){ if (n==0)return; cout 2 출력 -> func1(1) 호출 -> 1 출력 -> func1(0) 호출 -> 종료 이렇게 과정을 따라가고 나면 func1(3)을 실행했을 때 3 2 1이 출력된다는 것을 알 수 있다. 2. 귀납적 사고 func1(1)이 1을 출력한다. func1(k)가 k k-1 k-2 … 1을 출력하면, 즉 k부터 1까지 차례대로 출력하면 func1(k+1)은 k+1부터 1까지 차례로 출력한다는걸 보여야 한다. k+1이 출력된 이후 func1(k)가 호출되고 func1(k)는..

1. 알고리즘 설명 DFS - 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 2. 예시 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2. 스택에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 4. 스택가 빌 때 까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N). 사실상 BFS에서 큐가 스택으로 바뀐 것이다. 큐 - BFS 스택 - DFS DFS도 BFS처럼 Flood Fill이 필요할 때 사용할 수 있다. BFS와 DFS는 방문 결과는 똑같지만 방문 순서에서 큰 차이가 있다. DFS 구현..

1. 알고리즘 설명 Flood Fill - 외부 윤곽선을 따라서 구분되는 영역의 색을 한꺼번에 바꾸는 것 구현 방법 - BFS BFS - 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 2. 예시 우선 BFS 알고리즘에서는 좌표를 담을 큐가 필요하다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣는다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하면 된다. 큐가 빈 순간 과정은 종료되고 (0, 0)과 상하좌우로 이어진 모든 같은 영역의 칸을 잘 방문했음을 알 수 있다. 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 원소를 꺼내어 그..