이것이 취업을 위한 코딩 테스트다 CHAPTER 4 구현

• 구현
  • 완전 탐색
    • 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 시뮬레이션
    • 문제에서 제시한 알고리즘을 한단계씩 차례대로 직접 수행
• 알고리즘 팁
  • 리스트를 여러개 선언하고, 그중에서 크기가 1000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다는 점을 기억
  • 시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제가 있다면 일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘을 이용하여 문제를 풀어야 한다.
  • 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색 사용

 

문제 2. 왕실의 나이트

'''

    Chapter 4. 왕실의 나이트

   

    접근법 1

        이동할 수 있는 경우의 수가 8가지

        모두 다 확인

'''

import sys
input = sys.stdin.readline

# 현재 나이트가 위치한 곳의 좌표
now = input()

# 좌표 행,열
now_r, now_c = int(now[1]), ord(now[0])-ord('a') + 1 

# 특정 위치로 이동
d = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]]

answer = 0
for dr,dc in d:
    # 이동한 위치
    nr = now_r + dr
    nc = now_c + dc
    # 이동한 위치가 체스 안 이라면
    if 1 <= nr <= 8 and 1 <= nc <=8:
        answer += 1 

print(answer)

 

문제 3. 게임 개발

'''

    Chapter 4. 게임 개발

   

    접근법 1

        조건1과 조건2를 합치면

            (왼쪽 방향으로 돌면서 갈 수 있는 곳 찾기)를 최대 4번 가능

            찾으면 이동

            못찾으면 조건 3

'''

import sys
input = sys.stdin.readline

# 맵의 세로크기, 가로크기
N,M = map(int,input().split())

# 게임 캐릭터가 있는 칸의 좌표 (A,B), 바라보는 방향
# d : {0:'북',1:'동',2:'남',3:'서'}
A,B,d = map(int,input().split())
direction = [[-1,0],[0,1],[1,0],[0,-1]]

# 맵 {0:'육지',1:'바다'}
arr = [list(map(int,input().split())) for _ in range(N)]

answer = 1
# 방문 여부
visited = [[0]*M for _ in range(N)]
visited[A][B] = 1
while True:
    # 왼쪽 방향으로 4방향 다 확인
    for _ in range(4):
        d = (d-1)%4
        # 왼쪽 방향에 아직 가보지 않은 칸이 존재하는가?
        left_r, left_c = A + direction[d][0], B + direction[d][1]
        # 범위 내 +  육지 + 가본적 없는
        if 0 <= left_r < N and 0 <= left_c < M and arr[left_r][left_c] == 0 and visited[left_r][left_c] == 0:
            A = left_r
            B = left_c
            visited[A][B] = 1
            answer += 1
            break
        
    # 4방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우
    # 바라보는 방향에서 뒤로 1칸
    else:
        back_r, back_c = A - direction[d][0], B - direction[d][1]
        # 뒤로 한칸이 바다인 경우 멈추기
        if arr[back_r][back_c] == 1:
            break
        else:
            A = back_r
            B = back_c

print(answer)