룰루랄라 알고리즘

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 집에 누워있으면 진짜 안될 것 같은 위기감을 느끼고 집 앞 2분 거리 카페에 나와서 문제를 풀었다. 다이나믹 문제를 풀려고 푼 게 아니라 내가 좋아요 누른 문제집을 거의 다 풀고 2개 남아서 그중 하나를 골랐는데 풀어보니 dp였다. 이제 문제를 보기만 하면 dp가 생각이 난다 사실 문제를 풀려고 카페를 갔던 게 아니라서 펜과 종이가 없어서 그림판으로 풀었다. 작은 수를 놓고 좀만 끄적이다 보면 바로 규칙이 나온다. dp는 늘 규칙찾는 퍼즐 푸는 것 같다 1. [][0]에는 이전까지의 합을 누적해서 저장 2. [][1]에는 마지막 ..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 주말 하루종일 침대에만 있다가 죄책감이 들어 저녁 먹고 간단하게 홈트 후에 쉬운 문제를 풀어보았다. 다이나믹 프로그래밍은 예전에 문제를 많이 풀어봐서 바로 풀이법이 떠올랐다. // 0 1 2 3 4 // 0 0 00 000 // 1 1 11,01 111,001,011 // 2 2 22,02,12 222,002,022,012,112,122 // 3 3 33,03,..

일부러 DP만 푸는 게 아니라 풀어보니 DP였다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 해당 문제는 쉽게 점화식을 떠올릴 수 있는데 중복을 허락하지 않는다는 부분에서 고민이 길어졌다. 10원을 만들기 위해서는 dp[10] = dp[9] + dp[8] + dp[5] 처럼 제안된 동전의 값어치만 더하면 10원이 되는 식으로 점화식을 세울 수 있다. 하지만 이 문제는 중복을 허락하지 않는다. 예를 들어 만약 1과 2로 4를 만들어야할 때, ..

이 문제도 dp를 이용하기에 아주 좋은 문제인 것 같다. https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 전략은 dp테이블을 2차원 배열로 다음과 같이 생성하는 것! dp[자릿수][n으로 끝나는 수] 배열은 0부터 시작하기 떄문에 dp[1][2]는 자릿수가 2개인 숫자 중에 2로 끝나는 수의 개수를 의미한다. 계단 수의 특징은 0과 9로 끝나는 수는 다음 자리수에 1과 8만 올 수 있으므로 해당 케이스는 따로 처리하고, 나머지 숫자들은 자신의 수 보다 +1, -1 한 dp[i][j+1] + dp[i][j-1]로 계산한다. 또한 수의 크기가 크므로 자료형을 l..

여태 실버문제는 풀지 않았지만 코테문제는 실버에서 골드 수준으로 나온다는 걸 알게 되고 앞으로는 적극 실버를 풀 생각이다. 마침 대학교 알고리즘 시간에 분할정복, DP의 차이점과 상황에 따른 우수성을 배운지 얼마 지나지 않았어서 해당 문제를 보고 바로 DP로 풀어야 한다는 생각이 났다. 감사합니다 프로페서 조. https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 해당 문제는 이미 재귀 분할정복으로 구현되어 있는 식을 DP로 바꾸는게 풀이였다. 해당 식..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 다이나믹 프로그래밍으로 점화식을 구해서 풀어야 하는 문제. 1차원 적으로 생각했다가 도저히 답이 안 나왔는데 dp 테이블을 2차원 배열로 나누어 풀어야지 풀 수 있었다. dp[i][0] : i를 만들 때 1이 가장 앞에 오는 경우 ex) i=4 1+1+1+1 dp[i][1] : i를 만들 때 2가 가장 앞에 오는 경우 ex) 2+1, ..

https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 3차원 배열을 통해 dp 테이블을 구성하고 (N+1) X M X 3으로 출발지를 의미하는 행을 한층 더 쌓았다. 좌표 dfs 처럼 dx, dy의 범위를 제한하면서 dp 테이블을 업데이트. 아래 알고리즘의 기본 점화식 dp[nx][ny][중앙] = min( dp[x][y][왼쪽 위], dp[x][y][오른쪽 위] ) + graph[nx][ny] public c..

알고리즘은 맞았지만 생각지도 못한 이유로 시간초과에 걸려서 고생한 문제다. 다이나믹 프로그래밍을 이용해 누적합을 저장하는 dp 테이블을 생성하고 그 테이블을 이용해 Time Complexity를 줄이는 문제. 처음 문제를 보고 익숙한 누적 합 문제라 바로 dp 테이블을 만들고 문제를 풀었는데 아뿔싸 시간초과가 났다. 내가 푼 방식은 dp 테이블을 열 기준으로 한 줄씩 생성하는 것이다. 아무리 머리를 굴려도 내가 푼 방식보다 더 빠르게 동작하는 방법이 생각나지 않아 해답을 찾아봤는데 나랑 알고리즘이 똑같았다. 다른 점이 하나 있었는데 나는 반복문이 돌 때마다 System.out.print를 하면서 답을 출력했는데 풀이에는 StringBuilder sb에 답을 저장해 놓고 마지막에 sb를 출력하는 형식이었다..

진짜 평범한 배낭 문제 중에 한 문제다. 이 문제에서 N의 범위가 20으로 비교적 작은 범위로 제한되어 있어 ArrayList를 사용하지 않고 크기가 22인 배열을 사용해 문제를 풀 수 도 있었지만 그냥 가변배열을 사용하고 싶어서 ArrayList를 선택했다. 배낭 문제에서 [물품의 수 = 사람의 수] 로, [견딜 수 있는 무게 = 체력] 으로 변환하면 쉽게 풀 수 있다. 2차원 배열 선언하는 게 갑자기 생각이 안 나서 헷갈렸다. 행과 열의 구분을 헷갈리지 않도록 확실하게 기억해야 할 필요가 있을 듯 https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순..

개수를 구하는 코드는 LCS1 문제에 있으므로 그 부분은 생략한다. 다른 사람의 풀이를 보고 내 방식 대로 풀었다. 다른 사람의 풀이를 보지 않았다면 못 풀었을 것 같다. 역 추적으로 구하는 방식인데 아래 그림처럼 처음으로 숫자가 +1 되었을 때를 기준으로 문자열을 저장했다. 처음으로 +1이 되었다는것을 판별 할 때는 아래와 같은 규칙이 있다. 1. 자기 자신의 위나 왼쪽 중에 같은 숫자가 있다면 인덱스를 그 위치로 바꾼다. 2. 자기 자신의 위나 왼쪽 중에 더이상 같은 숫자가 없다면 대각선에 위치한 인덱스로 위치를 바꾼다. 3. 대각선으로 위치를 바꾸기 직전의 인덱스가 처음으로 +1이 된 위치다. DP의 값이 0 이되면 추적을 멈춘다.