규도자 블로그

재귀함수로 구하는 피보나치 수열의 직관성 나는 항상 def fib(n): head, body, tail = 0, 1, 0 for _ in range(n): tail = head + body head = body body = tail return head PythonCopy 이런식으로 피보나치 수열의 몇 번째 수를 구하곤 했었다. 연산도 빠르고 코드도 직관적이라서 피보나치수열을 응용해야하는 문제가 있을 때마다 항상 이 로직을 애용해왔는데 얼마 전에 피보나치수열을 재귀로 구현해야했다. 하지만 이 로직에 뇌가 절여진 나는 구현하지 못했다. 아, 참고로 피보나치수열을 재귀로 구하는 방법은 def fib(n): if n == 0: return 0 elif n == 1 or n == 2: return 1 else:..

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 내가 알고리즘 문제를 풀 때 소수가 필요한 부분에서 자주 사용했다. def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정 sieve[j] = False # 소수 목록 산출 return [i for i in range(2, n) if sieve[..

최대공약수 구하기 알고리즘을 풀다가 비슷한 로직이 필요했는데 잘 생각이 안나서 이번기회에 정리해두려고 한다. 보통 컴퓨터로 최대공약수를 구할 땐 유클리드 호제법이라는 방법을 많이 쓴다. 이미 기원전 300년에 검증된 로직이므로 그런게 아닐까 싶다. 유클리드 호제법은 다음과 같다. 입력으로 두 수 m, n이 들어온다. (m>n) n이 0이라면 m을 반환한다. m이 n으로 나누어 떨어지면 n을 반환한다. 위 2, 3번의 경우에 해당되지 않을 경우 n을 m으로, m을 n으로 나눈 나머지를 n에 대입하고 1번으로 돌아간다. 코드로 표현하면 다음과 같다. def gcd(m, n): if m < n: m, n = n, m if n == 0: return m if m % n == 0: return n else: re..

피즈버즈 테스트(FizzBuzz Test) 피즈버즈테스트(FizzBuzz Test)라고 해서 프로그래머의 역량을 간단하게나마 평가하는 알고리즘 문제가 있다. 훌륭한 프로그래머라면 2분 이내에 정확히 작동하는 코드를 작성할 수 있다고 한다. FizzBuzz 문제는 옛날 TV에서 하던 삼육구 + 아자랑 비슷한데, 삼육구 + 아자는 숫자에 3이 들어가거나 5가 들어가면 박수를 치고 아자를 외쳐야하는 반면 Fizzbuzz문제는 1부터 100까지 1씩 커지는 수열에서 3의 배수때는 Fizz, 5의 배수일때는 Buzz, 3과 5의 공배수일 때는 FizzBuzz를 출력하게 하고 위 세개의 모든 경우에도 들지 않으면 숫자 그대로를 출력해야 한다. 간단해보이는 이 문제가 왜 프로그래밍 테스트의 대표격이 됐을까. 사실 이..