본문 바로가기

알고리즘

[Python3] 31게임! 1부터 31까지 순서대로 번갈아가며 1개 이상 3개 이하의 숫자를 말한다.31을 말하면 게임에서 패배한다. ex) 1, 2, 3 / 4, 5 / 6, 7, 8 / .... / 28, 29, 30 / 31(패배) 한번쯤은 친구들과 이 게임을 해본적이 있을 것이다. 간단한 게임이지만 꽤나 두뇌를 쓰기 때문에 재밌게 할 수 있다. 알고리즘은 생각보다 바로 떠오르지 않는다. 컴퓨터가 31을 굳이 안 말해도 되지만 말해서 자폭하는 경우와 유저가 잘못 입력하는 경우들을 다 따져줘야 한다.from random import randint import sys num = [] for i in range(1, 34): # 유저가 31과 그 이후 까지 입력할까봐 넉넉히 잡았다. num.append(i) def com_num(.. 더보기
[Python3] 제곱해서 같은 수 - 2 n미만 자연수 중에 제곱해서 끝자리가 제곱한 자연수인 수를 찾아라예를 들어 15를 제곱하면 225이고, 25는 15와 같지 않으니 이 조건에 만족하지 않는다. 어제 제곱해서 같은 수 1을 올리고 좀더 빨리 계산할 수 없을까 쭉 고민했다. 그러다, abcde가 위 조건에 만족하는 수라면 bcde도 위 조건에 만족하는 수라는 걸 착안해서 기억해서 풀게 만들어 봤다. 또, 두개를 비교해야 하니 파이썬의 실행시간 측정코드도 넣었다 코드는 다음과 같다.import timestart = time.time()~~~코드 구간 ~~~print(time.time() - start)import time start = time.time() M = 1000000 """ for i in range(1, M + 1): if((i*.. 더보기
[Python3] 제곱해서 같은 수 - 1 10,000 미만 자연수 중에 제곱해서 끝자리가 제곱한 자연수인 수를 찾아라예를들어 15를 제곱하면 225이고, 25는 15와 같지 않으니 이 조건에 만족하지 않는다. 재밌는 문제라고 생각한다. 이 문제를 다음과 같은 방법으로 접근할 수 있을거라 생각한다. n의 제곱 빼기 n을 이용한다. 이게 무슨말이냐, 이 조건에 만족하는 수 하나인 5를 생각해보자, 5의 제곱은 25이고 25에서 5를 빼면 20이다. 이것은 10의 배수이다. 만약 69랑 숫자의 제곱이 3,269 라면 3,200만 남아서 100의 배수라는 의미의다. 따라서 다음과 같이 생각할 수 있다. 위 조건을 만족하는 n이 k자리 자연수라면, n^2 - n이 10^(k+1)의 배수이다. 프로그램은 다음과 같다.for i in range(1,9999.. 더보기
[Python3] 피보나치 수 피보나치 수는 0과 1로 시작해서 그 다음 숫자가 마지막 두개의 숫자의 합인 수열이다. 점화식으론 다음과같다.[사진 출처-위키백과] 점화식만 놓고 보자면 실제 구동하는 코드와 유사해서 다음과 같이 금방 짤 수 있을 것이다.def fibo(n): if(n == 0): return 0 if(n == 1): return 1 return fibo(n-1) + fibo(n-2) 하지만, 조금만 생각해보면 이 코드는 사람이 이해하고 읽기는 쉽지만 컴퓨터에겐 매우 복잡한 식이란걸 알 수 있다. fibo(5)를 호출하면 다음과 같은 일이 발생한다. 엄청나게 복잡해지는 연산을 컴퓨터가 해야한다. 물론 컴퓨터라 이정도는 빠를지 몰라도, 숫자가 무지막지하게 커지면 컴퓨터의 연산 실행 시간은 상상을 초월한다. 헌데, 저 순서.. 더보기
갈색눈과 빨간눈 이 문제는 실제 면접장에서 물어봤던 문제와 유사한 문제이다.'누워서 읽는 알고리즘'에 있던 문제이며, 꽤나 재미있는 문제여서 올려본다.어느 섬에 사람들의 눈 색은 빨간눈이거나 갈색눈이다.섬에 거울같은 자신을 볼 수 있는 물체가 하나도 없어서 사람들은 자신의 눈 색깔을 스스로 알아 낼 수 없었다.또, 사람들은 마법에 걸려서 자신이 빨간눈이라는 사실을 깨달으면 그날 밤 섬을 떠나야 한다. (마법인지라, 자신의 눈이 빨갛다는 것을 깨달으면 무조건 섬을 떠나야한다)따라서 사람들은 서로의 눈색깔을 말하지 않는 규칙을 정하고 잘 살고 있었다. 어느날 이 규칙을 모르는 관광객이 한명 찾아오고 다음과 같이 말하고 다른 섬으로 갔다.당신들 중 적어도 한명은 빨간눈이군요이때, 이 말을 받아들인 섬의 사람들은 어떻게 될까?.. 더보기