파게로그

문제 링크: 12015번 가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 먼저 lower bound에 대해 알아야 한다. lower bound는 처음으로 나온 key보다 큰 수의 위치를 말한다. 이는 이분탐색 과정을 조금만 응용하면 된다. static int lowerBound(ArrayList list, int target) { int left = 0; int right = list.size(); int mid; while (left = target) right = mid-1; else left = mid+1; } return left; } 배열이 아닌 리스트로 구현해 두어서 좀 보기 불편하긴 하지만... 언젠가 left > right이 성립할 때, ..

문제 링크: 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 dp[i]는 arr[0~i]에서 가장 긴 증가하는 부분 수열(LIS)의 길이를 저장한다. 그렇다면 이 dp[n]을 어떻게 갱신하느냐가 관건인데, O(n^2)의 알고리즘은 그다지 어렵지 않다. dp[n]을 구할 때, j는 0부터 n-1까지 탐색하면서 arr[i]와 arr[j]를 비교한다. 이 때 arr[i]가 더 크다면, dp[i] 즉 arr[0~i]에서 LIS의 길이는 dp[j]보다 최소한 1만큼은 더 크다. 왜냐하면 arr[i]는 arr[0~j]의 모든 수보다 더 크기 때문에 arr[0~j]에서의 LIS의 맨 마지막 원소에 arr[i]가 덧붙을 수 있는 것이다. 하지만 이는 '최소한..

문제 링크: 17298번 오큰수 https://www.acmicpc.net/problem/17298 프로그래머스 레벨 2였나... 주식 가격 문제와 비슷하다. 수열의 원소들을 쭉 받아주면서, 해당 숫자의 인덱스와 함께 묶어 스택에 push한다. 그리고 스택의 top에 있는 숫자보다 새로 받은 숫자가 더 크면, 더 작은 숫자가 나올때까지 스택을 pop해나가면서 각 인덱스에 새로 받은 숫자를 채워준다. 이런 과정을 반복했을 때 남은 숫자는 자신보다 더 큰 숫자를 만나지 못한 숫자들이므로, 스택에 남아있는 모든 아이템을 확인하면서 해당 인덱스의 자리에 -1을 채워준다. import java.io.BufferedReader; import java.io.IOException; import java.io.Input..

문제 링크: 1074번 Z https://www.acmicpc.net/problem/1074 Z를 그리되, 0부터 원하는 위치까지 모두 일일이 그린다면 시간 초과로 이 문제를 풀 수 없다. 따라서 분할 정복 기법을 활용하여 몇 번 사각형에 속하는지 확인하는 방식을 취한다. solution()에서의 n은 변의 길이이고, start는 사각형의 좌상단 숫자이므로 가장 처음에 n에는 2^N를, start에는 0을 넣어준다. 그리고 r, c를 통해서 1, 2, 3, 4번 사각형 중 어디에 속하는지를 판단하고 해당 사각형에 대해 solution()을 호출한다. 다만 r과 c는 최초의 사각형을 기준으로 하고 있기에, 분할된 사각형을 기준으로 갱신되어야 하는데, 행 또는 열, 또는 행과 열 모두에서 n/2를 빼줌으로써..

문제 링크: 2470번 두 용액 https://www.acmicpc.net/problem/2470 head와 tail이 각각 하나의 값들을 가리키고 있을 때, 두 값의 합 cur이 0에 가까워지고자 한다면, cur 0일 때는 cur을 왼쪽으로 옮겨준다. 계속해서 그 차이 diff를 확인하면서, 차이가 갱신될 때마다 head와 tail이 가리키는 값을 저장해준다. 물론 이러한 매커니즘이 동작하려면 배열이 가장 먼저 정렬되어 있어야 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; im..

문제 링크: 10800번 컬러볼 https://www.acmicpc.net/problem/10800 공을 먼저 크기에 따른 순서대로 정렬한다. 다음과 같은 예시가 있다고 생각해보자. 정렬후 인덱스 idx 0 1 2 3 4 5 6 7 8 size 2 3 4 10 11 12 15 16 17 color 3 2 1 2 2 1 2 3 1 sum 0 2 5 9 19 30 42 57 73 csum[1] 0 0 0 4 4 csum[2] 0 0 3 3 13 csum[3] 0 2 2 2 2 예를 들어, size가 11인 공의 경우 1. size를 고려한다면, 자신보다 앞에 있는 모든 공을 먹을 수 있다. -> sum[4] = 19 2. color를 고려한다면, 자신보다 앞에 있는 모든 공 중 동일한 color의 공은 먹을..

문제 링크: 17825번 주사위 윷놀이 https://www.acmicpc.net/problem/17825 채점 현황을 보니 최적화된 코드에 비해 시간은 2배, 메모리는 5배 정도 더 잡아먹는 것 같다. 많은 개선이 필요해 보인다. move(): 하나의 horse 배열이 완성되었을 때, 점수를 구한다. board: board[i][j] = k이면 '출발지에서 도착지로 가는 4개의 경로 중 i번째 경로'의 'j 위치'에 '쓰인 숫자'는 k이다. horse: horse[i] = k이면 'i번째 주사위'에는 '말 k'를 움직인다. pos[i] = k이면 '말 i'의 위치는 k이다. score[i] = k이면 '말 i'의 점수는 k이다. path[i] = k이면 '말 i'는 '출발지에서 도착지로 가는 4개의 경..

문제 링크: 16235번 나무 재테크 https://www.acmicpc.net/problem/16235 전형적인 시뮬레이션 문제로서, 주어진 조건을 얼마나 꼼꼼하게 구현해내느냐가 중요하다. 웬일로 다른 풀이에 비해 메모리를 적게 사용하는 양질의 풀이를 뽑아냈는데, 아마 클래스를 정의하지 않고 ArrayList의 2차원 배열로서만 나무를 표현했던 것이 주요한 것 같다(컴파일러가 경고를 주는데, 검색해보아도 이를 해결할 수 있는 방법이 없다고 하는 것 같다...). import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.uti..