파게로그

문제 링크: 17413번 단어 뒤집기 2 https://www.acmicpc.net/problem/17413 문제에서 시키는 대로 한다. string1은 입력 문자열이고, string2는 입력 문자열이며 idx1은 string1에 대한 인덱스이고, idx2는 string2에 대한 인덱스이다. 다른 것보다 인덱스를 일관되게 유지한는 것이 중요하다. 즉 예를 들어서 idx2가 마지막 문자의 위치를 가리키고 있는지, 또는 새로운 문자가 삽입될 위치를 가리키고 있는지를 섞어서 사용하면 안 되는 것이다. plain text, 즉 공백 사이에 있거나 문장의 처음이나 마지막에 있으며 태그가 아닌 '단어'의 경우 start와 end 인덱스를 별도로 설정해 단어의 시작과 끝을 알아낸다. 그 후 다시 끝에서부터 시작까지 ..

문제 링크: 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..

소개 index란... 파일에 있는 레코드를 찾아주는 보조적인 파일. - 색인은 정렬되어 있음 - 검색을 빨리 하도록 도와줌 - 자료 파일에 비해 상대적으로 양이 적음 순서 구조의 인덱스 - 인덱스 필드와 주소 값으로 구성된 엔트리들의 모임 - 초기 기본적인 색인 기법을 다단계로 이용하여 ISAM(Indexed Sequential Access Method)이라는 색인 순차 파일이 보급됨 ISAM은 정적. 자료의 추가와 삭제에 따라서 색인 구조가 증대하고 수축하는 동적인 색인인 B-tree 색인 해싱 구조의 인덱스 - 키 값에 의하여 레코드의 위치를 직접 찾아주는 기법 ------ 색인의 형태 색인의 분류 기본 색인 vs 보조 색인 vs 클러스터링 색인 primary index(기본 색인): 기본 키로 검..

문제 링크: 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의 공은 먹을..