본문 바로가기

Algorithm45

17478_재귀함수가 뭔가요? ▶실버5 풀이 재귀함수 문제. 조건에 상관없이 재귀함수에서 항상 실행되는 문장은 "재귀함수가 뭔가요?" i 가 아직 n에 도달하지 않았을 때 실행될 문장은 "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어." i가 n에 도달했을 때 실행될 문장은 "재귀함수는 자기 자신을 호출하는 함수라네" "라고 답변하였지." 마지막으로 재귀함수가 닫힌 후 실행될 문장은 "라고 답변하였지." 코드 #include #include #include #include using namespace std; void rec(.. 2023. 1. 22.
2156_포도주 시식 ▶실버1 풀이 연속으로 3잔을 마실 수 없으므로 2잔을 연속으로 마시면 한 잔은 쉬어야 하는데, 최대의 합을 내기 위해서는 연속 두 잔 이상을 마시지 않으면 안된다. 즉, 1번 잔을 마셨으면 꼭 2번 잔을 마시거나 3번 잔을 마셔야 한다. 2번과 3번을 모두 마시지 않으면 최대 값을 낼 수 없다. 이 점을 참고! 예제에서 5번째 잔까지만 표로 나타내면 6 10 13 9 8 여기서 모든 경우의 수는 (1, 2, 4, 5) (2, 3, 5) (1, 3, 4) 이다. ① (1, 2, 4, 5) => dp[2] + arr[4] + arr[5] ② (2, 3, 5) => dp[3] + arr[5] ③ (1, 3, 4) => dp[4] 이를 점화식으로 나타내면 dp[i] = max({ dp[i - 3] + arr[.. 2023. 1. 16.
9465_스티커 ▶실버1 풀이 여기서 중요하게 봐야할 것은 두 변을 공유하지 않는다는 점이다. 이 점을 참고하여 배열을 arr[i][j], dp[i][j] 두 개 만든다.(i는행, j는 열) ① n = 1이라면, 50 10 dp[0][0]의 값은 50이며, dp[1][0]의 값은 10이다. ② n = 2이라면, 50 10 30 50 dp[0][1]의 값은 dp[1][0] + arr[0][1] = 30 + 10 = 40 dp[1][1]의 값은 dp[0][0] + arr[1][1] = 50 + 50 = 100 이다. ③ n = 3이라면, 50 10 100 30 50 70 여기서부터 살짝 복잡해지는데, dp값이 두 가지 경우일 수 있다. dp[0][2]의 값은 dp[1][1], dp[1][0]의 값 중 큰 값에 arr[0][.. 2023. 1. 16.
1699_제곱수의 합 ▶실버2 풀이 ex) n = 12라면, ① dp[12 - 1*1] = dp[11], dp[12 - 2*2] = dp[8], dp[12 - 3*3] = dp[4] 중 가장 작은 값에 +1한 값이 dp[12]가 된다. 하지만 dp[1~11] 의 값을 알기 위해서는 1부터 1씩 증가하며 dp값을 구하는 작업을 먼저 진행한다. i = 1) dp[1] = 1 i = 2) dp[2]: dp[2 - 1*1] + 1= dp[1] + 1 = 2 i = 3) dp[3]: dp[3 - 1*1] + 1 = dp[2] + 1 = 3 ... 이런식으로 n까지 진행하는 과정에서, i 값에 따라 ①을 진행한다. 또, 주의할 점은 dp의 값을 dp값이 가질 수 있는 최대의 항의 수 개수로 초기화 해야한다. (dp[i] = i) 코드 .. 2023. 1. 13.
11660_구간 합 구하기 5 ▶실버1 풀이 누적 합 이용. 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 3 4 5 3 0 3 4 5 6 4 0 4 5 6 7 => 배열 표 0 1 2 3 4 0 0 0 0 0 0 1 0 1 3 6 10 2 0 3 8 15 24 3 0 6 15 27 42 4 0 10 24 42 64 => 누적 합 표 ex) (2, 2) ~ (3, 4) 의 구간 합 이는 8 + 15 + 24 + 15 + 27 + 42 와 같은데, 누적합을 이용하면 sum[3][4] - sum[3][1] - sum[1][4] + sum[1][1] 임을 알 수 있다. 이를 통하여 (x1, y1) ~ (x2, y2)의 구간 합의 점화식은 sum[x2][y2] - sum[x2][y1 -1] - sum[x1 - 1][.. 2023. 1. 11.
11055_가장 큰 증가 부분 수열 ▶실버2 풀이 기본적으로 dp[i] = arr[i]인 상태에서 arr[j](이전 값) < arr[i](현재 기준값)을 만족할 때, dp[j] + arr[i] 와 dp[i] 중 큰 값을 선택하여 dp[i]에 대입한다. 위의 예제를 표로 나타내면 1 100 2 50 60 3 5 6 7 8 1 101 1 + 2 = 3 max(1, 3) + 50 = 53 max(1, 3, 53) + 60 = 113 max(1, 3) + 3 = 6 max(1, 3, 6) + 5 = 11 max(1, 3, 6, 11) + 6 = 17 max(1, 3, 6, 11, 17) + 7 = 24 max(1, 3, 6, 11, 17, 24) + 8 = 32 dp값 중 가장 큰 값이 답 코드 #include #include #include u.. 2023. 1. 10.

티스토리툴바