Algorithm17 최대공약수 구하기 - 유클리드 호제법 두 개의 자연수에 대한 최대공약수를 구하기 위한 알고리즘으로, 유클리드 호제법이 있다. 유클리드 호제법 - 두 개의 자연수 A, B (A > B) 가 있을 때 A를 B로 나눈 나머지를 R이라고 하면, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. - 위의 아이디어에 재귀함수의 개념을 활용하여, 최대공약수를 구할 수 있다. # 유클리드 호제법을 재귀로 구현하여, 192와 162의 최대 공약수를 구해보자! def gcd(a, b): if a % b == 0: return b else: return gcd(b, a % b) print(gcd(192, 162)) 2021. 9. 21. DP(다이나믹 프로그래밍) Dynamic Programming - 그리디 알고리즘과 같이, 최적화 문제를 해결하는 알고리즘이다. - 문제를 부분 문제로 분할한 후 가장 작은 부분 문제부터 해를 구하여 결과를 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구하는 알고리즘이다. 다음은 피보나치 함수를 DP로 구현한 예시이다. # 기록할 배열의 크기를 먼저 정해놓는 경우 def fibo1(n): arr = [0] * (n+1) arr[1] = 1 # 최초의 부분문제의 해를 배열에 기록 for i in range(2, n+1): arr[i] = arr[i-1] + arr[i-2] # 각 부분문제의 해를 구하여 저장 return arr[n] # 배열의 크기를 미리 정하지 않고 해결하는 경우 def fibo.. 2021. 9. 7. 검색 알고리즘 주어진 자료에서 원하는 값을 찾기 위한 검색 알고리즘을 알아보자. 검색의 종류는 크게 순차 검색, 이진 검색, 해쉬가 있다. 이 번 글에서는 순차 검색과 이진 검색을 알아보자 # 1. 순차검색(sequential search) - 가장 간단하고 직관적인 검색 방법이다. - 배열이나 연결 리스트와 같이 순차 구조로 구현된 자료구조에 적합하다. - 단순하지만, 검색 대상의 수가 많을 경우엔 시간 복잡도가 급격히 증가하여 비효율적이다. - 배열 내 원소가 정렬되어 있지 않은 경우와, 정렬된 경우로 나뉜다. # 정렬되어있지 않은 경우 def search(arr, key): i = 0 n = len(arr) while i < n and arr[i] != key: i += 1 if i < n: return i el.. 2021. 8. 23. 부분집합을 구하는 알고리즘 - bit 연산 활용 특정 원소들로 이루어진 집합이 있다고 할 때, 이 집합의 부분집합을 구하기 위해 bit 연산을 활용할 수 있다. # 비트연산자 기본 & : 비트 단위로 AND 연산을 한다. | : 비트 단위로 OR 연산을 한다. > : 피연산자의 비트 열을 오른쪽으로 이동시킨다. # 2021. 8. 22. 이전 1 2 3 4 5 다음