아이디어를 코드로 바꾸는 구현
* 피지컬로 승부하기
-
코딩 테스트에서 구현이란?
=> "머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정" 어떤 문제를 풀든 간에 소스코드를 작성하는 과정을 필수 이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다. -
흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미.
ex) 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점까지 출력해야하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱을 해야 하는) 문제 -
피지컬이 좋다? 프로그래밍 언어의 능숙하고, 코드 작성 속도가 빠른 사람.
-
구현
완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
* 구현시 고려해야 할 메모리 제약사항
-
c/c++과 달리 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원함. 따라서 파이썬을 이용하는 독자라면 자료형의 표현 범위 제한에 대해 깊게 이해 하고 있지 않아도 무방.
-
**파이썬에서 리스트 크
meanstrike94
/
implement_basic
Python
Run
Invite
기 **
파이썬에서는 여러 개의 변수를 사용할 때는 리스트를 사용.
파이썬에서 리스트를 이용할 때에 고려해야 할 사항은 바로 코딩 테스트의 메모리 제한.
대체로 코딩 테스트에서는 125 ~ 512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 함. => 이럴 때는 메모리 제한을 염두에 두고 코딩을 진행해야 함.
<INT 자료향 데이터의 개수에 따른 메모리 사용량>
데이터의 개수(리스트 길이) 메모리 사용량
1,000 약 4KB
1,000,000 약 4MB
10,000,000 약 40MB
파이썬은 다른 언어에 비해서 구현상의 복잡함이 적은 편이지만 데이터 치리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자(그러나 이러한 경우는 드믐)
예제4-1) 상하좌우 문제
#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)
예제4-2) 시각
#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)
실전문제1) 왕실의 나이트
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)]
#8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
#이동하고자 하는 위치 확인
next_row = row + step[0]
next_column = row + step[1]
#해당 위치로 이동이 가능하다면 카운트 증가
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)실전문제2) 게임 개발
#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:
dirction = 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)