Part2, 구현

LeeKyoungChang·2021년 11월 14일

algorithm 이것이 코딩 테스트다

Algorithm

목록 보기

5/203

구현

코팅 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

프로그래밍 언어의 문법을 정확히 알고 있어야 하며 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

구현 유형의 문제

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미

구현 유형을 묶어서 다룬다.

(1) 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

(2) 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행

int 자료형 데이터의 개수에 따른 메모리 사용량

데이터 개수(리스트의 길이)	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

[4-1] 상하좌우

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 = 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] 시각

완전 탐색 유형 : 가능한 경우의 수를 모두 검사해보는 탐색 방법

일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다.

완전 탐색 적절한 경우 : 탐색 해야 할 전체 데이터 개수가 100만 개 이하일 경우

# 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)

[4-3] 왕실의 나이트

list1 = [-2,-1,1,2,2,1,-1,-2]
list2 = [-1,-2,-2,-1,1,2,2,1]

List안에 Tuple을 넣을 수 있다.

steps = [
    (-2,-1), (-1,-2),(1,-2),(2,-1),
    (2,1),(1,2),(-1,2),(-2,1)
]

print(steps[0][1])

# 결과
# -1

# 왕실의 나이트
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)

[4-4] 게임 개발

1) 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다.

현재 위치에서 반시계 방향으로 90도 회전한 방향부터 검토

2) 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

3) 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

문제를 이해하는데 시간이 걸렸다.

현재 방향에서 반시계 방향으로 회전한 후, 이동 가능하다면 이동

아니라면 한 번 더 반시계 방향으로 회전 한다.

예를 보면 이와 같다.

소스

# 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()
    print("x y dir 좌표 : ",x, y, direction)
    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)