https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.www.acmicpc.net1. Logic- 검은색이 먼저나오는 최적의 배열과 흰색의 먼저 나오는 최적의 배열을 선언. - 검은색이 먼저나오는 배열을 확인하는 함수와 흰색이 먼저나오는 배열을 확인하는 함수를 실행시켜서 두개의 함수의 최솟값을 Answer 배열에 저장 #include using namespace std; string arr[51]; string whitef[8] = { "WBWBWBWB", "BWBWBWBW..
Algorithm
https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 1. Logic - 값을 확인해주며 0이 나왔을때는 값을 빼줘야하기때문에 후입선출(Last In First Out)의 성질을 가진 stack 활용. - 정수가 입력되면 sum에 더해주고 0이 나오게되면 stack의 최상단 값을 sum에 빼주고 stack에서 pop #include using namespace std; stack s; int main() { int ..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. Logic - 버틸수 있는 무게 >= 지금까지의 무게 + 이번(넣을 or 넣지 않을) 차례의 무게 - 가능하다면 이후의 항의 최댓값에 현재 배낭의 value를 더해주기 #include using namespace std; vector goods; int dp[101][100001]; int n, k; int solve(int ..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. Dynamic programming(동적 계획법) - 하나의 큰 문제를 작은 문제로 나누어 푸는 방법 - 재귀로 풀게되면 계산했던 경우의 수도 한번 더 하기 때문에 메모이제이션(Memoization)을 통해 계산한 값을 배열에 저장하고 다음 호출때 이전에 계산했던 값을 만나게 되면 계산하지 않고 값을 불러와서 사용함. - 시간복잡도를 현저히 줄일 수 있음. 2. Logic 1. 조건에 맞춰 3가지 분기를 만든다. 2. 완성된 수가 주어지기 때문에 주어진 수에서 1로 만들어가며 실행한다 3. 기저조건은 수가..
