유클리드 호제법빠른 시간에 두수의 최대공약수를 구할 수 있는 방법이다.2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다.2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다.gcd(a, b) = gcd(b, r) 공식 대입해보기a = 36, b = 24gcd(a, b) = gcd(b, a % b)gcd(36, 24)= gcd(24, 12)= gcd(12, 0)r == 0 일 때, b가 최대공약수가 된다. 예제문제백준 14476번 : 최대공약수 하나빼기 https://www.acmicpc.net/problem/14476 최대공약수 구하는 메소드// gcd(a, b) == gcd(b, r) : r ..
트라이(Trie)Prefix Tree, Digital Search Tree, Retrieval Tree문자열을 빠르게 검색할 수 있는 자료구조K진 트리 구조 (문자열 K를 담을 수 있는 트리)단어 사전을 트라이로 생성 후 찾을 단어를 트라이를 사용하여 검색한다.트라이의 root 노드는 항상 공백문자열 상태이다. 구축하기트라이 노드 설계class Node { Node child[]; boolean isWord; }단어 사전의 입력할 단어를 트라이에 삽입루트 노드부터 시작하여 단어의 첫 글자부터 트라이를 탐색만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 있다면, 현재 노드를 해당하는 자식 노드로 이동만약, 현재 노드의 자식 중 현재 입력 중인 철자에 해당하는 자식이 없다면, 새로운 자식..
https://www.acmicpc.net/problem/9202알고리즘 분류 : 자료 구조, 그래프 이론, 문자열, 브루트포스 알고리즘, 그래프 탐색, 트리, 깊이 우선 탐색, 백트래킹, 트라이❓문제🔅해석Trie 알고리즘을 활용하여 문제를 해결한다. 먼저, 입력받은 단어들로 Trie를 생성한다."ACM'을 입력받았다면 아래와 같이 Trie 객체가 생성된다. for문을 순회하여 Trie 객체인 root를 완성하면 뒤에 N개의 맵을 입력받아 탐색한다. dfs를 작성할 때는 아래 6단계를 거쳐 작성하는 것을 추천한다. 1. 체크인visited 배열에 true 를 입력하고 현재 map 좌표에 있는 알파벳 하나를 Stringbuilder에 붙인다. 2. 목적지인가목적지의 기준은 1) 현재 노드가 단어이면서, ..
