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/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..
자료구조 (Data Structure)자료구조란 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법.저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분된다.선형 자료구조 : 데이터가 일렬로 나열되어 있음배열, 연결 리스트, 스택, 큐비선형 자료구조 : 데이터가 특정한 형태를 띄고 있음트리, 그래프 1. 배열 (Array)가장 기본적인 자료구조로 동일한 자료형의 데이터를 일렬로 나열한 자료구조배열의 특징데이터 접근이 용이하다. (O(1)의 시간복잡도를 가짐)데이터 삽입/삭제가 어렵다. (O(N)의 시간복잡도를 가짐)중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동해야 한다.구조가 간단하여 프로그램 작성이 쉽다.1) 배열 []int[] arr =..
