zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
합이 target인 겹치지 않는 부분 배열 두 개를 골라서 길이의 합을 최소로 만드는 문제. 일단 arr[i] >= 1이라 전부 양수다. 그래서 합이 target인 구간은 슬라이딩 윈도우로 죽 밀면서 찾아주면 된다. 겹치지 않게 두 개를 고르는 게 문제인데, 오른쪽 구간을 고정하면 왼쪽은 제일 짧은 것 하나만 알면 된다. minLen[i]를 i 이하에서 끝…
1차원 위에 놓인 점 n개에서 서로 겹치지 않는 선분 k개를 그리는 경우의 수를 구하는 문제. 선분은 점을 둘 이상 덮어야 하고 끝점은 공유할 수 있다. modular 나온 걸 보고 딱 DP겠거니 했다. 어제 2472처럼 겹치지 않게 k개를 고르는 문제인데 이번엔 최대 개수가 아니라 경우의 수다. 한 점에서 할 수 있는 건 이어붙이기, 끊고 넘어가기, 새로…
이진 트리에서 자기 값이 서브트리 전체 값의 평균(내림)과 같은 노드의 개수를 구하는 문제. 노드마다 서브트리를 다시 돌면 O(n^2)이다. 평균을 구하려면 서브트리의 합과 개수만 있으면 되고, 둘 다 자식 값으로 바로 구할 수 있다. 즉, 후위 순회로 (합, 개수)를 올려주면 한 번만 돌아도 된다. 정답 개수도 같은 튜플에 넣어서 올려주면 따로 변수가 필…
n x n 이진 행렬 img1을 상하좌우로만 평행이동해서 img2 위에 겹쳤을 때, 둘 다 1인 칸의 최대 개수를 구하는 문제. n이 최대 30이라 평행이동을 전부 해봐도 (2n-1)^2 = 3481번이다. 그냥 다 돌려보면 된다. 처음에는 (3n-1) x (3n-1) 보드를 깔고 img1을 실제로 옮겨 그려서 셌는데 시간 초과가 났다. 이동할 때마다 보드…
1부터 n까지의 수를 세 자리마다 콤마를 찍어서 쓸 때, 콤마가 총 몇 개 쓰이는지 구하는 문제. n이 10^15까지라 하나씩 세는 건 불가능하다. 잘 생각해보면 1000 이상인 수는 콤마가 최소 1개, 10^6 이상이면 최소 2개... 이런 식이다. 즉, 1000의 거듭제곱마다 그 이상인 수의 개수를 더해주면 된다. n 이하에서 div 이상인 수는 n -…
k 길이의 부분 배열 중에 원소가 전부 다를 때의 합의 최댓값을 구하는 문제 간단한 슬라이딩 윈도우 문제. 원소 하나씩 보면서 counter 하면서 모두 distinct 이면 결과에 업데이트 해주면 된다.
루트부터 리프 노드까지를 이었을 때 생기는 수를 다 더하는 문제 재귀적으로 구현하면 된다. 자식 노드로 내려갈 때 현재 값에 10을 계속 곱해주면서 더하면 된다. 보통 재귀적으로 합을 구할 때와 순서가 반대라서 약간 헷갈리긴 한다
이진 트리가 주어질 때 레벨 별로 지그재그 하면서 출력하는 문제 레벨별로 맵을 만들고 순서에 맞게 집어넣으면 된다. 일반 bfs 탐색을 약간 변형하면 됨
ACGT로만 이루어진 gene이 둘 주어질 때 startGene 에서 endGene으로 mutate가 가능하면 최소 횟수를 출력하는 문제. mutate는 bank에 있는 문자열로만 가능하다. bank 개수 제한이 아주 여유로워서 DFS, BFS 다 가능하다. 일단 간단하게 DFS 백트래킹으로 구현했다. bank로 mutate가 가능한지 판단해서 이동하는 방…
배열에서 정렬 없이 k 번째 큰 수를 찾는 문제 정렬하면 쉽지만 안하고 풀어야 한다. quick sort를 응용한 quick select 알고리즘을 쓰면 된다. quick sort와 비슷하게 피벗을 잡고 피벗 기준으로 왼쪽은 더 큰 값들, 오른쪽에는 더 작은 값들을 몰아 넣는다. 여기서 포인트는 quick select는 정렬이 필요가 없으므로 왼쪽, 오른쪽…