- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 흔히 구현 유형의 문제라 하면, 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.
- 구현 유형의 예시로는 다음과 같다.
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아서 사용해야 하는 문제 (ex. 순열, 조합 찾기)
- 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.
- 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다.
시뮬레이션 유형의 문제. 나의 풀이는 너무 지저분하다.
# 내 풀이
n = int(input())
command = list(input().split())
count = len(command)
x = 1
y = 1
i = 0
while count > 0 :
if command[i] == 'R' :
i += 1
count -= 1
if y == n :
continue
y += 1
elif command[i] == 'L' :
i += 1
count -= 1
if y == 1 :
continue
y -= 1
elif command[i] == 'U' :
i += 1
count -= 1
if x == 1 :
continue
x -= 1
elif command[i] == 'D' :
i += 1
count -= 1
if x == n :
continue
x += 1
else :
print('잘못된 입력')
break
print(x, y)
방향 벡터를 활용하면 더욱 간단히 작성할 수 있다.
# 교재 풀이
# 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)
모든 경우를 다 세서 푸는 문제. 완전 탐색(Brute Forcing) 문제 유형이라고 불린다. 가능한 경우의 수를 모두 검사해보는 탐색 방법을 의미한다.
# 내 풀이
n = int(input())
x = [3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53]
count = 0
for i in range(n+1) :
for j in range(60) :
for k in range(60) :
for three in x :
if i == three :
count += 1
break
if j == three :
count += 1
break
if k == three :
count += 1
break
print(i,j,k,count,three)
print(count)
# 교재 풀이
# H를 입력받기
h = int(input())
count = 0
for i in range(h + 1):
for j in range(60):
for k in range(60):
# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)
교재에서는 시, 분, 초를 문자형으로 바꾸어서 풀었다. 파이썬에서는 형변환이 다른 언어들보다 비교적 자유롭기 때문에 이와 같이 해결 하는 습관이 소스 코드를 간단히 하는 지름길인 것 같다.
시뮬레이션, 완전 탐색, 2차원 좌표 이용하는 구현 문제
# 내 풀이
spot = list(input())
# 좌표로 변환
x = int(spot[1])
input_y = ['a','b','c','d','e','f','g','h']
for i in range(len(input_y)):
if spot[0] == input_y[i] :
y = i+1
# 총 경우의 수
dx = [-1, -2, -1, -2, 1, 2, 1, 2] # 위1 위2 위1 위2 아1 아2 아1 아2
dy = [-2, -1, 2, 1, -2, -1, 2, 1] # 왼2 외1 오2 오1 왼2 왼1 오2 오1
# 이동 가능 여부 확인
count = 0
for i in range(8) :
if not (x + dx[i] < 1 or x + dx[i] > 8 or y + dy[i] < 1 or y + dy[i] > 8) :
count += 1
print(count)
# 교재 풀이
# 현재 나이트의 위치 입력받기
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)
내 풀이와 생각하는 방법은 똑같았다. 그러나, 입력 방식에서 아스키 코드를 이용했다는 점과 방향 설정을 튜플을 활용하여 하나의 리스트로 설정했다는 점이 차이가 있었다.
숫자는 따로 합계를 계산해주고, 알파벳은 별도의 리스트에 저장하면 되는 문제.
# 내 풀이
data = input()
data_str = []
sum = 0
for x in data :
if 65 <= ord(x) <= 90 :
data_str.append(x)
else :
sum += int(x)
data_str.sort()
for x in data_str :
print(x, end = '')
if sum != 0 :
print(sum)
# 교재 풀이
data = input()
result = []
value = 0
# 문자를 하나씩 확인하며
for x in data:
# 알파벳인 경우 결과 리스트에 삽입
if x.isalpha():
result.append(x)
# 숫자는 따로 더하기
else:
value += int(x)
# 알파벳을 오름차순으로 정렬
result.sort()
# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
result.append(str(value))
# 최종 결과 출력(리스트를 문자열로 변환하여 출력)
print(''.join(result))
isalpha() : 알파벳 판별 함수
'구분자'.join(리스트) : 리스트 내의 문자열을 합쳐주는 함수
교재 풀이에서는 위의 함수들을 사용했다는 것과 숫자의 합계를 문자열로 변환하여 하나의 리스트에 append 해주었다는 점이 차이가 있다.
시뮬레이션 문제. 이와 비슷한 문제를 코드업 100제 마지막 문제에서 풀어봤다고 생각했는데, 이 문제는 거기에다 방향 전환까지 추가되어서 너무 어려웠다. 하루 넘게 코딩해보다가 도저히 못하겠다 싶어서 풀이를 봤다.
# N, M을 공백을 기준으로 구분하여 입력받기
n, m = map(int, input().split())
# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * m for _ in range(n)]
# 현재 캐릭터의 X 좌표, Y 좌표, 방향을 입력받기
x, y, direction = map(int, input().split())
d[x][y] = 1 # 현재 좌표 방문 처리
# 전체 맵 정보를 입력받기
array = []
for i in range(n):
array.append(list(map(int, input().split())))
# 북, 동, 남, 서 방향 정의
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 왼쪽으로 회전
def turn_left():
global direction
direction -= 1
if direction == -1:
direction = 3
# 시뮬레이션 시작
count = 1
turn_time = 0
while True:
# 왼쪽으로 회전
turn_left()
nx = x + dx[direction]
ny = y + dy[direction]
# 회전한 이후 정면에 가보지 않은 칸이 존재하는 경우 이동
if d[nx][ny] == 0 and array[nx][ny] == 0:
d[nx][ny] = 1
x = nx
y = ny
count += 1
turn_time = 0
continue
# 회전한 이후 정면에 가보지 않은 칸이 없거나 바다인 경우
else:
turn_time += 1
# 네 방향 모두 갈 수 없는 경우
if turn_time == 4:
nx = x - dx[direction]
ny = y - dy[direction]
# 뒤로 갈 수 있다면 이동하기
if array[nx][ny] == 0:
x = nx
y = ny
# 뒤가 바다로 막혀있는 경우
else:
break
turn_time = 0
# 정답 출력
print(count)