구현

'이것이 취업을 위한 코딩테스트다' 참고

 

구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

ㄴ 이 책에선 완전 탐색, 시뮬레이션 유형을 묶어 다루고 있음

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

 

변수의 표현 범위

• 파이썬에서는 프로그래머가 직접 자료형을 지정할 필요가 없으며 매우 큰 수의 연산 또한 기본으로 지원한다. > 자료형의 표현 범위 제한에 대해 깊게 이해하고 있지 않아도 괜찮다.
• 다른 언어와 마찬가지로 유효숫자에 따라서 연산 결과가 원하는 값이 나오지 않을 수 있다는 점을 기억하자.

 

리스트 크기

• 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자.
• 리스트를 여러 개 선언하고, 그 중 크기가 1,000만 이상인 리스트가 있다면 메모리 용량 제한으로 문제를 풀 수 없게 되는 경우도 있다.

 

[ 111쪽 상하좌우 ]

 

My Code

import sys
n = int(sys.stdin.readline().rstrip())

move = list(input().split())

row = 1
col = 1

for i in range(len(move)):
    if move[i] == 'L':
        if col == 1:
            continue
        col -= 1

    elif move[i] == 'R':
        if col == n:
            continue
        col += 1

    elif move[i] == 'U':
        if row == 1:
            continue
        row -= 1

    else:  # D
        if row == n:
            continue
        row += 1

print(row, col)

 

책 속 Code

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

• 연산 횟수는 이동 횟수에 비례 ( ex. 이동 횟수가 N번이면 시간 복잡도는 O(N) )
• L, R, U, D에 따른 이동 방향을 리스트로 만들어서 for문으로 코드 통일
• x, y랑 nx, ny를 따로 둠 >  nx, ny이 조건을 벗어나도 따로 처리를 안해줘도 됨

 

[ 113쪽 시각 ]

 

My Code

 

책 속 Code 

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

 

[ 115쪽 왕실의 나이트 ]

 

My Code

• 분명 풀었는데 날아감 ㅠㅠ ...

책 속 Code 

# 현재 나이트의 위치 입력받기
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)

• 현재 나이트의 위치를 입력 받을 때, ord() 함수를 이용함 - 특정 문자를 아스키 코드로 변환하는 함수

 

[ 118쪽 게임 개발 ]

 

My Code

n, m = map(int, input().split())
x, y, start = list(map(int, input().split()))
array = [[0]*m for _ in range(n)]
# visit = [[0]*m for _ in range(n)]  # 1 - 방문

for i in range(n):
    array[i] = list(map(int, input().split()))

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
count = 1

while True:
    for i in range(4):
        array[x][y] = 1
        x += dx[i]
        y += dy[i]

        if array[x][y] == 1:
            x -= dx[i]
            y -= dy[i]
            array[x][y] = 0
        else:
            count += 1

• 미완성
• 이전에 공부했던 BFS 코드랑 유사한 예제 같으나 확실한 과정이 생각나지 않아 끝까지 못함 ㅠㅠ

 

책 속 Code 

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

• 2차원 리스트를 선언할 때 리스트 컴프리헨션을 이용하는 것이 효율적이라는 점을 기억하자.
• direction == -1일 때 direction이 3이 되도록 하여 0, 1, 2, 3 반복
• 회전 > 정면에 가보지 않은 칸이 존재하는 경우 / 가보지 않은 칸이 없거나 바다인 경우 / 네 방향 모두 갈 수 없는 경우 - 뒤로 갈 수 있음 or 바다로 막혀 있음

 

[ BOJ 1292 쉽게 푸는 문제 ]

a, b = map(int, input().split())

array = []

i = 1
while len(array) < 1000:
    for _ in range(i):
        array.append(i)
    i += 1

result = 0
for j in range(a-1, b):
    result += array[j]

print(result)