끈기 있는 개발 공간

https://school.programmers.co.kr/learn/courses/30/lessons/1843접근주어진 배열 arr 에서 괄호를 묶을 수 있는 모든 조합 중에 계산 결과가 최대가 되는 경우를 찾아야 하는 문제다.arr 의 길이가 $3\leq{...}\leq{201}$ 이므로 완전 탐색은 할 수 없다.연산의 중요한 특징은 연산의 결과를 재사용해서 다른 결과를 만들 수 있다는 것이다.즉, 다이나믹 프로그래밍(Dynamic Programming)의 요건 중 Optimal Substructure를 만족한다.문제의 정답을 작은 문제에서 구할 수 있기 때문이다.그렇다면 이 문제를 작은 문제로 쪼갤 수 있는지(Overlapping Subproblem)를 검증하는 과정을 거쳐야 한다.$1-3+5-8$..

https://school.programmers.co.kr/learn/courses/30/lessons/68937접근그래프 탐색 문제이므로 DFS나 BFS를 사용한다.n의 범위가 $3\leq{…}\leq{250,000}$ 이므로 그래프 탐색에서 $O(1)$의 추가적인 탐색만 허용한다.이 문제는 DFS로는 해결할 수 없다.이 문제의 핵심은 말단 노드로부터 탐색(말단 노드가 루트 노드가 되어 탐색)했을 때,새로운 말단 노드까지 이동한 거리만큼이 두 점 사이의 거리가 되는 데 있다.또한, 이 문제의 특징은 f의 매개변수의 개수가 3개라는 것이다.루트 노드로부터 깊이가 제일 큰 상위 3개 노드의 이동 거리만 알면 된다.따라서, 깊이 우선 탐색(DFS)를 진행하면 깊이를 우선을 탐색해루트 노드로부터 각 노드까지의..

https://school.programmers.co.kr/learn/courses/30/lessons/67260접근문제가 좀 긴데… 요약하면 노드 탐색 중에 주어진 방문 순서를 만족하면서 모두 탐색할 수 있는지를 확인하는 문제이다.그래프 완전탐색이기 때문에 DFS 혹은 BFS로 문제에 접근하면 된다. 나는 BFS 알고리즘을 사용했다.후수가 선수보다 먼저 나오는 경우에는 탐색 불가능한 경우로 보고, 이후 선수가 나오게 될 때 탐색 가능한 경우로 본다.즉, 노드에 방문할 때마다 선수를 확인하는 과정과 후수를 확인하는 과정이 연속적으로 이루어져야 한다.마지막으로, 이 과정에 따라 전체 노드를 탐색했다면 이는 가능한 경우로 탐험 가능한 경우로 보고, 아니면 불가능한 경우로 본다.소스코드(Java)import ..

https://school.programmers.co.kr/learn/courses/30/lessons/12984접근land의 각 원소는 $0\leq{…}\leq{1,000,000,000}$의 정수이므로, 각 층별로 뭘 해보겠다는 생각은 접어야 한다.처음엔 추가하는 비용과 제거하는 비용이 가까워질수록 총 비용이 작아질 거라 생각했다.하지만, 그렇지 않다. 예를 들어, $N=7$의 다음과 같은 land 배열이 주어진다고 가정해보자. 그리고 $P=10$, $Q=10$이다.land = [ [1000000000, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0, 1], [1, 0, 1, 0, 1, 0..

https://school.programmers.co.kr/learn/courses/30/lessons/42894접근블록의 모양이 12가지이다. 이 중에 지울 수 있는 블록의 모양은 5개뿐이다.또한, 그 블록을 만들기 위해 필요한 1x1 크기의 블록의 갯수는 4개이다.이를 고려하면, 각 블록의 검사 기준 위치에서 지울 수 있는 5개의 블록을 모두 검사하면 문제를 해결할 수 있다.검사 기준 위치는 각 블록의 최상단 최우측이다. 내가 블록을 좌측에서 우측으로 움직일 것이기 때문이다.이 검사 기준 위치를 기반으로 검사 배열을 정의한다.검사 배열은 검사 기준 위치에서 검사하려는 블록의 모든 1x1 블록에 접근하게 할 수 있는 변화량이다.나는 좌측에서 우측으로 하나씩 1x1 크기의 검은 블록을 떨어트릴 것이다.그..

https://school.programmers.co.kr/learn/courses/30/lessons/12983접근이 문제는 완전 탐색으로 해결할 수 없다.strs 배열의 길이가 $1\leq{…}\leq{100}$ 이기 때문에, 순열을 계산하면 시간이 초과될 것이기 때문이다.t의 길이 제한이 $1\leq{…}\leq{20,000}$ 이기 때문에 DP만 잘 정의하면,t의 어느 자릿수까지를 만드는 데 필요한 최소 조각수를 구할 수 있다.따라서, memoization을 위한 배열 dp를 i 길이의 문자열을 만드는 데 필요한 최소 조각 수로 정의한다.소스코드(Java)class Solution { public int solution(String[] strs, String t) { int[] ..

https://school.programmers.co.kr/learn/courses/30/lessons/60060접근이 문제를 보자마자 딱 들었던 생각이 Trie 자료구조를 사용해야겠다는 것이었다.마침 얼마 전 Trie 자료구조를 알게 된 문제가 있어 관련 포스팅을 작성했었다.Trie 자료구조에 대해 궁금하면 다음 글을 읽어보면 도움이 될 것이다.[Algorithm] 프로그래머스 - [3차] 자동완성words와 queries 배열의 길이 제한사항이 $2\leq{…}\leq{100,000 }$ 이기 때문에 완전 탐색으로는 이 문제를 풀 수 없다.그래서 words를 Trie 자료구조상 트리 형태로 저장시키고, queries 배열의 원소들을 Trie에서 하나씩 순차적으로 탐색해야 한다. 트리 자료구조에서 탐색..

https://school.programmers.co.kr/learn/courses/30/lessons/43236접근주어진 제한사항에서 rocks 배열의 길이가 50,000개 이하이므로 솔루션의 시간복잡도는 $O(N^2)$이 될 수 없다.$O(N\log{N})$, $O(N\log{M})$이나 $O(N)$의 시간복잡도를 가지는 알고리즘을 선택해야 한다.잘못된 초기 접근펼치기/접기나는 아쉽게도 $O(N)$의 시간복잡도로 문제를 해결하려고 시도했다. DP로 접근했다.일단 주어진 rocks 배열을 오름차순으로 정렬시킨다. 근데, 이미 이 부분에서 $O(N\log{N})$이 됐다…바위 사이의 거리를 담은 배열 d를 정의한다. 이 때, 시작지점과 도착지점도 포함하여 거리를 계산한다.예를 들어, rocks 배열을 오..