Hello Ocean! 🌼

문제 알고리즘 문제해결 전략 8단원 문제. 원주율 외우기 https://www.algospot.com/judge/problem/read/PI algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다. 이 때, 각 조각들의 난이 www.algospot.com 입력된 수열은, 3-5자리씩 끊어서 난이도를 평..

문제 도서관 영업 후에 책 정리를 할 것이다. 재훈이의 현재 위치는 0이고, 각 책들의 위치는 절댓값이 10000이하인 정수이며, 0 위치에 있는 책은 없다. 한 번에 M개의 책을 운반할 수 있다고 할 때, 책을 모두 정리하는데 필요한 최소 걸음횟수를 구해라 . (마지막 책을 정리한 후에는 다시 원점으로 돌아올 필요가 없다.) 입력 N : 책의 개수 (1

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. => 연속하지 않아도 된다는 것이 포인트. 풀이 2차원 cache를 이용한 DP 방식으로 풀면 된다. 말로 풀어 쓴 것은 이해하기 힘드므로 그림을 그려보았다. s1 = ACAYKP s2 = CAPCAK 를 입력했을 때 cache의 모습이다. cache[i][j]에는 s1의 i 번째와 s2의 j 번째가 같을 때 값이 채워진다. (같지 않은 경우에는 0이 채워진다) 둘이 같을 때, 그냥 1을 채우는 것이 아니라 지난 구역에서 가장 큰 값+1을 채운다. 첫 번째 그림에서 빨..

[문제] 주어진 수열에 대해 최대 증가 부분 수열 구하기. 최대 증가 부분수열이란? - 원소들이 순증가하는 부분수열 중에 가장 긴 것 [풀이] 나의 풀이 n 크기의 수열에 대해 n*n 크기의 이차원 cache를 사용하자. 이 문제의 알고리즘은 위와 같다. 그리고 추가적으로 maxCount를 새 cache값을 계산해서 저장할 때 마다 갱신시켜야 한다. 그 이유는, maxCount가 첫 번째 원소부터 시작한 경우에서 나오지 않을 수 있기 때문이다. ex) 5,3,4의 경우 최대증가부분수열은 3,4가 된다. 따라서 모든 cache 내부의 값중에서 최댓값을 찾아야하는데 이 과정을 계산할 때 한번에 하기 위해서 maxCount를 사용한다. (뒤에 코드를 보면 이해가 더 잘 될 것이다.) 알고리즘에 대해 좀 더 복..

[문제] 삼각형 모양으로 배치된 수들이 있다. 이 수들에 대해서 위에서부터 아래로 내려오는 경로를 만드려고 한다. 아래 줄로 내려갈 때 마다, 바로 아랫칸이나 한칸 오른쪽 아래칸으로 내려갈 수 있다. 지나온 경로상의 모든 수의 합의 최댓값을 구해라. [Input] C (testcase 수) 각 testcase마다 n (층의 개수) n줄에 걸쳐 삼각형 각 가로줄에 있는 숫자 입력 [Output] 각 testcase마다 최대 경로 숫자의 합 [풀이] 알고리즘은 위와 같다. dynamic programming을 사용하면, 모든 경로를 하나씩 살펴보지 않고, 바로 위에 칸과의 경우의수만 계산해주면 되기 때문에 복잡도를 크게 줄일 수 있다. 이 알고리즘의 복잡도는 O(n^2)이다. 좀 더 큰 input의 예시를 ..

[문제] 기호 1번으로 출마한 다솜이는 선거 전에 후보별 득표수를 미리 알 수 있다. 다솜이는 득표수를 미리 알아낸 후, 다른 후보를 찍는 사람들을 돈으로 매수해서 자신이 당선되게 하려고 한다. 다솜이가 매수해야 할 사람의 최솟값을 구해라. [Input] N(후보의 수) 둘째 줄 부터 각 후보의 득표수가 N줄에 걸쳐서 입력된다. [Output] 매수해야 할 사람의 최솟값 [풀이] 완전탐색 우선 가장 기본적인 방법으로 접근해보자. 전체 후보의 득표수가 votesNum[] 안에 순차적으로 저장되어 있다고 하자. 후보가 3명이고 각 후보의 예상 득표수가 5,7,7이었다고 하자. voteNum[]에서 max 위치를 구하고, 다솜이(기호 1번)가 최댓값이 아닐 경우 해당 max 위치에서 1을 빼고, 그 표를 다솜..