[알고리즘] 구현(Implementation)

이것이 취업을 위한 코딩테스트다 with 파이썬

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

4장. 구현

1. 아이디어를 코드로 바꾸는 구현

구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
- 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형

구현 시 고려해야 할 메모리 제약 사항

- 파이썬에서 리스트 크기
데이터의 개수(리스트의 길이) / 메모리 사용량
1,000 / 약 4KB
1,000,000 / 약 4MB
10,000,000 / 약 40MB

- 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야한다.

채점 환경

- 1초에 2000만번의 연산을 수행한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다.
- 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 이 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

구현 문제에 접근하는 방법

- 파이썬 구현 난이도는 쉬운편, 프로그램 실행 시간은 긴 편이다.
- Pypy3은 파이썬3보다 실행 속도가 더 빠르다. 코딩 테스트 환경이 Pypy3을 지원한다면 이를 이용할 것

예제 4-1. 상하좌우

- 이동 횟수가 n번일 경우 시간 복잡도는 O(N)이다. 시간 복잡도는 넉넉한 편
- 시뮬레이션(Simulation) 유형

< 답안 예시 >

# 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. 시각

- 모든 시각의 경우를 하나씩 모두 세서 푸는 문제

- 경우의 수가 86, 400가지 밖에 존재하지 않기 때문에 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제 해결 가능

- 전체 시, 분, 초에 대한 경우의 수는 24 X 60 X 60 이며 3중 반복문을 이용해 계산

- 완전 탐색(Brute Forcing) 유형

 

< 답안 예시 >

# H를 입력받기
n = int(input())
count = 0

for h in range(n + 1):
    for m in range(60):
        for s in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(h) + str(m) + str(s):
                count += 1

print(count)

실전문제 2. 왕실의 나이트

- 상하좌우와 비슷한 문제

- 나이트가 이동할 수 있는 경로를 배열에 담고 이 경우의 수를 반복문을 이용하여 하나씩 검사한다

 

< 답안 예시 >

# 현재 나이트의 위치 입력받기
start = input()
x = ord(start[0])   # 열 (문자를 아스키코드로 변환)
y = start[1]        # 행

# 나이트가 이동할 수 있는 8가지 방향 정의
move_type = [(2, 1), (-2, 1), (2, -1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
count = 0

# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
for i in range(8):
    nx = chr(x + move_type[i][0])
    ny = int(y) + move_type[i][1]

    # 해당 위치로 이동이 가능하다면 카운트 증가하고 아니면 무시하고 다음 경우의 수 진행
    if nx < 'a' or nx > 'h' or ny < 1 or ny > 8:
        continue
    else:
        count += 1

print(count)

실전문제 3. 게임 개발

- 시뮬레이션 문제

- 삼성 SW 코딩테스트에서 자주 출제되는 대표적인 유형

- 방향을 설정해서 이동하는 문제 유형에서는 dx, dy라는 별도의 리스트를 만들어 방향을 정하는 것이 효과적이다

 

< 답안 예시 >

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)