Algorithm/Algorithm

유클리드 호제법 유클리드 호제법(Euclidean Algorithm)은 자연수의 최대공약수를 구하는 알고리즘의 하나다. 호제법은 두 수가 서로 상대 수를 나눠, 결국 원하는 수를 얻는 알고리즘이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 과정을 반복하여 나머지가 0이 되었을 때의 나누는 수가 최대공약수가 된다. 그림으로 이해하기 파이썬 구현 def uclid(a, b): r = a % b if r == 0: #종료조건 return b else: return uclid(b, r) 최소 공배수 a, b의 최소공배수는 a * b / gcd(a, b) def lcm(a, b): return a*b..

서론 주어진 리스트에서 어떤 key 값을 찾아야 할 때, 만약 리스트가 정렬이 되어있다면 이진 탐색이 유리하고 정렬되지 않은 리스트라면 어쩔 수 없이 리스트의 처음부터 끝까지 하나하나 살펴봐야한다. 이 방법은 순차 탐색이라고 한다. 이진 탐색은 무엇일까? 이번 포스팅에서는 파이썬으로 이진 탐색을 구현해보려고 한다. 이진 탐색이란? 이진 탐색(Binary search)은 정렬된 리스트가 주어졌을 때 사용하는 탐색 방법이다. 이런 정렬된 리스트가 주어지고, 이 중에서 18을 찾아보려고 한다. 이진 탐색은 이 리스트의 가운데를 먼저 본다. 리스트의 가운데는 25다. 우리가 찾고자 하는 수는 25보다 작다. 리스트가 이미 정렬이 되어있으므로 25 이후(오른쪽)의 숫자를 볼 필요가 없다. 이제 25의 왼쪽 숫자들..

분할 정복 알고리즘 분할 정복(Divide and Conquer) 알고리즘은 문제를 더이상 나눠지지 않을 때까지 나누어서 각각을 풀면서 합병하여 문제의 답을 얻는 알고리즘이다. 알고리즘의 기법 중 하나다. 알고리즘 단계 분할 정복 알고리즘에는 크게 세가지 단계가 있다. 1. Devide : 문제가 분할이 가능한 경우, 2개 이상으로 나눈다. 2. Conquer : 나눈 문제가 여전히 분할이 가능하면 다시 Divide로 돌아가고, 분할이 안 되면 문제를 푼다. (재귀) 3. Combine : Conquer한 문제를 합쳐 원래의 정답을 찾는다. 분할 정복 알고리즘에는 재귀가 사용되므로 재귀 알고리즘의 문제점들을 그대로 갖고 간다. 문제 종류 이진 탐색(Binary Search) 정렬(퀵 정렬, 병합 정렬) ..

💡 투 포인터가 필요한 이유? 아래와 같은, 1부터 5까지의 수가 담겨있는 배열에서 합이 5인 부분 연속 수열의 개수를 구하는 방법을 생각해봅시다. 투 포인터를 모른다고 가정했을 때, 생각해낼 수 있는 가장 간단한 방법은 반복문을 이용해 하나하나 구하는 건데요, 1부터 차례대로 합을 구해가며 합이 5가 되면 count를 증가시켜주고, 다음으로는 2부터 시작해서 차례대로 합을 구해가며 합이 5가 되면 count를 증가, 이렇게 3, 4, 5 배열이 끝날 때까지 반복하는 겁니다. 이것을 코드로 작성하면 다음과 같습니다. numbers = [1, 2, 3, 4, 5] count = 1 # 부분수열의 합이 5가 되는 경우의 수를 저장하는 변수 for i in range(5): sum = numbers[i] fo..

💡 구간 합 알고리즘이란? 일반적으로 일정 범위의 합을 구하는 시간 복잡도는 O(N)입니다. 한 번 합을 구하는 거야 그냥 하던대로 합을 구하면 되겠지만, 아주 여러번 그 합을 구해야 한다면 시간복잡도가 펑펑펑 늘어나겠죠?? 이런 경우에 시간 복잡도를 줄이기 위해 합 배열을 구현해놓고 인덱스로 접근하여 O(1)의 시간복잡도로 빠르게 합을 구하는 것이 바로 구간 합 알고리즘입니다. 💡 합 배열 정의하기 합 배열을 그림으로 살펴봅시다. 그림에서 알 수 있듯, 합 배열은 i번째까지의 합을 저장해둔 배열입니다. S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] 입니다. 예를 들어, S[2]는 A[0] + A[1] + A[2] = 15 + 13 + 10 = 38이 되겠죠. 이것..

재귀를 배울 때 빼놓지 않고 꼭 배우는 하노이의 탑. 애기 때 머리 좋아진다고 학교에서 많이 했었는데.. 그땐 나중에 이걸 코드로 구현하고 있을지 알았을까요?..🙄 암튼 이번 포스팅에서는 하노이의 탑을 파이썬으로 구현해보겠습니다! 🗼 하노이의 탑이란? 사진에서 볼 수 있듯이 세 개의 기둥이 있어요. 첫 번째 기둥에는 크기가 다른 여러개의 원판이 쌓여있고요. 원판은 반경이 큰 순서대로 쌓여있습니다. 이걸 순서가 변하지 않게 세 번째 기둥으로 옮겨주어야 하는 게 바로 하노이의 탑 문제입니다. 하노이의 탑에는 규칙이 있는데요, 한 번에 한 개의 원판만을 다른 기둥으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. (크기 순서여야 한다.) * 한 개의 원판만 있다면 넘 당연하게 ..

Summary) 시간 복잡도가 무엇인지, 시간 복잡도를 고려하여 '좋은' 알고리즘을 짜는 방법은 무엇인지에 대해 알아본다. ⚡ Time Complexity(시간 복잡도)란? 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 파이썬 프로그램에서는 2,000만 번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있습니다. 💡 시간 복잡도를 정의하는 2가지 유형 실제로 시간 복잡도를 정의하는 유형은 다음과 같습니다. (빅-세타 유형도 있지만 생략!!) 빅-오메가 : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법. 이렇게만 봐서는 느낌이 잘 안 오죠? 예시를 통해 알아봐요! i..