zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
1차원 위에 놓인 점 n개에서 서로 겹치지 않는 선분 k개를 그리는 경우의 수를 구하는 문제. 선분은 점을 둘 이상 덮어야 하고 끝점은 공유할 수 있다. modular 나온 걸 보고 딱 DP겠거니 했다. 어제 2472처럼 겹치지 않게 k개를 고르는 문제인데 이번엔 최대 개수가 아니라 경우의 수다. 한 점에서 할 수 있는 건 이어붙이기, 끊고 넘어가기, 새로…
문자열 s에서 길이가 k 이상인 팰린드롬 부분 문자열을 서로 겹치지 않게 최대 몇 개 고를 수 있는지 구하는 문제. 딱 보니 DP라서 처음에는 top-down으로 풀었다. 팰린드롬 판별도 isPalindrome(l, r)로 DP를 두면 전체가 O(n^2)이 된다. 처음엔 너무 편하게 둘 다 @cache를 붙였다가 메모리 초과가 났다... isPalindro…
축에 평행한 직사각형 두 개가 주어질 때, 교집합의 넓이가 양수인지 판단하는 문제. 변이나 꼭짓점만 닿는 것은 겹치지 않는 것으로 본다. easy지만 생각보다 easy하지 않은 문제. 처음엔 한쪽의 끝점이나 꼭짓점이 상대 직사각형 안에 들어가는지로 판단하려 했다. 그런데 한쪽이 다른 쪽을 품는 경우나 십자 모양으로 겹치는 경우를 놓치고, 경계 처리도 계속 …
이진 트리에서 자기 값이 서브트리 전체 값의 평균(내림)과 같은 노드의 개수를 구하는 문제. 노드마다 서브트리를 다시 돌면 O(n^2)이다. 평균을 구하려면 서브트리의 합과 개수만 있으면 되고, 둘 다 자식 값으로 바로 구할 수 있다. 즉, 후위 순회로 (합, 개수)를 올려주면 한 번만 돌아도 된다. 정답 개수도 같은 튜플에 넣어서 올려주면 따로 변수가 필…
n x n 이진 행렬 img1을 상하좌우로만 평행이동해서 img2 위에 겹쳤을 때, 둘 다 1인 칸의 최대 개수를 구하는 문제. n이 최대 30이라 평행이동을 전부 해봐도 (2n-1)^2 = 3481번이다. 그냥 다 돌려보면 된다. 처음에는 (3n-1) x (3n-1) 보드를 깔고 img1을 실제로 옮겨 그려서 셌는데 시간 초과가 났다. 이동할 때마다 보드…
구간마다 가중치가 있을 때, 서로 겹치지 않는 구간을 최대 4개까지 골라 가중치 합을 최대로 만드는 문제. 합이 같으면 인덱스 배열이 사전순으로 가장 작은 것을 반환해야 한다. 가중치 있는 구간 스케줄링에 조건이 두 개 붙은 문제. 일단 끝점 기준으로 정렬하면 어떤 구간과 안 겹치는 구간들은 항상 앞쪽에 몰려 있다. 그래서 이분 탐색으로 경계만 찾으면 DP…
1부터 n까지의 수를 세 자리마다 콤마를 찍어서 쓸 때, 콤마가 총 몇 개 쓰이는지 구하는 문제. n이 10^15까지라 하나씩 세는 건 불가능하다. 잘 생각해보면 1000 이상인 수는 콤마가 최소 1개, 10^6 이상이면 최소 2개... 이런 식이다. 즉, 1000의 거듭제곱마다 그 이상인 수의 개수를 더해주면 된다. n 이하에서 div 이상인 수는 n -…
k 길이의 부분 배열 중에 원소가 전부 다를 때의 합의 최댓값을 구하는 문제 간단한 슬라이딩 윈도우 문제. 원소 하나씩 보면서 counter 하면서 모두 distinct 이면 결과에 업데이트 해주면 된다.
루트부터 리프 노드까지를 이었을 때 생기는 수를 다 더하는 문제 재귀적으로 구현하면 된다. 자식 노드로 내려갈 때 현재 값에 10을 계속 곱해주면서 더하면 된다. 보통 재귀적으로 합을 구할 때와 순서가 반대라서 약간 헷갈리긴 한다
이진 트리가 주어질 때 레벨 별로 지그재그 하면서 출력하는 문제 레벨별로 맵을 만들고 순서에 맞게 집어넣으면 된다. 일반 bfs 탐색을 약간 변형하면 됨