알고리즘
-
유클리드 호제법Algorithms 2017. 11. 9. 10:55
오늘은 최대 공약수를 구할 수 있는 파워풀한 알고리즘인유클리드 호제법 에 대해 포스팅을 하도록 하겠다. 유클리드 호제법의 정의는 다음과 같다. 두 양의 정수 a, b (b > a) 에 대해 b = aq + r (0 35 이므로 r = 35 이다.즉, gcd(60, 95) = gcd(60, 35) = gcd(35, 60) 이다.다음 식은60 % 35 -> 25 이므로gcd(35, 60) = gcd(35, 25) = gcd(25, 35) 이고,35 % 25 -> 10 이므로gcd(25, 35) = gcd(25, 10) = gcd(10, 25) 이고...25 % 10 -> 5 이므로gcd(10, 25) = gcd(10, 5) = gcd(5, 10) 이고10 % 5 -> 0 이므로최대 공약수는 5 가 된다. 요..
-
[www.acmicpc.net] 별찍기-11 (2448번) 문제 (2)Algorithms 2017. 10. 19. 17:11
지난번 작성한 포스팅에 이어서 새로운 알고리즘으로 문제를 풀어보기로 했다.지난번 내용이 궁금하면여기를 통해 확인하기 바란다.해당 포스팅 내용으로 저작권 문제가 발생할 경우 글을 삭제하도록 하겠습니다. :) 이 포스팅은 누구에게 보여주기가 아닌 내가 그냥 정리하는 수준이므로 소스코드가자세하게 별로 나와있지 않다. 고 이전 포스팅에도 말했었다. 참고하기 바란다. ;) 자 그럼 이번에는 이진 트리가 아닌 동적 프로그래밍 기법을 통해서 문제를 풀어보자. 일단, 문제가 뭔지는 알아야하니 문제를 적고 가자. 문제는 다음과 같다. 입력: 첫째 줄에 N이 주어진다. N은 항상 3*2^k 수이다. (3, 6, 12, 24, 48, ...) (k 0 일 경우 3 * 3^(k - 1) 이 된다.3. 전체 별모양을 저장할 2..
-
[www.acmicpc.net] 별찍기-11 (2448번) 문제 (1)Algorithms 2017. 10. 19. 15:48
백준 온라인 저지에는 다양한 알고리즘 문제들이 많이 있다. 그 중에서 별찍기-11 (2448번) 문제에 대해 포스팅하려고 한다. 해당 포스팅 내용으로 저작권 문제가 발생할 경우 글을 삭제하도록 하겠습니다. :) 이 포스팅은 누구에게 보여주기가 아닌 내가 그냥 정리하는 수준이므로 소스코드가 자세하게 별로 나와있지 않다.참고하기 바란다. 문제는 다음과 같다. 입력: 첫째 줄에 N이 주어진다. N은 항상 3*2^k 수이다. (3, 6, 12, 24, 48, ...) (k
-
Brute-Force 알고리즘Algorithms 2016. 3. 11. 14:03
요즘 이슈인 "이세돌 vs AlphaGo"에 관한 기사를 찾아 보다가 아래와 같은 기사를 보았다. "모든 경우의 수를 다 탐색하는 알고리즘인 브루트 포스(Brute force)를 일종의 '훈수꾼'으로 사용해 100% 승리할 수밖에 없다." (출처 : http://www.huffingtonpost.kr/) 보다보니깐 브루트 포스 알고리즘이 무얼까 궁금해서 한번 찾아봤다. 요 알고리즘은 어떻게 돌아갈까? 짜잔. 정의는 아래와 같다. "길이가 n인 텍스트 T에서 길이가 m인 패턴 P를 찾는 간단한 방법" 그럼 이게 무슨 말일까? 예를 보자. 이게 과연 예일까? T는 아래와 같은 문자열을 포함한 텍스트다. 0 0 0 1 0 0 1 0 1 1 1 0 1 ... 0 0 1 P의 패턴이 1 0 1 이라고 하면 T에서..