알고리즘

[python] 재귀 알고리즘 - 최대공약수 GCD - 유클리드 호제법

안녕하세요. 이번 포스팅은 재귀 알고리즘에 대해서 다뤄보았습니다. 재귀는 다양한 알고리즘에서 활용이 되는데요. 특히, 재귀를 모르고 지나친다면 다른 재귀에 기반하여 풀 수 있는 고등 알고리즘에 대해 알 수 없게 된다는 점이 있습니다.  재귀로 쉽게 풀 수 있는 대표적인 알고리즘 중 하나인 최대공약수 찾는 알고리즘에 대해서 다뤄보겠습니다. 예를 들어 9 x 24 인 직사각형이 있다고 가정하겠습니다. 쉽게 범용적으로 풀 수 있는 방법 중 하나는 다음처럼 정사각형으로 분할이 될 때까지 쪼개는 방법이 있는데요. 로직 자체는 간다합니다.위 첫번째 그림처럼 9 x 24 크기의 직사각형에서 짧은 변의 길이인 9를 한 변으로 하는 정사각형으로 나눠줍니다. 그러면 2개의 9x9 정사각형이 만들어지고 하나의 9 x 6 크..

투 포인터 (two pointer) 알고리즘이란?

투 포인터란? '투 포인터'라는 기법은 문자열 string 또는 배열 array 기반의 알고리즘 문제에서 자주 사용할 수 있는 효과적인 기법입니다. 구체적으로 투 포인터도 여러 가지 방식이 있지만, 대개는 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략으로 볼 수 있습니다. 알고리즘 문제를 풀 때, 일반적인 반복문 접근 또는 브루트 포스 방식을 활용하다 보면 타임아웃에 직면하게 되는 경우가 종종 있습니다. 투 포인터 방식을 활용하면 복잡도를 한단계 낮출 수 있습니다. ==> $O(N^k)$ --> $O(N^{k-1})$ 투 포인터는 크게 두가지 방법으로 응용할 수 있습니다. 앞쪽 첫번째에서 시작하는 포인터 & 뒤쪽 끝에서 시작하는 포인터 빠른 포인터가 느린 포인터..

[leetcode 42] Trapping Rain Water - hard

