zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
어떤 문자를 담으면 그 문자가 나오는 모든 위치를 담아야 한다는 조건 아래, 겹치지 않는 부분 문자열을 최대 개수로 고르는 문제. 일단 알파벳별로 first, last 인덱스를 뽑아둔다. 시작점 후보는 각 알파벳의 first, 26개뿐이다. 거기서 오른쪽으로 훑으면서 보이는 문자의 last로 end를 늘려주면 된다. 대신 중간에 first[cc] < sta…
문자열 s에서 길이가 k 이상인 팰린드롬 부분 문자열을 서로 겹치지 않게 최대 몇 개 고를 수 있는지 구하는 문제. 딱 보니 DP라서 처음에는 top-down으로 풀었다. 팰린드롬 판별도 isPalindrome(l, r)로 DP를 두면 전체가 O(n^2)이 된다. 처음엔 너무 편하게 둘 다 @cache를 붙였다가 메모리 초과가 났다... isPalindro…
구간마다 가중치가 있을 때, 서로 겹치지 않는 구간을 최대 4개까지 골라 가중치 합을 최대로 만드는 문제. 합이 같으면 인덱스 배열이 사전순으로 가장 작은 것을 반환해야 한다. 가중치 있는 구간 스케줄링에 조건이 두 개 붙은 문제. 일단 끝점 기준으로 정렬하면 어떤 구간과 안 겹치는 구간들은 항상 앞쪽에 몰려 있다. 그래서 이분 탐색으로 경계만 찾으면 DP…
한 문자를 죽 이어 붙이거나 특정 범위의 문자열을 교체하는 2가지 연산을 할 때 최소한의 연산으로 문자열을 만드는 횟수를 찾는 문제. 약간 분할 정복, 완전탐색 느낌이 나는데 쉽지 않다. 일단 양옆이 같은 문자인 경우 중간을 바꿔치기 했다고 생각할 수 있다. 그 외의 경우는 이어 붙여야 한다. 따라서 문제를 나눠볼 수 있는데 맨 앞과 같은 문자가 중간에 나…
배열 중에서 pair의 차이가 k번째로 작은 값을 찾는 문제 대충 감으로 이진 탐색으로 찾아야할 것 같다. 그런데 어떻게 n보다 작은 pair 개수를 셀 수 있을까? 슬라이딩 윈도우로 셀 수 있다. 먼저 배열을 정렬해주자. 그 후 n보다 작은 pair의 개수를 세는 함수를 정의하고 n을 이진 탐색으로 돌면서 k개가 나올 때까지 탐색해주면 된다. n보다 작은…
2d 배열로 맵이 주어진다. 0은 바다, 1은 육지. 1을 0으로 바꿔서 섬이 2개로 나눌 수 있는 최소 횟수를 구하는 문제. 엄청 어려워 보이는데 간단하게 풀 수 있는 방법이 있다. 답은 무조건 0, 1, 2 중 하나이다. 일단 0, 1은 그럴 수 있는데 왜 2번만에 모든 섬을 2개로 나눌 수 있을까? 섬이 어떻게 생겼든 꼭지점을 나눠서 섬을 2개로 만들…
배열의 크기와 행과 열에서의 원소들의 순서가 주어질 때 순서에 맞게 배열을 만드는 문제. 간단한 위상정렬 문제. 원소들의 순서를 그래프로 보면 원소들의 놓는 순서는 위상 정렬로 쉽게 얻어낼 수 있다. 얻어낸 행와 열의 순서대로 배치하면 된다. 불가능한 경우, 사이클이 있다면 빈 배열을 리턴하면 된다.
숫자를 영어로 변환하는 문제. 문제는 매우 쉽지만 아주 지저분하다. 1000씩 끊고 10씩 끊는 등 숫자를 잘게 나누면 그나마 덜 지저분하게 짤 수 있다. 오타 조심..! (Ninety 잘못 쳐서 1번 틀림..)
풍선을 터뜨릴 때 최대 점수를 구하는 문제. 터뜨릴 때는 풍선의 양쪽과 현재 값을 곱한 값이 점수가 된다. 딱 보면 해답이 나오지 않는 DP 문제. 문제를 반대로 생각해봐야 한다. 일단 문제 그대로는 이전 선택이 이후 선택에 영향을 주기 때문에 DP를 적용하기 어렵다. 다만, 풍선을 먼저 터뜨릴 것을 고르는 것이 아니고 마지막에 터뜨릴 것을 고른다고 생각하…
세탁기에 옷들이 있고 옷들을 한번에 하나씩 이동시킬 수 있을 때 모든 옷의 개수가 같게 만드는 최소 이동 횟수를 구하는 문제. 일단 전체 합이 개수의 배수가 되어야 하니 먼저 예외 처리를 해주고, 모든 세탁기의 옷은 합 / 개수가 되어야 한다. 여기서 간단하게 드는 생각은 가장 큰 값 - (합 / 개수) 하면 답일까? 싶은데 반례가 존재한다. [0,0,2,…