점화식
-
BOJ) 가장 큰 정사각형알고리즘/백준 2020. 8. 26. 15:22
가장 큰 정사각형 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 전에 푼 적이 있는 문제여서, 비교적 쉽게 풀 수 있었다. 당시에는 어떻게 풀어야하는지 막막했었는데, 그때 봤던 풀이가 아직 머릿속에 남아있었다. 우선, 맵을 돌면서 1인 경우에 좌측 상단, 좌측, 상단 세 군데를 확인한다. 세 곳의 최소값 +1(자기자신)이 dp의 값이 된다. dp[y][[x] += min(dp[y-1[[x-1], dp[y-1][x], dp[y][x-1]) 이 된다는 소리다. 변이 2인 사각형은 2로, 3을 만족하는 사각형은 3으로 값이 정해지는 것이다. (손으로 위의 식을 풀어가다보면 쉽게..
-
BOJ) 동물원 (1309, JAVA)알고리즘/백준 2020. 8. 24. 16:44
풀이 코드 라인을 보면 아주 간단한 문제라고 여겨지겠지만, 점화식을 도출하는 것이 어려웠다. 더 사실대로 말하자면, 혼자 도출하지 못했고 다른 풀이에서 점화식을 얻어왔다고 표현하는게 더 맞는 것 같다. 처음에는 Combination과 같은 경우를 찾는 식을 활용하는 방향으로 접근했다.하지만 어떤 식도 부합하는 것이 없었고, n=1 ~ n=4까지 직접 경우의 수를 찾아봤다. n=1 => 3n=2 => 7n=3 => 17n=4 => 41 위와 같이 경우의 수가 나왔다.위에서 유추할 수 있는 것은, dp[n] = dp[n-1]*2 + dp[n-2] 라는 식이다.n-1의 경우의 수 *2 + n-2의 경우의 수가 되는데, 왜 이 식이 성립하는지는 아직 명확하지 않다.n이 1씩 증가할 때마다, 2칸이 생기기 때문에..
-
BOJ) 이항 계수 2알고리즘/백준 2020. 8. 8. 15:49
이항 계수 2 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCr 을 구하는 문제다. nCr = n-1Cr-1 + n-1Cr 이라는 공식을 저번에 이어서, 다시 한번 머리에 남기기 위해 포스팅 한다. r이 0일 때와, n일 때 1로 설정하고, 나머지 r에 대해서 위의 공식을 적용하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public sta..
-
BOJ) 동전 1알고리즘/백준 2020. 7. 18. 21:56
동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 n 가지 종류의 동전을 각각 여러개 이용해서 k원이 되게 하는 수를 구하는 문제다. 처음에는 dfs로 접근했다가, 동전은 몇개라도 사용할 수 있다는 조건을 보고 DP로 선회했다. 각각 동전에 대해서 K원 이하일 때, 쓰일 수 있는 모든 돈에 경우의 수를 추가시켜주었다. for문을 돌면서 각 동전 coin에 대해coin의 가치부터 K원 까지 들어갈 수 있는 경우만 추가시켜주면 해결되는 문제였다. 코드 import java.io.BufferedReade..
-
BOJ) 다리 놓기알고리즘/백준 2020. 7. 16. 16:42
다리 놓기 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 강의 왼쪽과 오른쪽에 다리를 건설하는데, 교차해서 지으면 안되는 조건의 문제다. 왼쪽보다 오른쪽에 다리를 지을 수 있는 포인트가 더 많다. 여기서 Combination 문제라고 생각했다. 하지만, 30이나 되는 수에서 직접 Combiantion을 구할 수 없었기 때문에 수학 공식을 찾아봤다. nCr = n-1Cr-1 + n-1Cr 이라는 공식이 있다는 것을 알았다. 앞으로는 콤비네이션을 이용해 푸는 문제를 만났을 때, 더욱 효율적으로 풀기 위해 ..
-
BOJ) 쉬운 계단 수알고리즘/백준 2020. 7. 6. 18:27
쉬운 계단 수 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 문제 제목은 쉬운 계단 수 인데, 어렵다.. ㅋㅋㅋㅋ DP 문제를 푼지 오래된 것 같아서 DP 문제를 선택해봤다. 우선 2차원 배열을 사이즈에 따라 생성하는 것 까지는 해놓고 생각을 했다. n자리 수 때, 0~9 숫자가 몇 번 쓰이는지 저장을 해야 풀 수 있는 문제인가 생각을 해보았다. 한 20분정도 생각했는데 이 방법은 아니었다. 다른 저장 방법은 없을까 고민했지만 떠오르지 않았다. 위의 생각에 빠져서 해당 숫자에서 -1 , +1 사이에 있어야 하는 것을 간과한 것이다.. 그래서 질문하기 게시판을 참고했다. 코드가 있는 질문들은 과감하게 넘기고 점화식을 물..
-
BOJ) 1,2,3 더하기알고리즘/백준 2020. 6. 29. 15:49
1,2,3 더하기 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 풀이 브루트 포스 문제로 입력값 n을 1, 2, 3 숫자의 합으로 나타낼 수 있는 경우의 수를 구하는 문제다. 또한, 순서가 있기 때문에, 1+1+2 와 1+2+1은 다른 것으로 간주한다. 예전에 풀었던 문제인데, 기억에 남아있지 않아서 새롭게 풀었다. 먼저, 예전에 풀었던 방식은 점화식을 통해서 답을 찾았었다. dn = dn-3 + dn-2 + dn-1 이라는 식이 나와서..
-
프로그래머스 Lv.3) 기지국 설치알고리즘/프로그래머스 2020. 6. 1. 17:48
Summer/Winter Coding(~2018) 기지국 설치 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 두번의 수정을 거쳤고, 푸는데 20분? 30분?정도 걸린 것 같다. 우선, 문제의 조건에 N이 2억 이하의 자연수 임을 보고 배열은 안된다는 판단을 내렸다. 된다 하더라도 효율이 안좋을 것이기 때문에 사용을 안하려고 마음먹었다. 다음으로 stations 배열은 오름차순으로 정렬되어 있다는 것을 보고, 이전에 설치된 5G망과 현재 설치된 5G망 사이에 커버하지 못한 아파트 세대..