Java/Algorithms

문제 접근 방식 강의에서 설명해 주기 전까진 DP 문제일 줄은 생각도 못하고 있던 문제다... 일단 위와 같은 타일을 채워야 할 때 가장 위의 칸부터 채우는 경우를 살펴 보면 2*1 타일은 이렇게 하나를 둘 수 있는데 그러면 정확히 2*(n-1) 칸이 남게 된다. 1*2 타일의 경우에는 어차피 한 층에 1*2 타일을 쌓으면 다른 한 층도 무조건 1*2 타일을 쌓을 수밖에 없으니 2*(n-2) 칸이 남게 된다. 결국 이 한 칸에 올 수 있는 경우의 수는 (n-1) + (n-2)에 해당한다. 눈치가 빠른 사람은 이 공식을 어디서 많이 봤다고 생각할 수도 있는데 피보나치수열과 똑같은 공식이다. 이제 문제를 풀 수 있는 식은 구했으니 DP 테이블을 만들어야 하는데 간단하게 i일 때 경우의 수를 저장할 DP [N..

문제 접근 방식 백트래킹이나 다중반복문으로도 풀 수 있는 문제지만 시간제한을 보면 그렇게는 풀 수 없는 문제들이라 DP를 사용해서 풀었다. 1 ~ N번 집까지 있을 때, N번 집을 가장 적은 비용으로 칠할 수 있는 경우는 N-1번째 집을 칠한 경우 중 가장 적은 비용 + 현재 칠할 수 있는 색깔이다. RGB 264083 496057 138999 위와 같이 3개의 집과 각 집을 칠하는 색깔별 비용이 주어졌을 때를 살펴보면 26 -> 60 OR 57 -> 13 OR 99 / 13 OR 89 40 -> 49 OR 57 -> 89 OR 99 / 13 OR 89 83 -> 49 OR 60 -> 89 OR 99 / 13 OR 99 이전 집을 칠한 색깔을 제외한 각각의 색깔들 별로 칠할 수 있다. DP 테이블을 각 ..

문제 접근 방식 길이가 N인 수열에서 같은 숫자끼리는 최대 K번까지만 사용한 부분 수열을 구해야 한다. 각 숫자들마다 등장 횟수를 기록해야하기 때문에 불리언 배열이 아닌 정수형 배열에 특정 숫자가 등장 할 때마다 해당 인덱스에 카운트를 증가시키면서 투 포인터로 탐색을 하다가 특정 숫자가 K번 이미 등장 했을 때 또 등장했다면 만들 수 있는 부분 수열의 끝이므로 현재 부분 수열의 길이를 구한 후에 현재 까지 가장 긴 부분 수열의 길이인지 비교하고 값을 바꿔주면 된다. 풀이 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStre..

문제 접근 방식 k개의 초밥을 연속으로 먹었을 때 가장 다양한 종류의 초밥을 먹을 수 있는 경우를 구해야 하는 문제로 초밥을 k개 먹었을 때 중복 되지 않은 초밥이 몇 개인지를 찾으면 된다. 탐색은 이전의 투포인터 문제들과 마찬가지로 배열의 첫 인덱스를 기준으로 k개의 초밥을 먹을 때까지 탐색을 하고, 시작 인덱스를 1 증가시켜주면 된다. // 연속으로 먹은 횟수 // 회전 벨트의 초밥 목록 1234k 7973027925 1234k 7973027925 1234k 7973027925 1234k 7973027925 1234k 7973027925 4k123 7973027925 34k12 7973027925 234k1 7973027925 탐색의 진행 과정은 위와 같다. 불리언 배열을 이용해 이미 등장한 초밥이라..

문제 접근 방식 숫자를 k번만 삭제해서 짝수로만 이루어진 부분 수열 중 가장 긴 부분 수열의 길이를 구해야 한다. 첫 숫자부터 시작 포인트로 정하고 나머지 하나의 포인터를 사용해 다음 숫자들을 탐색해나가면 된다. {1, 2, 3, 4, 5, 6, 7, 8} 예를 들어 위와 같은 수열이 주어졌고, 2번만 삭제할 수 있다면 짝수만 남겨야하니 홀수를 만날 때만 삭제해주고 다음에 홀수를 만났을 때 더이상 삭제할 기회가 남아있지 않다면 현재 까지 수열의 길이를 계산해주면 된다. (현재 까지 수열의 길이 = 끝 포인터 - 시작 포인터 - 삭제한 홀수의 갯수) // 남은 삭제 기회 // 숫자 1100x 12345 21100x 234567 1100x 34567 21100 45678 순서를 살펴보면 위와 같다. 풀이 p..

문제 접근 방식 분명 이전 투포인터 문제들과 비슷한 문제라 쉽게 풀 수 있을거라 생각했는데 반환값의 범위를 잘못 생각해서 맞왜틀을 시전하느라 시간을 날려먹었다. 수열이 수의 범위가 1 ~ 100,000까지인 10만개의 수들로 이루어져 있어서 결과가 인트형으로 될줄 알았는데 혹시 싶어 long으로 바꿔보니 맞았다... (왜 10만 * 10만을 10억으로 생각하고 있었지...새벽이라 정신줄을 놓고 했나보다) {1, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 2, 1} 위와 같은 수열이 주어졌을 때 중복되지 않는 수로만 이루어지는 경우를 살펴보자 {1, 2, 3, 2, 1, 1, 2, 3, 2, 1, 1, 2, 3, 2, 1} // i[0] 1, 12, 123 // i[1] 2, 23 /..

문제 접근 방식 주어진 수 n까지의 소수를 모두 구한 후에 투 포인터를 사용해 첫 번째 소수부터 기준으로 합이 n과 같거나 커질 때까지 수들을 합해주고 합이 n과 같은 경우에는 카운트를 1 증가시켜 주면서 현재 기준점이 끝날 때마다 합에서 현재 값을 빼준 후에 다음 기준점으로 넘어가면서 계산해 주면 된다. a = {2 3 5 7 11 13 17 23 29 31 37 41} n이 41일 때를 예로 들면, 2 ~ 41까지의 소수는 위와 같다. suma[i]count 221 532 1053 1774 28115 41136v 39-25 56176x 53-35 48-54 41-73v 30-112 53233x 40-132 69293x 52-172x 29-231 60312x 31-291 68372x 37-311 784..

문제 접근 방식 주어진 수들의 부분 수열의 합이 S 이상인 것 중에 가장 길이가 짧은 부분 수열을 찾아야 하는 문제로 이분 탐색이나 투 포인터를 사용해 풀 수 있는데 투 포인터를 연습 중이기 때문에 투 포인터를 사용해서 풀었다. 이전 글에서 풀었던 2230번 문제와 비슷한 문제라 풀기는 쉬웠는데 정렬을 해야 하는줄 알고 하고 풀다가 맞왜틀을 시전하느라 시간을 날렸다. a = {5 1 3 5 10 7 4 9 2 8} / 15 suma[i]count 551 612 933 1454 24105v 19-54v 18-13v 15-32o 위와 같이 10개의 수가 주어지고, 부분 수열의 합이 15이상인 경우를 살펴보면 시작 점을 0, 비교할 인덱스는 1부터 시작했을 때, 합이 15 이상이 될 때까지 더하다 15 미만이..