https://www.acmicpc.net/problem/11438알고리즘 분류 : 자료 구조, 트리, 최소 공통 조상, 희소 배열❓문제🔅해석순서input된 값을 adjacent list(양방향 간선)에 넣는다.BFS로 트리 탐색bfs로 트리를 탐색하면서 각 노드의 깊이(depth)와 부모(parent)를 기록한다. 희소 테이블(Sparse Table) 구성각 노드에 대해 2^k번째 부모를 미리 계산한다. 이 테이블을 이용하면, 두 노드의 깊이를 맞춘 후, 공통 조상을 빠르게 찾을 수 있다.Find LCA항상 b가 a보다 depth가 큰 노드(root로부터 먼)가 되도록 swapa, b의 depth 맞추기(0.에 의해 항상 b를 끌어올리게 된다)2에서 depth를 맞추었는데 a와 b가 같다면 lca를 ..
https://www.acmicpc.net/problem/3830알고리즘 분류 : 자료 구조, 분리 집합❓문제🔅해석Union-Find 알고리즘으로 해결한다. 부모와 가중치를 함께 저장하기 위해 Node class를 정의한다. // TestCase34 7! 1 2 100? 2 3! 2 3 100? 2 3? 1 3! 4 3 150? 4 1 1. Initialize 2. "! 1 2 100" find를 통해 서로의 부모가 같은지 확인하고 같지 않다면, a의 부모를 b의 부모로 변경하여 하나로 합친다. 3. "? 2 3"2과 3의 부모를 확인한다. 2의 parent(=2) != 3의 parent(=3) 이므로 "UNKNOWN"를 반환한다. 4. " ! 2 3 100" 5. "? 2 3"2과 3의 부모를 확인..
https://www.acmicpc.net/problem/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..
https://www.acmicpc.net/problem/2243알고리즘 분류 : 자료 구조, 세그먼트 트리, 이분 탐색 ❓문제🔅해석 세그먼트 트리에서 구간의 정보를 조회하는 query는 총 다섯가지 정보를 넘긴다.query(int left, int right, int node, int queryLeft, int queryRight) 현재 문제에서는 해당 순위의 정보만 필요하므로 query(int left, int right, int node, int query) 으로 넘긴다. 문제의 입력을 보자면, 레벨 1 사탕 2개, 레벨 3 사탕 3개가 존재하고 여기서 2번째로 맛있는 사탕을 꺼내준다고 할 때, 답은 레벨 1이다. 위 그림을 볼 때, 노드를 탐색하면서 해당 노드의 값이 B보다 크거나 같을 때 왼쪽..
https://www.acmicpc.net/problem/2042알고리즘 분류 : 자료 구조, 세그먼트 트리 ❓문제🔅해석세그먼트 트리를 이용하는 가장 기본적인 문제이다.인덱스 트리 생성 - init인덱스 트리의 리프 노드에 배열을 담아야 하므로 리프 노드가 시작하는 인덱스 번호를 알아야한다.리프 노드의 개수를 S로 표현하고 S는 N 이상의 2^n으로 표현 가능한 수여야 한다.따라서 S 는 아래와 같이 구한다. (N은 주어진 배열의 크기)S = 1;while (S 리프 노드에 배열에 적혀있는 수를 넣기위해 S번째부터 넣는다.그 외 내부 노드는 S - 1번째부터 자식 노드(왼쪽, 오른쪽) 합을 대입한다.private static void init() { // leaf노드 채우기 for (in..
https://www.acmicpc.net/problem/1927알고리즘 분류 : 자료 구조, 우선순위 큐직접 힙을 구현하여 풀이하였습니다. ❓문제🔅해석직접 힙을 구현하여 풀어본 문제이다. 최소 힙은 ' 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.'는 힙 조건을 가진다.힙 조건에 맞춰 삽입과 삭제 연산을 진행한다. 삽입 연산트리의 가장 마지막 위치에 노드를 삽입한다.추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.만족하지 않는다면 부모와 자식의 키 값을 바꾼다.조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2 ~ 3을 반복한다. 입력을 받다가 '0'을 만나게 되면 삭제 연산을 수행한다. 삭제 연산힙의 삭제 연산은 항상 루트 노드를 삭제한다.트리의 가장 마지막 노드를 루..