오늘은 리트코드(leetcode) 42번 문제 trapping rain water에 관해 풀어보겠습니다. (링크: https://leetcode.com/problems/trapping-rain-water/description/) 문제는 높이를 입력받아 비 온 뒤 얼마나 많은 물이 쌓일 수 있는지 계산을 요구하는 문제입니다. 이 문제는 높이와 너비 모든 공간을 차례대로 살펴보면서 풀어나간다면 $O(n^2)$만큼의 시간 복잡도로 풀이가 가능합니다. 하지만 시간 복잡도가 높기 때문에, 더 효율적인 풀이를 찾는 것이 권장됩니다. 풀이: 투 포인터 활용 투 포인터를 활용하면 $O(n)$의 시간 복잡도로 문제를 풀 수 있다고 생각했습니다. 우선 다음 그림을 보겠습니다. 위 그림에서 주목할 부분은 '가장 높은 막대..

[백준 24313] 점근적 표기 1 문제 풀이 & 해설 - 파이썬

백준 24313 문제에 대해 풀어보겠습니다. 이 문제는 알고리즘 수행 시간에 관한 문제로 "점근적 표기 (asymptotic notation)"에 관해 알고 있는지를 묻고 있습니다. Background: 점근적 표기 점근적 표기에 대해 간략히 설명을 하자면, Big-O를 계산할 때 입력값의 크기에 따라 함수가 얼마나 빨리 커지는지 알아볼 때 중요하지 않은 항과 상수 계수를 제거하면서 이해를 방해하는 불필요한 부분을 없앤 표기법이라고 볼 수 있습니다. 즉, 간략한 예로 $ y = 0.0006n^3 - 1000 $라고 했을 때, $O(y)=n^3$ 가 되는 반면에, $ x = 1000n^2 + 1000 $의 Big O는 $O(x)=n^2$ 가 되기 마련입니다. 따라서 y의 수행시간이 x보다 더 크다고 할 수..

[python] 등차수열과 등차수열의 합

알고리즘 및 코딩 테스트를 진행하다보면, 이따금 수학적 공식을 알고 있다면 생각보다 쉽게 풀리는 문제들이 있습니다. 수많은 공식들을 모두 외울 수도 없지만, 기본적인 내용은 짚고 넘어가면 도움이 될 수 있습니다. 그 중에서도 오늘은 등차수열에 관해 다뤄보려고 합니다. 등차수열의 기본 공식: n 번째 항 구하기 등차수열에서 n번째 항을 구하는 공식은 다음과 같습니다. $$ a_n = a_1 + (n-1)d $$ 여기서 각 기호는 다음을 의미합니다. $a_n$: $n$번째 항 $a_1$: 첫번째 항 $d$: 공차 $n$: 항의 순서 이 공식은 등차수열의 어느 항이든지 첫 번째 항과 그 항의 순서를 통해 계산할 수 있게 해줍니다. 등차수열의 기본 공식은 주로 수열의 특정 항을 찾을 때 사용되는데, 간단..

[백준 9506] 약수 합 - 파이썬

백준 9506번 문제는 약수들의 합을 구해 완전수 (perfect number)인지 아닌지를 판별하는 문제입니다. 저는 다음과 같이 풀었습니다. while 문으로 exit (-1)전까지 입력을 받습니다. 1부터 n까지 for문을 돌면서, 나머지가 없는 즉, 모든 약수 (factor)를 리스트에 기록합니다. 약수의 합이 입력 값(n)과 같은지 확인하고 맞다면 형식에 맞춰 출력을 진행 if __name__ == '__main__': while True: n = int(input()) result = [] if n == -1: break else: for i in range(1, n): if n % i == 0: result.append(i) if n == sum(result): result = list(ma..

[백준 11005] 진법 변환 2 - 파이썬

백준 11005번은 '주어진 10진법 수 N을 사용자가 지정한 진법 B로 변환하는 알고리즘'을 만드는 문제입니다. 원리만 이해하면 생각보다 간단하게 풀 수 있습니다. 간단한 예시를 통해 이해하고 답을 보겠습니다. 예시 10진수 10을 2진수로 변환하는 경우: N = 10, B = 2 10진수 -> B진법 변환은 나머지를 기록해둘 필요가 있습니다. 또한 10진수 값 N 을 B로 나눴을 때 몫을 기억해둘 필요가 있습니다. 지속적으로 업데이트 해주어야 합니다. 10 % 2 = 0 --> 나머지 = "0" N // B : 10 // 2 = 5 --> 몫 = "5" N = 5 (i.e. N = N // B) 5 % 2 = 1 --> 나머지 = "1" N // B: 5 // 2 = 2 --> 몫 = "2" 2 % ..

[백준 2563번] 색종이 - 파이썬

백준 2d array 부분 색종이 알고리즘에 대해 풀어보겠습니다. (https://www.acmicpc.net/problem/2563) 처음 이 문제를 접했을 때 들었던 생각은 각 색종이 area를 구하여 더함 교집합 영역을 구함 하나의 교집합 영역만 전체 area에 남겨두고, 나머지는 뺌 그런데 이렇게 처리하면 예외 케이스가 많이 생겨 너무 복잡도가 증가한다는 단점이 있었습니다. 단순하게 생각해보면, A라는 100 x 100 매트릭스가 있다고 가정했을때, 겹치든 겹치지지 않든, 색종이가 영역을 덮고 있다면 A[i][j] 의 값을 1로 설정하고 그렇지 않다면 0으로 설정하면 불필요한 예외 처리 없이 문제를 해결 할 수 있습니다. 정답 코드는 다음과 같습니다. if __name__ == '__main__..