머릿속에 그리고, 실행!
구현이란?
- 알고리즘 문제를 보면 우리는 생각을 한다
- 어떻게 풀어야 할까?
- 풀이 방법이 떠올랐다고 풀리는 것은 아니다! 그 아이디어를 코드로 옮겨야 한다.
- 이러한 일련의 과정들이 구현이 된다.
- 코딩 테스트에 있어 구현이란?
- 머리로 생각해 풀이를 떠올리는 것은 어렵지 않지만, 그를 코드로 옮기기는 어려운 문제
- 사소한 조건이 많을수록 구현하기 까다롭다.
- 파이썬의 경우 타 언어에 비해 큰 단위의 정수나 문자열에 대한 처리가 수월한 편
- 다만 크기가 1천만 이상인 리스트를 여러 개 만드는 경우 메모리 초과를 주의하자
어떻게 접근할까?
- 파이썬은 매우 느려
- 다른 언어에 비해 동작 속도가 느리다.
- 대략 1초에 2천만번의 연산을 수행한다고 가정하고, 시간 제한에 따라 복잡도를 계산해야 한다.
- 시간 제한, 데이터의 개수 등을 꼭 확인할 것!
- 문제가 길다
- 구현 문제의 경우 사소한 조건들을 문제 안에 명시해주기에 문제의 길이가 길다.
- 겁먹지 말고, 문제를 읽으며 중요한 정보들을 잘 추려내자.
주요 유형
- 완전 탐색(브루트 포스)
- 문제를 해결하기 위해 모든 경우의 수를 전부 계산하는 방법
- 문제 해결 가능성은 높지만, 시간이 많이 든다.
- 3자리의 암호가 있다면, 000부터 999까지 전부 시도하는 것
- 대체로 for문 / 순열, 조합 / 재귀 / 비트마스크 와 같은 방법을 이용한다.
- 완전 탐색은 주어지는 데이터의 크기 N이 작을 때 효과적!
- 시뮬레이션
- 문제에서 제시하는 알고리즘을 한 단계씩 차례대로 직접 수행
예제 - 상하좌우
N x N 크기의 정사각형 공간에서 사람이 움직인다.
가장 왼쪽 위 좌표는 항상 (1, 1)이다. 상하좌우 4방향의 이동이 가능하다.
L, R, U, D의 이동이 주어졌을 때 도착하게 되는 지점의 좌표는?
생각해보자
- 보통 이런 유형의 문제에서는 2차원 배열을 만들어 이동하곤 하는데, 이 문제에서는 그렇게까지 할 필요는 없어보인다.
- 단순히 n번 이동한 것에 대한 좌표를 구할 뿐이기에 사실 이동에 따라 좌표를 1씩 더해주거나 빼면 된다!
- 이동에 있어 주의할 점은 정사각형 공간을 벗어나지 않게 하는 것! 경계를 벗어나는 움직임은 무시한다.
- 시간 제한은 1초, n의 크기와 이동 횟수의 최댓값은 100이다.
- 데이터의 크기가 매우 작기 때문에 O(N!) 수준의 복잡도가 아니라면 통과가 될 듯하다.
- 아마 O(N)의 복잡도로 풀리지 않을까? 연산 횟수는 이동 횟수에 비례하기 때문이다.
풀이
# 처음 생각한 풀이
# 각 이동마다 함수를 만들었는데, 너무 길다!
# 심지어 각 함수의 if 이하는 모두 동일하다...
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
def up(x, y):
tx, ty = x + dx[0], y + dy[0] # 방향에 맞게 좌표 값 변환
if 1 <= tx <= N and 1 <= ty <= N: # 정사각형 범위를 벗어나지 않았다면
return tx, ty # 새로운 좌표를 반환
else:
return x, y # 그렇지 않다면 해당 이동을 무시함
def down(x, y):
tx, ty = x + dx[1], y + dy[1]
if 1 <= tx <= N and 1 <= ty <= N:
return tx, ty
else:
return x, y
def left(x, y):
tx, ty = x + dx[2], y + dy[2]
if 1 <= tx <= N and 1 <= ty <= N:
return tx, ty
else:
return x, y
def right(x, y):
tx, ty = x + dx[3], y + dy[3]
if 1 <= tx <= N and 1 <= ty <= N:
return tx, ty
else:
return x, y
N = int(input())
move = list(map(str, input().split()))
x, y = 1, 1
for i in move:
if i == 'U':
new_x, new_y = up(x, y)
elif i == 'D':
new_x, new_y = down(x, y)
elif i == 'L':
new_x, new_y = left(x, y)
elif i == 'R':
new_x, new_y = right(x, y)
x, y = new_x, new_y
print(x, y)# 간추린 풀이
# 이동방향을 따로 저장하고, 방향의 인덱스를 함수의 인자로 전달한다.
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
def move(x, y, check):
tx, ty = x + dx[check], y + dy[check]
if 1 <= tx <= N and 1 <= ty <= N: # x와 y축 모두 공간 안에 있어야 하기에 or가 아닌 and!
return tx, ty
else:
return x, y
N = int(input())
move_list = list(map(str, input().split()))
move_direction = ['U', 'D', 'L', 'R']
x, y = 1, 1
for i in move_list:
check = move_direction.index(i)
new_x, new_y = move(x, y, check)
x, y = new_x, new_y
print(x, y)답안 예시
n = int(input())
x, y = 1, 1
plans = input().split()
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, ny = x + dx[i], y + dy[i]
if nx < 1 or ny < 1 or nx > n or ny > n: continue
x, y = nx, ny
print(x, y)예제 - 시각
정수 N을 입력받았을 때 00h:00m:00s에서부터 Nh:59m:59s 까지 모든 시각에 3이 포함되는 경우의 수를 구하면?
생각해보자
- 시각은 0시부터 23시까지 -> 데이터가 크지 않다.
- 00시 00분 00초부터 확인해도 문제가 없다.
- 00:00:00부터 시작하기에 연산 회수는 (분 x 초 x 시간(N)) 정도가 되지 않을까?
풀이
N = int(input())
cnt = 0
for i in range(N + 1):
for j in range(60):
for k in range(60):
if '3' in str(i) or '3' in str(j) or '3' in str(k):
cnt += 1
print(cnt)예제 - 왕실의 나이트
나이트의 위치가 주어졌을 때, 이동이 가능한 경우의 수는 몇 가지인가?
생각해보자
- 입력은 a1과 같이 들어온다. a1이라는 문자열을 가지고 8 x 8 사이즈의 배열에 나이트를 위치시켜주어야 한다.
- 한 좌표를 기준으로 이동할 수 있는 경우의 수는 최대 8개!
- 지정된 위치를 기반으로 매 경우에서 이동이 가능한지를 확인한다.
풀이
# 수직으로 이동한 뒤 수평으로 이동하거나, 수평으로 이동한 뒤 수직으로 이동하는 경우를
# 전부 별도로 나누어 계산했다. 하지만 그럴 필요가 없었다....
# 처음부터 dx, dy를 나이트가 이동할 수 있는 8방향으로 맞추었다면 아래의 두 함수는
# 사용할 이유가 없게 된다.
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
def move_first(x, y):
for i in range(4):
check = False
for j in range(2):
tx, ty = x + (dx[i] * (j + 1)), y + (dy[i] * (j + 1))
if 0 <= tx < 8 and 0 <= ty < 8:
check = True
else:
check = False
if check == True:
move_second(tx, ty, i)
def move_second(x, y, i):
global cnt
if i == 0 or i == 1:
for j in range(2, 4):
new_x, new_y = x + dx[j], y + dy[j]
if 0 <= new_x < 8 and 0 <= new_y < 8:
cnt += 1
elif i == 2 or i == 3:
for j in range(0, 2):
new_x, new_y = x + dx[j], y + dy[j]
if 0 <= new_x < 8 and 0 <= new_y < 8:
cnt += 1
location = input()
arr = [[0] * 8 for _ in range(8)]
location_y, location_x = abs(97 - ord(location[0])), int(location[1]) - 1
arr[location_x][location_y] = 1
cnt = 0
move_first(location_x, location_y)
print(cnt)# 조금 더 줄인 풀이
dx = [-1, -2, -2, -1, 1, 2, 2, 1] # 한 위치에서 나이트가 이동할 수 있는 경우
dy = [-2, -1, 1, 2, -2, -1, 1, 2]
location = input()
arr = [[0] * 8 for _ in range(8)]
location_y, location_x = abs(97 - ord(location[0])), int(location[1]) - 1
arr[location_x][location_y] = 1
cnt = 0
for i in range(8):
tx, ty = location_x + dx[i], location_y + dy[i]
if 0 <= tx < 8 and 0 <= ty < 8:
cnt += 1
print(cnt)답안 예시
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
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)예제 - 문자열 재정렬
모든 알파벳을 오름차순으로 정렬하고, 그 뒤에 모든 숫자의 합을 붙여넣으면?
생각해보자
- 모든 알파벳을 오름차순으로 재정렬하고, 그 뒤에 모든 숫자를 더한 값을 붙여 출력한다.
- 우선 문자열의 요소를 하나씩 전부 순회한다.
- 문자라면 새로운 빈 문자열에 채워넣고, 숫자라면 더해 별도의 변수에 담는다.
- 문자만 남은 새로운 문자열을 정렬해준 뒤, 숫자를 문자열 형태로 덧붙여준다.
풀이
word = input()
new_string = ''
temp = 0
# 사실 알파벳 소문자와 숫자만 들어오기에 아래와 같은 반복문이 가능했다.
# 다른 특수문자나 기호가 들어왔다면 할 수 없는 방법
for i in word:
if ord(i) >= 65:
new_string += i
else:
temp += int(i)
new_string = list(new_string)
# print(sorted(new_string)) # 사실 이렇게 정렬하면 아래의 정렬 코드는 필요없다.
for i in range(len(new_string) - 1):
for j in range(i + 1, len(new_string)):
if ord(new_string[i]) > ord(new_string[j]):
new_string[i], new_string[j] = new_string[j], new_string[i]
print(''.join(new_string) + str(temp))답안 예시
- 문자열을 구성하는 요소가 알파벳인지, 숫자인지를 내장함수로 확인할 수 있다!
isalpha()나isdigit()내장함수로 확인이 가능하다.isalpha()의 경우, 문자열에 공백이나 숫자가 포함된다면 False를 돌려준다.isdigit()의 경우, 문자열에 공백이나 문자가 포함된다면 False를 돌려준다.- 이 문자열이 문자와 숫자로 구성되어있는지를 확인하려면
isalnum()으로도 가능하다. - 위 모든 함수들은
str.isalpha()와 같은 방식으로 사용한다.
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))
즐거워요