khann's IT와 경제 블로그

알고리즘 → (2)건

프로그래머스 단어 변환 풀이 (파이썬)

프로그래머스 단어 변환 풀이 (파이썬) 프로그래머스 -> 코딩 테스트 연습 -> 깊이/너비 우선 탐색(DFS/BFS)에서 단어 변환에 대한 문제 python으로 BFS가 아닌 DFS를 이용해 문제를 풀었다. 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot, dot, dog, lot, log, cog]라면 hit->hot->dot->dog->cog와 같이 4단계를 거쳐 변환할 수 ..
알고리즘 2020. 3. 4. 15:32

알고리즘 정리 #1 - 최대공약수와 최소공배수

최대공약수(GCD, Gratest Common Divisor) 최대공약수란, 2개의 자연수의 공통된 약수 중에서 가장 큰 정수이다. 여기서 약수는 어떤 수를 나누었을 때 나누어 떨어지는 수이다. -> 6의 약수는 1, 2 ,3, 6이다. 만약 1과 자기 자신밖에 약수가 존재하지 않으면 '소수'이다. -> 7, 11 등등 따라서 두 자연수의 약수 중에 공통된 최댓값을 구하면 된다. -> 두 자연수 2와 4의 최대공약수(GCD)는 2이다.(2의 약수 1, 2와 4의 약수 1,2,4) 최대공약수를 구하는 여러 알고리즘 중에 유클리드 호제법(Euclidean Algorithm)이 가장 유명하다. 호제법 또는 연제법(連除法)은 두 수 A와 B가 있으면 서로의 수를 나누어가기를 반복하며 나머지가 0이 되었을 때의 ..
알고리즘 2019. 7. 20. 13:11
◀ 1 ▶

티스토리툴바