zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
1을 임의의 0과 swap해서 1이 연속되게 만드는 문제. 단, 배열은 원형이다 한 덩어리로 만든다고 생각해보면 1이 나온 개수만큼 어딘가에 뭉쳐놓는다고 볼 수 있다. 그렇게 되면 슬라이딩 윈도우 방법으로 1이 나온 개수 크기의 윈도우로 배열을 순회하면서 그 윈도우 안의 0의 개수가 swap 횟수가 된다. 원형 처리는 간단하게 배열을 그냥 뒤에 그대로 붙여…
모든 subarray의 합을 정렬한 후 left부터 right 까지 합을 구하는 문제 그냥 문제 그대로 모든 subarray에 대해 합을 구한 후 정렬하면 된다. 당연하게도 합을 구할 때는 prefix sum으로 구해야 시간 안에 들어온다. 시간 복잡도는 정렬 때문에 O(n^2 log(n^2)) sliding window, binary search를 쓰면 …
책을 책장에 꽂아 넣을 때 높이가 최소가 되도록 꽂는 문제. DP 문제이다. 책을 꽂는 방식이 2가지가 있고 현재 shelf에 꽂을지 혹은 다음 shelf로 꽂을지 선택할 수 있다. 책의 너비가 전체 shelf 보다 크지 않으면 한 shelf로 다 꽂을 수 있다. 로 두고, 한 줄에 꽂을 수 있을 때까지 꽂으면서 top-down dp로 구현하면 된다.
a 또는 b를 최소한으로 지워서 문자열을 /a*b*/ 형태로 만드는 횟수를 구하는 문제. 기준점을 두고 그리디하게 왼쪽의 b를 지우고 오른쪽의 a를 지웠을 때 횟수의 합 중 최소를 구하면 된다. 마지막에 1 빼주는건 현재 위치가 중복으로 들어가서 그냥 빼주었다. (현재 위치도 카운트에 집어넣었기 때문) 또한, 배열을 안쓰고 count 변수 2개로도 풀 수 …
연속으로 작아지거나 커지는 3 크기의 부분 배열을 구하는 문제. 브루트 포스는 O(n^3)으로 불가. 약간 스마트한 브루트 포스로 풀린다. O(n^2) 배열의 크기가 3이므로 중간을 기준으로 왼쪽은 더 작은 값, 오른쪽은 더 큰 값을 고르면 된다. 비슷하게 중간을 기준으로 왼쪽은 더 큰 값, 오른쪽은 더 작은 값을 갖는 배열의 개수를 구해서 더하면 정답이 …
정렬 구현 문제 뭐 별거 없고 그냥 정렬을 구현하면 된다. nlogn 정렬들 중 아무거나 구현하면 되는데 제일 간단하면서 안정적인 merge sort를 구현하였다. 퀵 소트, 힙 소트 등 기억이 잘 안나네 ㅋㅋ
배열에서 중복된 수를 찾는 문제. 단 배열의 조작은 불가능하고, 공간복잡도는 O(1)이어야 한다. 제약 조건이 없다면 매우 쉬운 문제... 하지만 제약 조건과 follow up을 전부 만족하려면 특별한 알고리즘이 필요하다. 일단 해당 문제를 링크드 리스트로 볼 수 있는데 nums의 값을 인덱스로 해서 다음 리스트로 넘어가는 링크드 리스트로 가정하면 링크드 …
구간들이 주어질 때 새로운 구간을 추가하는 문제. 구간들은 겹칠 경우 머지되어야 한다. 약간 그리디 느낌? 겹치지 않은 경우는 그냥 결과 배열에 넣으면 되고 겹치는 경우는 left는 겹치는 구간들의 최소, right는 겹치는 구간들의 최대로 해서 추가하면 된다. 좀 지저분하게 짜긴 했지만 결과도 맞게 나오고 O(n)이라 별 상관 없다.
풍선의 x 좌표 구간이 주어질 때 수직으로 화살을 쏴서 전부 터뜨릴 수 있는 최소한의 화살 개수를 구하는 문제. 그리디로 풀면 된다. 먼저 정렬부터 해주자. 그런 다음 화살을 발사할 범위를 계속 계산하면서 가능한지 판단하면 된다. 좀 더 자세히 설명하면 겹치는 풍선의 범위를 계속 계산해나가면 된다. 풍선의 오른쪽 좌표의 최소값, minRight를 계속 갱신…
배열에서 0과 1의 숫자가 같이 나오는 부분 배열을 구하는 문제 지금까지 0과 1이 나온 카운트를 트래킹 해주면서 같은 카운트가 나왔다면 그때 0과 1이 같은 개수로 나온 배열이 된다. 말로 하니 어려운데 에디토리얼 그림을 보면 이해하기 쉽다. [0 0 1 0 0 0 1 1] 에 대한 카운트에 따른 그림이고 A, B, C 지점을 찍었을 때 해당 구간은 0과…