1. 알고리즘 설명 그리디 - 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘  이상적인 풀이 흐름 1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다. 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다. 3. 구현해서 문제를 통과한다. 절망적인 풀이 흐름 1. 관찰을 통해 탐색 범위를 줄이는 잘못된 방법을 고안한다. 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다. 3. 믿음을 가지고 구현했는데 계속 틀린다. 코딩테스트에서의 추천 전략 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다 -> 짜서 제출해보고 틀리면 빠르게 손절 100% 확신은 없지만 맞는 것 같은 그리디 ..

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 구현..