본문 바로가기

트리10

[Javascript/PGS] Lv.3 : 등대 - js 런타임에러 해결법 https://school.programmers.co.kr/learn/courses/30/lessons/133500 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 프로그래머스 레벨 3 등대 문제 - 트리 dp, dfs 유형* 정답 풀이는 최하단에 1. 재귀 풀이 - DFS이 풀이는 트리 dp 문제의 정석인 느낌인데, js로는 풀 수 없다.파이썬의 경우에는 sys.setrecursionlimit를 사용한다면, 재귀의 최대 깊이를 설정할 수 있어서이렇게 풀면 되지만...자스는 그런거 없다고 함 이 풀이로 제출 시 93.8점이 나왔다. (테스트 9만 틀림) let dp = null;let visited = .. 2025. 2. 26.
[문제해결기법] 8. 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합 : 전체집합의 부분집합들 중, 둘을 고르면 교집합=공집합, 전체 합집합=U U의 두 원소가 같은 부분집합의 원소인지 아닌지 어떻게 알 수 있을까? 신장트리 : 그래프 G의 노드를 모두 포함하는, E에 속하는 에지로 만든 트리 최소신장트리 : 트리에 속한 가중치의 합이 가장 작은 신장 트리. 최소 신장 트리 (MST) 만들기 Prim’s algorithm : 현재 집합(노드들)과 연결된 에지 중 가중치가 최소인 것을 MST 집합에 포함시킴. 구현법에 따라 시간복잡도가 차이남 다익스트라 알고리즘 = 특정 시작노드부터 다른 노드들까지의 최단거리를 구함. 유/무향 그래프 프림 알고리즘 = 모든 노드들을 최소비용으로 연결 / 두 노드사이의 거리는 최.. 2023. 6. 16.
[문제해결기법] 6. 세그먼트 트리 1. Segment Tree 부분합 문제에서 응용 가능 생성 코드 2. 합을 구하는 코드 [start, end]의 합을 구하려면 루트부터 시작하여 다음을 점검한다. 노드가 나타내는 구간이 [left, right]라면 다음의 4가지 경우가 가능하다. 각 경우마다 처리는 다음과 같다. (1) [start, end]와 [left, right]가 겹치지 않음 -> 할 일이 없다 (2) [start, end]가 [left, right]를 포함 -> 미리 구해둔 [left, right]의 합을 사용한다. (3) [start, end]를 [left, right]가 포함 -> 두 자식 노드에 대해서 정확히 어느 노드가 [left, right]를 포함하는지 찾는다. (4) [start, end]가 [left, right.. 2023. 4. 18.
[문제해결기법] 4. 자료구조2 1. 트리 지름 트리의 두 정점 u, v의 거리의 최댓값 (1) O(n^3) : brute force (2) O(n^2) : u를 고정하고 bfs한다. (3) O(n) 트리에서 임의의 정점 x를 선택하고 x에서 가장 먼 정점 y를 찾는다.(bfs) 이후 y에서 가장 먼 정점 z를 찾는다. 그러면 y와 z가 가장 멀리 떨어져있는 정점 쌍이다. 증명 원하는 답이 두 정점 u와 v이다. 그렇다면 3가지 가능성이 있는데, x에서 가장 먼 점이 y라고 하면 (1) x = u / x = v (2) y = u / y = v (3) x,y,u,v 모두 다른 경우 (1)과 (2)는 위 알고리즘의 답이 맞다는 것이 자명하다. (3)의 경우는 u~y 경로와 u~v 경로가 거리가 같은 경우 이외에는 없어야 한다. x,y,u,.. 2023. 4. 16.
[문제해결기법] 3. 자료구조1 1. RMQ : Range Minimum Query (범위 최소 쿼리) 배열의 부분배열에서 최솟값을 찾기 (1) O(n^3) 전처리, O(1) 질의 : brute force 방식으로 가능한 RMQ(a,b)에 대한 답을 모두 저장해놓는다. n^2칸을 채워야하고, 한 칸을 채울 때 최대 O(n)시간이 걸린다. (2) O(n^2) 전처리, O(1) 질의 : 가능한 RMQ(a,b)에 대한 답을 모두 저장하는데, RMQ(a,b+1) = min(RMQ(a,b) , A[b+1])을 사용하여 n^2칸을 각각 O(1)의 시간으로 채울 수 있다. (3) O(n) 전처리, O(sqrt(n)) 질의 : 배열을 sqrt(n) 묶음으로 나눈 후 각 묶음의 최솟값을 구하는데에 O(n)이 걸리며, RMQ(a,b)를 구하.. 2023. 4. 16.
[C++/PGS] Lv.2 : 타겟 넘버 (DFS) 깊이/너비 우선 탐색(DFS/BFS) : 타겟 넘버 문제 출처 - 프로그래머스 코딩테스트 고득점 Kit 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 .. 2023. 2. 23.
728x90
반응형

티스토리툴바