나름 개발자의 IT블로그

배열에서 특정한 수를 찾으려면 어떻게 할까? 앞에서부터 하나씩 찾아보면 될 것이다. arr = [9,3,7,5,6,2,0] x = 3 for i in arr: if x == i: print("찾았다") 최악의 경우는 배열 끝에서 찾은 경우이므로 $O(n)$만큼 시간이 걸릴 것이다. 만약 배열이 정렬되어 있다면 더 빠른 시간 안에 찾을 수 있다. 만약 배열이 arr = [1,3,5,7,8,9,10]이 있다고 하자. 이 배열에서 8이 있는지 찾고 싶다. 그럼 위 코드를 사용하여 찾는다면 찾는데 5번의 탐색이 필요하다. 하지만 정렬이 되어 있으니 다른 방법을 사용해보자. 우선 배열의 가운데 값을 선택한다. 만약 선택한 값이 찾는 값이라면 그대로 반환하고 아니라면 찾는 수보다 큰지 작은지 판별한다. 정렬이 되어..

알고리즘을 풀며 쌓아온 꿀팁 아닌 꿀팁을 정리하고자 한다. 1. (파이썬) 여러개의 변수 입력받기 # 여러개의 변수 a,b,c = map(int, input().split()) # 1 2 3 # 한줄로 입력받는 리스트 arr = list(map(int, input().split())) # 1 2 3 4 5 6 7 8 9 # 여러줄을 입력받는 리스트 arr = [int(input()) for _ in range(n)] # 1 # 2 # 3 # 4 # 2차원 배열 arr = [list(map(int, input().split())) for _ in range(n)] # 1 2 3 # 4 5 6 # 7 8 9 2. (파이썬) 배열 초기화 # 1차원 배열 a = [0]*n # 2차원 배열 a = [[0]*n f..

알고리즘 문제를 풀다 보면 "답이 커질 수 있으니 $1,000,000,007$로 나눈 나머지를 출력하시오" 이런 문장이 많이 보인다. 오늘은 이런 나머지연산에 대한 이야기를 하고자 한다. 피보나치 수 7 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 한번 보자 단순히 문제에서 제시한대로 구현한다면 이런 코드가 나올것이다. n = int(input()) a, b = 0, 1 for i in range(n): a,b = b, a+b print(a%1000000007) 하지만 이렇게 제출하게 되면 시간초과 또는 틀렸습니다를 받는다. 그 이유는 계산 과정에서 a, b의 값이 매우 커지기 때문이다. 이를 ..

피보나치 수는 많은 성질을 가지고 있다. 이 포스트에서 소개하고자 한다. 여기서 살펴볼 피보나치수열은 다음과 같다. $F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} \ (n\ge3)$ 1. $\sum_{k=1}^n F_k = F_{n+2} - 1$ 정의에 따라 $F_1 = F_3 - F_2$ $F_2 = F_4 - F_3$ ... $F_n = F_{n+2} - F_{n+1}$ 이다. 그럼 식을 다음과 같이 변형할 수 있다. $F_1+F_2+...+F_n$ $= (F_3-F_2)+(F_4-F_3)+...+(F_{n+2}-F_{n+1})$ $= F_{n+2} - F_2$ $= F_{n+2} - 1$ 이를 통해 $\sum_{k=a}^b F_k $ $= \sum_{k=1}^b F_k..

이전 글에서 피보나치 수를 구하다가 빠른 거듭제곱이 나와 따로 글로 남기게 되었다. 거듭제곱을 위해 다음 코드를 작성하면 $O(N)$의 시간이 필요하다. def pow(a,n): r = 1 for _ in range(n): r *= a return r 위 코드는 거듭제곱을 $a^n=a^{n-1} \times a$ 방식으로 구한다. 이것을 빠르게 해 보자! $n$이 짝수이면 $a^n = a^{n/2} \times a^{n/2}$ $n$이 홀수이면 $a^n = a^{n/2} \times a^{n/2} \times a$ 가 된다. 이제 이것을 재귀적으로 계산하면 된다. 예를 들어 $3^{60}$을 계산해보자 $3^{60} = 3^{30} \times 3^{30}$ $3^{30} = 3^{15} \times 3..

피보나치 수열은 다음 조건을 만족하는 수열이다. $F_0=1, F_1=1, F_n=F_{n-1}+F_{n-2} \ (n \gt 2)$ $1,1,2,3,5,8,13...$ (경우에 따라서 $F_0=0$이 되기도 함) 위 식을 사용해서 구하면 시간 복잡도가 $ O(N) $이기 때문에 $N