전체 글
프로그래머스 42895 N으로 표현
문제 문제 분석 나는 그냥 DP로 풀었다. 현재 N의 갯수가 i라고 할 때 가능한 모든 경우의 수를 DP[i][something]에 저장하자고 하고 1부터 i-1까지는 모두 다 정확하게 정의되어 있다고 하자. 그렇다면 i는 다음과 같이 2개로 나눌 수 있다. (1, i-1), (2, i-2), (3, i-3) ...(i-1, 1) 그리고 이렇게 분할된 두개의 조각에 존재하는 모든 조합의 사칙연산의 결과값을 DP[i][idx]에 저장한다. 이렇게 하다보면 결국에는 될것이다. 이걸 dfs로써 풀 수 있다고 하는데 그런 분들의 코드를 보면 하나같이 왼쪽의 데이터를 새로운 데이터로 구성하고 오른쪽은 고정된 값들 ( temp = temp * 10 + N / 즉 N, NN, NNN등)으로만 구성하던데 이렇게 하면 ..
Parametric search algorithm, 2805 백준
알고리즘 분석 파라메트릭 서치 알고리즘이란? In the design and analysis of algorithms for combinatorial optimization, parametric search is a technique for transforming a decision algorithm (does this optimization problem have a solution with quality better than some given threshold?) into an optimization algorithm (find the best solution). -> 결정 알고리즘을 최적화 알고리즘으로 변형해주는 알고리즘이다. 이때 결정 문제를 해결하여 최적의 값을 얻기 위해소서는 정답의 후보군이..
13270 백준 피보나치 치킨
문제 문제 분석 i번째 피보나치 수열을 저장하는 배열을 DP[i]라고 하자. 예시를 보면 알겠지만, 인원수와 닭 수 모두 피보나치 수열의 형태를 띄고, DP[i]인 DP[i-1]형태를 띈다. 문제는 이것을 이용해서 어떻게 최대, 최소를 구할까?... 인데 이 문제에서 가장 마음에 들지 않았던 부분은 N을 정확하게 명시하지 않았았다는 점이었다. N이 제대로 명시되지 않았기 때문에 어느정도의 복잡도를 가져도 되는지 정확하게 파악하지 못했고, DP보다는 수학적으로 접근하려고 시도했었다. (뭐 대충 3천정도라 하는데 이걸 어케알아 ㅋㅋ) 그래서 수학적으로 최소는 구해보았는데, DP[i] = DP[i-1] + DP[i-2]이고 DP[i-1] / DP[i]의 비율이 가장 낮은 경우의 수들을 골라야 한다. DP[i-..
백준 11054 번 가장 긴 바이토닉 부분 수열
문제 문제 분석 DP문제이다. 우선 증가하는 부분수열과 감소하는 부분수열로 문제로 나누어 보았다. 그 결과가 (1,2,3,2,1)이라고 가정하자. 그렇다면 "3"을 갖는 인덱스를 기준으로 양 옆으로 나뉠것이다. 물론 3이 여러개일 수도 있고 위치마다 결과는 다르지만 최적의 값을 도출하는 인덱스를 X라고 가정하자. 결과가 가장 긴 바이토닉 수열이 되기 위해서는 (X번째 인덱스 이전을 기준으로 증가하는 수열 + X번째 인덱스 이전을 기준으로 감소하는 수열)이 최대가 되는 경우일 것이다. 그렇다면 모든 인덱스 i에 대하여 해당 인덱스 전까지의 증가하는 수열과 i이후의 감소하는 수열의 길이를 구하고 모든 인덱스에 대하여 비교하면 될것이다. 그렇다면 증가 / 감소하는 수열을 어떻게 구하는지 알아보기에 앞서 우선 ..
2633 백준
문제 문제 분석 티어에 비해 꽤 까다로운 문제였다. 가장 문제라고 생각했던 것은 "치즈가 없는 칸, 0이 치즈 속의 빈 공간인가 혹은 바깥과 연결된 0인가"를 판별해야 한다는것을 생각해내고 구하는 부분이었던것 같다. 그림1과 그림2만 보더라도 같은 0이라도 그림1 근처의 빈 공간의 치즈들은 녹지 않는 반면 그림 2의 빈 공간은 바깥과 연결되어있는 빈칸이기 때문에 빈칸 옆의 치즈들도 녹게 된다. 그렇다면 이 빈 공간을 판단하는 방법은 무엇일까? 점 0,0에서 시작해서 0으로만 이동하는 BFS를 통해 구하면 결국 치즈 바깥만 0으로 남아있는 치즈 그림자가 생성될것이다. 그렇다면 바깥쪽 치즈는 무엇일까? 위 아래 양 옆 중 하나라도 바깥과 연결되어 있다면 그 치즈는 바깥쪽 치즈일 것이다. 이렇게 생성된 새로운..
6588, 15711 백준
문제 문제 분석 입력 a,b에 대하여 a+b를 2개의 소수로 나눌 수 있는가?를 묻는 질문이다. 다른 쉬운 소수 문제와는 별개로 범위가 1 ≤ A, B ≤ 2 × 10^12 로 꽤 크다는 점이다. 가장 먼저 생각해본 방법은 에라토스테네스의 체를 이용하여 하나의 소수, a'를 얻고 sum - a'인 b'를 sqrt(b')까지 나눠가면서 b'가 소수인지 판별하는 방법이었다. 하지만 문제 조건에 의하면 에라토스테네스의 체를 이용해서 얻을 수 있는 범위가 그래봐야 10^8이고 그렇게 되면 b의 범위는 10^12정도가 되므로 10^4초가 걸리게 되면서 시간 초과가 날 것 같아 다른 방법을 고안하였다. 그래서 이전에 풀었던 6588번 골드바흐의 추측 문제를 떠올렸는데 이 추측에 따르면 "4보다 큰 모든 짝수들은 두..