16 Apr 2017
|
알고리즘
프로그래밍
문제출처
문제
수학을 공부하던 민지는 재미있는 사실을 발견하였습니다. 그 사실은 바로 연속된 자연수의 합으로 어떤 숫자를 표현하는 방법이 여러 가지라는 것입니다. 예를 들어, 15를 표현하는 방법은
(1+2+3+4+5)
(4+5+6)
(7+8)
(15)
로 총 4가지가 존재합니다. 숫자를 입력받아 연속된 수로 표현하는 방법을 반환하는 expressions 함수를 만들어 민지를 도와주세요. 예를 들어 15가 입력된다면 4를 반환해 주면 됩니다.
풀이
def expressions(num):
answer = 1
for i in range(1,num//2+1):
test_sum = i
for j in range(i+1, num//2+2):
test_sum += j
if test_sum > num:
continue
if test_sum == num:
answer += 1
return answer
# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(expressions(15));
다른사람 풀이
def expressions(num):
answer = 0
for i in range(1, num + 1):
s = 0
while s < num:
s += i
i += 1
if s == num:
answer += 1
return answer
# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(expressions(15));
배운점
- for문의 중첩보다 for문 안에 while문을 사용하면 속도가 더 빠른 것 같다.
11 Apr 2017
|
알고리즘
프로그래밍
문제출처
문제
어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.
A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다.
보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.
“a B z”,4를 입력받았다면 “e F d”를 리턴합니다.
풀이
import string
def caesar(s, n):
alphabet_lower = list(string.ascii_lowercase)
alphabet_upper = list(string.ascii_uppercase)
s = list(s)
for i, char in enumerate(s):
if char in alphabet_lower:
position = (alphabet_lower.index(char) + n) % 26
s[i] = alphabet_lower[position]
elif char in alphabet_upper:
position = (alphabet_upper.index(char) + n) % 26
s[i] = alphabet_upper[position]
else:
pass
return ''.join(s)
# 실행을 위한 테스트코드입니다.
print('s는 "a B z", n은 4인 경우: ' + caesar("a B z", 4))
풀이 과정
- 알파벳 대문자, 소문자 리스트를 준비
- 매개변수 문자열 s를 list로 변환
- 해당 list의 각 요소를 순회하면서
- 해당 문자가 대문자 혹은 소문자에 포함된다면,
- 알파벳 리스트에서 해당 문자의 index 값을 찾아서 매개변수 n을 더하고, 알파벳의 길이인 26으로 나눈 나머지를 구한다.
- 해당 나머지 값을 index 값으로 갖는 문자를 찾아서 리스트 s의 요소를 변경한다.
- 해당 문자가 대문자 혹은 소문자 둘다 포함되지 않는다면 pass 한다.
- 반복이 끝나면, 리스트 s를 문자열로 변환한다.
다른사람 풀이
# 풀이 1
import string
def caesar(s, n):
result = ""
base = ""
for c in s:
if c in string.ascii_lowercase:
base = string.ascii_lowercase
elif c in string.ascii_uppercase:
base = string.ascii_uppercase
else:
result += c
continue
a = base.index(c) + n
result += base[a % len(base)]
return result
# 실행을 위한 테스트코드입니다.
print('s는 "a B z", n은 4인 경우: ' + caesar("a B z", 4))
# 풀이 2
def caesar(plain, no):
result = ""
for k in plain:
if k.isalpha():
if k.islower():
result += chr((ord(k) - ord("a") + no) % 26 + ord("a"))
else:
result += chr((ord(k) - ord("A") + no) % 26 + ord("A"))
else:
result += k
return result
# 실행을 위한 테스트코드입니다.
print('s는 "a B z", n은 4인 경우: ' + caesar("a B z", 4))
배운점
- chr(x) 을 통해서 ascii 코드 10진수, 16진수를 문자로 바꿀 수 있다.
- ord(x) 를 통해서 axcii 문자를 10진수로 바꿀 수 있다.
01 Apr 2017
|
알고리즘
프로그래밍
문제출처
문제
효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다.
풀이
def jumpCase(num):
result = [1, 2]
i = 0
while len(result) < num:
result.append(result[i] + result[i+1])
i += 1
return result[num-1]
#아래는 테스트로 출력해 보기 위한 코드입니다.
print(jumpCase(4))
풀이 과정
- 1칸이 있을 때 경우의 수 : 1
- 2칸이 있을 때 경우의 수 : 2
- 3칸이 있을 때 경우의 수 : 3
- 4칸이 있을 때 경우의 수 : 5
- 5칸이 있을 때 경우의 수 : 8
- n칸이 있을 때 경우의 수 : (n - 2) + (n - 1) 칸이 있을 때 경우의 수의 합으로 피보나치 수열을 통해 구할 수 있다.
다른사람 풀이
def jumpCase(num):
if num == 1:
return 1
elif num == 2:
return 2
answer = jumpCase(num - 1) + jumpCase(num - 2)
return answer
#아래는 테스트로 출력해 보기 위한 코드입니다.
print(jumpCase(4))
01 Apr 2017
|
알고리즘
프로그래밍
문제출처
문제
피보나치 수열이란, 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.
예) 0, 1, 1, 2, 3, 5, 8, 13
인풋을 정수 n으로 받았을때, n 이하까지의 피보나치 수열을 출력하는 프로그램을 작성하세요
풀이
def fib(n):
array = [0, 1]
i = 0
while array[i] + array[i+1] < n:
array.append(array[i]+array[i+1])
i += 1
return array
