개발 블로그

https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 이 문제는 곱2, 나3이 섞인 수열이 존재하면, 순서에 맞는 수열을 찾는 문제입니다. 여기에서 핵심은 각 수를 소인수분해 했을 때, 3의 인수가 가장 많은 수가 제일 앞에 와야 합니다. 왜냐하면, 인수가 3이 많게 되면, 그다음 수도 자연스럽게 3으로 나누어 떨어지기 때문입니다. 그리고 3의 인수가 동일하다면 오름차순 정렬해주면 됩니다. (3의 인수가 동일한 경우에는 곱하기 2를..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 비교적 간단한 브루트포스 문제였습니다. 우선적으로 I,V,X,L을 사용하여 만들 수 있는 로마 숫자의 개수를 반환해야 합니다. 그런데 for문을 4번 돌리게 된다면, 시간 복잡도가 O(n^4)이 되기 때문에 다른 방안을 생각해야 합니다. I+V+X+L = n(사용할 로마 숫자 개수)이 되어야 합니다. 그러면 가장 큰 수를 나타내는 L의 개수는 n-X-V-I가 됩니다. 나머지 부분은 가장 작은 수 I부터 n까지 탐색하고, V는 n-I까지, X는 n-I-V까지 탐색해서 만들 수 있는 로마 숫자의 ..

https://www.acmicpc.net/problem/16917 16917번: 양념 반 후라이드 반 현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 www.acmicpc.net 문제에서 주어지는 입력 값은 양념치킨 값, 후라이드 치킨 값, 반반 치킨 값, 만들어야 할 양념치킨, 후라이드 치킨의 개수이다. 이 문제에서 신경 써야 할 부분은 반반 치킨이다. 반반 치킨을 기준으로 완전탐색(브루트 포스)을 하여 최소 금액을 구할 수 있게 됩니다. #include #include using namespace std; int main() { int a,b,c,x,y; c..

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 기존 BFS 방식(상,하,좌,우)에서 이동할 수 있는 경로가 8개가 추가되었습니다. (나이트의 이동경로 8개) 문제에서 주어지는 조건은 나이트처럼 이동할 수 있는 횟수 K와 w(가로)*h(세로)와 2차원 배열입니다. 그래서 기존 2차원 배열이 아닌, 나이트처럼 이동한 횟수를 담아야 하기에, 3차원 배열로 선언해 주었습니다. d[a][b][c] = 원숭이가 a,b로 이동하기 위해 k..

https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 이 문제는 간단하지 않은 BFS 문제입니다. 빈 물통 A, B의 용량과, 가득 찬 물통 C의 용량이 주어집니다. 이제 여기에서 각각의 물통에 물을 부어서 한 쪽이라도 물통이 비면 모든 가능한 C의 물의 양을 출력하는 경우입니다. 로직 from -> to (모든 from의 물의 양을 부어준다.) from의 물의 양 0으로 초기화 to에 가득찬 물의 양이 c의 양을 초과한 경우(f..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 이 문제도 마찬가지로 dp를 활용한 풀이입니다. 왜냐하면 값을 하나씩 누적해서 더하면 시간 복잡도가 O(2^20)이므로 dp 배열에 저장할 때, 이전 값을 참조해서 누적 값 자체를 저장해야 합니다. #include using namespace std; unsigned long long dp[1025][1025]; int main() { ios_base::..

https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 비교적 쉬운 문제의 DP 문제입니다. 백준 브론즈1 정도의 난이도입니다. 한창 생각없이 알고리즘 문제 풀 때, 이 문제를 dp로 바라보지 않고, 누적합이라고 생각했는데요. 하지만, 알고리즘을 단원별로 나눠서 풀고 문제를 바라보는 관점에 따라, 어떤 알고리즘으로 풀어야 되는지 알게되고 나서부터는 이 문제를 보자마자 DP를 써야겠다고 생각했습니다. #include using namespace std; int dp[15][15]; int ma..

Longest Increasing Subsequence(가장 긴 증가하는 부분 수열)이란? : 하위 시퀀스의 모든 요소가 오름차순으로 정렬되도록 주어진 시퀀스의 가장 긴 하위 시퀀스의 길이를 찾는 것이다. #include #include using namespace std; int d[1001]; int a[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin>>n; int i; for(i=0;i>a[i]; } int j; int max=1; for(i=0;i

Optional Substructure [최적 하위 구조] : 하위 문제의 최적 솔루션을 사용하여 문제를 최적으로 해결할 수 있는 경우 주어진 문제에 최적 하위 구조 속성이 있는 것. 동적 프로그래밍 기술은 이 속성을 활용하여 문제를 더 작은 하위 문제로 분할하고 대신 해결하는 기술입니다. 하위 솔루션 -> 상위 문제 해결 -> 최종 결과 도달 ex) 최단 경로 알고리즘(Shortest Path Problem) Source node (u) -> Destination node (v)까지의 최단 경로를 찾아야 하는 방법 x : u에서 v까지의 최단 경로에 있는 정점 u -> x : u->x 까지의 최단 경로 x -> v : x->v 까지의 최단 경로 하위 문제의 최적 솔루션을 사용하여 상위 문제 해결 (최적..

DP란 ? 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘(나무 위키) 동적 프로그래밍은 동일한 결과를 다시 계산하지 않도록, 하위 문제로 나누고 하위 문제의 결과를 저장하여 주어진 복잡한 문제를 해결하는 알고리즘 패러다임(divide and conquer와 유사, 하위 문제로 나누고 하위 문제의 솔루션을 결합하는 관점에서 유사) Mathematical Background [수학적 배경] 피보나치 수열 F(n) = F(n-1) + F(n-2) n>=2, F(1) = 1, F(0) = 0을 보면, 재귀적인 함수 호출이 있습니다. 앞선 두 숫자의 합으로 주어지는 일련의 숫자로 정의할 수 있습니다. F(2) = F(1) + F(0), F(3) ..