zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
구간마다 가중치가 있을 때, 서로 겹치지 않는 구간을 최대 4개까지 골라 가중치 합을 최대로 만드는 문제. 합이 같으면 인덱스 배열이 사전순으로 가장 작은 것을 반환해야 한다. 가중치 있는 구간 스케줄링에 조건이 두 개 붙은 문제. 일단 끝점 기준으로 정렬하면 어떤 구간과 안 겹치는 구간들은 항상 앞쪽에 몰려 있다. 그래서 이분 탐색으로 경계만 찾으면 DP…
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는 정렬이 필요가 없으므로 왼쪽, 오른쪽…
unix path가 주어질 때 간단화 하는 문제. 즉, 여러 슬래시나 .. 같은 디렉토리 변경 등을 다 처리후 최소화된 경로로 만드는 문제. 스택을 쓰면 되는 간단한 문제. 먼저 슬래시 기준으로 split을 해준다. 일반적인 ., .. 같은 디렉토리 명렁어가 아닌 경우 스택에 넣어주고, ..의 경우에는 스택에서 빼주면 된다. 비어있는 문자열은 연속된 슬래시…
문자열이 주어질 때 적당히 잘라서 모든 substring이 팰린드롬이 되게 배열을 반환하는 문제. 백트래킹으로 하면 간단하다. 애초에 모든 substring 경우의 수를 반환해야 해서 다 탐색할 수밖에 없다. 다만 그냥 하면 중복되는 substring 체크가 많기 때문에 dp를 섞어주면 빠르게 뽑을 수 있다. 시간 복잡도는 O(2^N * N) 공간 복잡도는…
배열이 주어질 때 가장 긴 원소들의 연속 증가 길이를 구하는 문제 (순서는 상관 없음) O(n log n) 풀이는 정렬하면 되니까 쉽다. **O(n)**은 약간 생각해야 함. 일단 O(n)이니까 hashmap 방식으로 가야하고 hashmap으로 구현하려면 각 원소들을 한 번씩만 순회해야 한다. 원소들을 set에 넣어두고 set의 처음 지점인 원소부터 쭉 올…