구현
구현
풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
이코테에서는 이 유형에서 완전 탐색과 시뮬레이션을 다루고 있는데, 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제이다.
구현에서는 채점 환경을 고려하는 것이 중요하다. 특히 파이썬은 C/C++에 비해 동작 속도가 느리다. 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2000만 번의 계산을 수행한다고 가정하면 크게 무리가 없다.
얼마 전에 사용자에게 정수 입력을 받고 제켄도르프 정리(Zeckendorf’s Theorem)을 구현하는 알고리즘 과제를 풀었었는데, 그때 나의 코드가 Time Limit Exceeded이 떴다.
나의 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
n = int(input())
n_first = n
i = 0
people = []
chicken = []
def fibo (n):
if n <= 1:
return n
else:
return fibo(n-1) + fibo(n-2)
while fibo(i) < n: # 가장 큰 피보나치 수 찾기
i += 1
if fibo(i) >= n:
i -= 1
people.append(fibo(i))
chicken.append(fibo(i-1))
chicken_index = i # 연속된 피보나치수는 안되기 때문에 인덱스를 저장해서 나중에 비교
n = n - fibo(i) # 가장 큰 피보나치수 빼주기
while True: # 다 더하면 빠져나가기
while fibo(i) > n: # 반복
i -= 1
if fibo(i) <= n and i != chicken_index:
if i == 0:
break
people.append(fibo(i))
chicken.append(fibo(i-1))
chicken_index = i
n = n - fibo(i)
break
if sum(people) == n_first:
break
print(sum(chicken))
이 코드에서 피보나치 함수가 재귀 알고리즘을 사용하기 때문에 시간복잡도가 지수의 영향을 받아서 최종적으로 최악의 경우 시간복잡도가 O(2^log(n))가 된다. 따라서, 재귀 알고리즘을 쓰지 않고 구현해야만 했다.
정답 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def fibonacci_sum(n):
# 피보나치 수열 생성
fibonacci = [0, 1]
while fibonacci[-1] < n:
fibonacci.append(fibonacci[-1] + fibonacci[-2]) # 최종적으로, n보다 큰 요소가 마지막에 들어감.
# 피보나치 수열 중 n보다 작거나 같은 수를 찾아서 더하기
result = 0
i = len(fibonacci) - 2 # n보다 큰 요소 포함 안시키기 위함.
while n > 0 and i >= 0:
if fibonacci[i] <= n: # 빼고 남은 값(n)보다 작은 최대의 피보나치 수 구하기
n -= fibonacci[i] # 피보나치수 빼주기
result += fibonacci[i - 1] # 치킨 개수 추가
i -= 1
return result
# 사용자로부터 입력 받음
n = int(input())
# 최종 결과 출력
print(fibonacci_sum(n))
이렇게 하면 재귀 알고리즘이 쓰이지않기 때문에 시간복잡도가 지수의 영향을 받지 않는다. 둘 다 피보나치를 구하는 정상적인 알고리즘인데 이렇게 달라지는게 신기했다. fibonacci.append(fibonacci[-1] + fibonacci[-2])이 함수를 사용하는게 관건이었던 것 같다. 굳이 큰 수부터 재귀적으로 피보나치를 적용하지 않고, fibonacci[-1]를 이용하여 리스트 끝에 있는 요소를 불러올 수 있는 것이다.
이처럼, 구현을 할 때 채점 환경을 고려하여 시간복잡도가 지수의 영향을 최대한 받지 않게 조심해야한다.
예제1-상하좌우
여행가 A가 N x N 크기의 정사각형 공간에서 움직이는데, Left, Right, Up, Down의 방식으로 움직이는 구현이다. 정사각형 공간을 벗어나는 움직임을 무시된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
N = int(input())
plan = list(input().split())
now_loca = [1, 1]
count = 0
while count != len(plan):
if plan[count] == 'L' and now_loca[1] - 1 != 0: # 왼쪽
now_loca[1] -= 1
if plan[count] == 'R' and now_loca[1] + 1 != N + 1: # 오른쪽
now_loca[1] += 1
if plan[count] == 'U' and now_loca[0] - 1 != 0: # 위
now_loca[0] -= 1
if plan[count] == 'D' and now_loca[0] + 1 != N + 1: # 아래
now_loca[0] += 1
count +=1
print(' '.join(str(x) for x in now_loca))
리스트로 코드를 짜서, 마지막에 join함수를 이용하여 ‘ ‘간격으로 하나씩 출력해줘야 했다..
굳이 now_loca[1,1]로 짜지 않고, x = 1, y = 1로 진행시켰어도 되는 거였다.
그래도 덕분에 join함수를 알아갔으니까 긍정적으로 생각하자!
답안 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# N 입력받기
n = int(input())
x, y = 1, 1
plans = input().split()
# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']
# 이동 계획을 하나씩 확인
for plan in plans:
# 이동 후 좌표 구하기
for i in range(len(move_types)):
if plan == move_types[i]:
nx = x + dx[i]
ny = y + dy[i]
# 공간을 벗어나는 경우 무시
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
# 이동 수행
x, y = nx, ny
print(x, y)
책에 있는 답안에는 기가막힌 풀이가 있었다. dx, dy로 나눠서 move_types[i]에 따라 진행되는 코드이다. 이동하는 코드는 저렇게 배열을 생각해낼 수 있으면 좋을 것 같다.
예제2-시각
00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 경우의 수를 구하는 문제이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
N = int(input())
cal = 0
count = 0
for i in range(60):
if '3' in str(i):
cal += 60
else:
for j in range(60):
if '3' in str(j):
cal += 1
for k in range(N+1):
if k == 3:
count += 60 * 60
else:
count += cal
print(count)
if '3' in str(i):
이 부분만 구현할 수 있으면 정말 쉬운 문제였다.
내 코드가 뭔가 찝찝할 때, GPT한테 물어보는데,
numbers_with_3 = [x for x in range(60) if '3' in str(x)]
이렇게 간결하게도 구현할 수 있었다.
실전 문제 - 왕실의 나이트
가로는 a~h까지, 세로는 1~8까지 구성되어있는 8 x 8 체스판에서 나이트의 위치가 입력된다.(ex. a1) 그 위치에서 나이트가 이동할 수 있는 경우의 수를 구하는 문제이다.
나의 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
a = input()
string = list(a)
x = string[0]
y = string[1]
count = 0
if int(y) - 2 >= 1:
if ord(x) - 1 >= 97:
count += 1
if ord(x) + 1 <= 104:
count += 1
if int(y) + 2 <= 8:
if ord(x) - 1 >= 97:
count += 1
if ord(x) + 1 <= 104:
count += 1
if ord(x) - 2 >= 97:
if int(y) - 1 >= 1:
count += 1
if int(y) + 1 <= 8:
count += 1
if ord(x) + 2 < 104:
if int(y) - 1 >= 1:
count += 1
if int(y) + 1 <= 8:
count += 1
print(count)
처음부터 막혔다.. 원래 보통 ‘ ‘을 기준으로 입력받아서 input().split()을 쓰면 됐는데, 붙어있는 것들 나눠야해서 조금 당황스러웠다. 그냥 list()를 써서 문자열을 나눈 뒤에, 따로 x, y에 넣어주면 되는 것이었다.
그 이후에는 그냥 주어진 대로 쭉 구현을 해보았다.
답안 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1
# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
# 이동하고자 하는 위치 확인
next_row = row + step[0]
next_column = column + step[1]
# 해당 위치로 이동이 가능하다면 카운트 증가
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)
ord() 함수를 써서 구현하는 아이디어는 똑같았지만, for step in steps 안을 살펴보면 굉장히 잘 짜여져있는 것을 볼 수 있다.
어차피 나이트가 움직일 수 있는 최대 경우의 수는 8가지이기 때문에 이를 덧셈, 뺄셈으로 step[]에 넣어주고, 이를 for문을 이용하여 경우의 수를 세는 것이다.
알게된 것 정리
3이 포함된 정수 찾기
if '3' in str(i):
0-59까지 3이 포함된 정수 찾기
numbers_with_3 = [x for x in range(60) if '3' in str(x)]
’ ‘을 간격으로 리스트의 요소들을 출력하기
print(' '.join(str(x) for x in now_loca))
문자열을 리스트로 저장하기
string = list(a)
x = string[0], y = string[1]