이것저것 개발 블로그

https://www.acmicpc.net/problem/7576

문제)

해설)

이 문제는 당연히 bfs로 풀어야지!! 하면서 좀 헤맸다..ㅎㅎ

두 가지 방식으로 했는데, 코드는 두 번째가 조금 더 깔끔한 것 같다.

풀이 1)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    count = 0
    while tomato:
        second = []
        t_li = tomato.popleft()
        for t_mem in t_li:
            x, y = t_mem[0], t_mem[1]
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m:
                    if box[nx][ny] == 0:
                        second.append([nx, ny])
                        box[nx][ny] = 1
                    else:
                        continue
        if second != []:
            tomato.append(second)
        count += 1
    return count - 1

m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

first = []
for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            first.append([i, j])
tomato.append(first)


day = bfs(tomato)
for i in range(n):
    for j in range(m):
        if box[i][j] == 0:
            print(-1)
            exit(0)
print(day)

bfs 함수 내에서 며칠이나 걸렸는지 반환해주려고 이 코드를 짜게 되었다.

한 박스에 토마토가 여러 개일 경우 동시에 토마토가 있는 좌표의 옆 토마토들이 익는다.

따라서 하루 단위로 익을 토마토(box에서 0인 애들) list(first, second)를 만들어 저장하고, 그것을 tomato라는 queue에 저장하는 방식으로 구현했다.

tomato에서 하나를 뽑으면 그 list에 해당하는 좌표를 순회하고, 해당 list에 저장된 좌표를 모두 돌면 하루가 늘어나는 방식이다.

하지만 여기에는 처음에 토마토가 있던 위치도 하루가 지난 것으로 치는 방식이기에 1을 뺀 값을 반환한다.

bfs가 모두 끝나면 혹시 토마토가 익지 않은 경우가 있을 수 있기 때문에 확인해준다.

여기에서 익지 않은 토마토가 있을 경우 -1을 출력하고 exit 하여 끝낸다.

그렇지 않다면 bfs 결과를 출력해준다.

풀이 2)

from collections import deque

def bfs(tomato):
    global box
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    while tomato:
        x, y = tomato.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if box[nx][ny] == 0:
                    tomato.append([nx, ny])
                    box[nx][ny] = box[x][y] + 1
                else:
                    continue


m, n = map(int, input().split()) # m: col, n: row
box = []
tomato = deque()
for i in range(n):
    box.append(list(map(int, input().split())))

for i in range(n):
    for j in range(m):
        if box[i][j] == 1:
            tomato.append([i, j])


day = 0
bfs(tomato)
for i in box:
    for j in i:
        if j == 0:
            print(-1)
            exit(0)
    day = max(day, max(i))
print(day - 1)

이 풀이도 똑같이 bfs를 활용했다.

다른 점은 좌표를 차례대로 queue인 tomato에 저장해주고, bfs를 하는 도중 다음 좌표의 box 값이 0이라면 원좌표의 값에 +1을 해주는 방식을 사용했다. 

또한 이 방식도 처음 토마토의 위치가 1이어서 하루가 더 더해진 방식이므로 box에 0이 없음을 확인하면 1을 뺀 값을 출력해준다.

https://www.acmicpc.net/problem/20207

문제)

풀이)

구현 문제인데 직사각형을 표현하는 방법을 어떻게 표현해야 할지 고민이 많았다. 결국 해결 못해서 이것저것 검색해봄..ㅎ

직사각형은 row, col을 구해야하므로 이를 생각해야 한다.

row는 어떤 날짜에 일정이 몇 개가 있는지에 따라 다르다. 이것은 문제에 있는 그림을 보면 이해하기 쉬울 것이다.

따라서 row를 구하기 위해 일정을 schedule이라는 일차원 배열에 저장한다. 여기에서 가장 큰 것이 row가 될 것이다.

col은 schedule에 저장한 값이 0이 아닌 것들이 연속된 개수이다. 따라서 schedule의 값을 확인하여 col 값을 구한다.

schedule 값이 0이라면 직사각형 하나가 만들어진 것이므로 row * col 값을 정답에 저장해준다.

이때, 만약 schedule의 맨 마지막 index인 365에서 0이 아닌 값이 존재한다면 정답에 row*col 값을 저장해 줄 수 없다.

따라서 이에 해당하는 조건을 달아 해결해준다.

소스코드)

n = int(input())
schedule = [0] * 366
for i in range(n):
    start, end = map(int, input().split())
    for j in range(start, end+1):
        schedule[j] += 1

row = 0
col = 0
answer = 0
for i in range(1, len(schedule)):
    if schedule[i] != 0:
        col += 1
        row = max(row, schedule[i])
    else:
        answer += row * col
        row = 0
        col = 0
    # 만약 맨 마지막에 일정이 존재한다면 정답에 업데이트가 되지 않는다. 따라서 새로운 if문 생성
    if i == len(schedule)-1:
        answer += row * col
print(answer)

https://www.acmicpc.net/problem/2606

문제)

풀이)

def dfs(x):
    global visited
    if visited[x] == False:
        visited[x] = True
        for i in graph[x]:
            dfs(i)
    else:
        return 0

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False for _ in range(n+1)]
li = int(input())

for i in range(li):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

count = 0
dfs(1)
for i in range(2, len(visited)):#1번은 제외
    if visited[i] == True:
        count += 1
print(count)

이 문제는 dfs로 해결했는데, 간단한 문제이다. 물론 bfs로도 충분히 가능할 것이다.

무조건 1번에서 시작하므로 1번 노드에서 각 노드를 방문 표시한 개수를 센다면 문제를 해결할 수 있을 것이라고 생각했다.

따라서 입력으로 그래프를 생성하고(이때 그래프는 i번 노드에 연결된 노드를 모두 저장한다.),

DFS를 이용하여 1번에서 연결된 노드를 방문 표시해준다.

마지막으로 방문 표시한 개수를 세는데, 본인 노드(1번 노드)는 카운트하지 않으므로 2번 노드부터 끝까지 방문 표시된 노드 개수를 센다.

정렬(Sorting)

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

선택 정렬(Selection Sort)

가장 작은 데이터를 선택 -> 맨 앞에 있는 데이터와 교환 -> 그 다음 작은 데이터를 선택 -> 앞에서 두 번째 데이터와 교환

예시)

가장 작은 데이터인 '0'와 맨 앞 데이터인 '7'을 교환한다.

그 다음 작은 데이터인 '1'과 두 번째 데이터인 '5'를 교환한다.

위의 과정을 9번 반복하면 다음과 같이 정렬이 완료된다.

선택 정렬은 데이터 교환 과정을 N-1번 반복하면 완료된다.

선택 정렬 소스코드)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i	# 가장 작은 원소 인덱스
    for j in range(i+1, len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i]	# 교환
    
print(array)

시간 복잡도: O(N^2)으로 느린 편이다.

하지만 코테에서는 가장 작은 인덱스를 찾는 과정이 있으므로 위의 과정은 익숙해지는 것이 좋다.

삽입 정렬(Insertion Sort)

특정한 데이터를 적절한 위치에 삽입하는 정렬. 이때 삽입되기 이전, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

예시)

첫 번째 데이터인 '7'은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다.

'7'의 왼쪽 또는 오른쪽 중에서 결정하는데 왼쪽에 삽입한다.

(본 위치에서 왼쪽으로 차례차례 확인하는 것)

다음 '9'가 어느 위치에 들어갈지 판단한다. 들어갈 수 있는 위치는 총 3가지이다.

'5'의 왼쪽, 오른쪽, 그리고 '7'의 오른쪽이다.

적절한 위치는 '7'의 오른쪽이므로 그대로 둔다.

'0'은 총 4가지의 위치 중 '5'의 왼쪽에 해당하므로 해당 위치에 삽입한다.

'3'은 '0'과 '5'사이에 삽입한다.

위의 과정을 N-1번 반복하면 다음과 같이 정렬이 완료된다.

삽입 정렬의 특징으로는 정렬이 이루어진 원소는 항상 오름차순이다.(내림차순으로 정렬했다면 내림차순!)

예시의 파란색 숫자를 보면 이해하기 편하다.

따라서 삽입 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면, 그 위치에 멈추면 된다.

삽입 정렬 소스코드)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:	# 한 칸씩 왼쪽으로 이동
            array[j], array[j-1] = array[j-1], array[j]
        else:	# 자기보다 작은 데이터를 만나면 그 위치에서 멈추기
            break
    
print(array)

시간 복잡도: O(N^2)

단, 최선의 경우(현재 리스트의 데이터가 거의 정렬되어 있는 상태) 시간 복잡도: O(N)

퀵 정렬(Quick Sort)

기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬

가장 많이 사용하는 정렬!

예시)

처음 pivot을 설정할 땐 맨 처음 데이터로 설정한다.

2번째 데이터부터 차례로 오른쪽으로 가면서 pivot보다 작은 수를 찾는다.

맨 끝 데이터부터 차례로 왼쪽으로 가면서 pivot보다 큰 수를 찾는다.

찾은 후에는 데이터를 교환한다.

이를 pivot보다 작은 수와 pivot보다 큰 수의 위치가 엇갈릴 때까지 반복한다.

엇갈릴 때 pivot과 pivot보다 작은 수를 교환한다!

즉, 위의 예시에서는 1과 5를 교환한다.

그렇다면 pivot인 5를 기준으로 왼쪽은 pivot보다 작은 수, 오른쪽은 pivot보다 큰 수로 구성된다.

이 상태에서, 왼쪽과 오른쪽을 각각 또 정렬한다!

이 과정을 반복하면 전체 정렬이 완료된다.

위의 예시에 해당하는 quick sort를 실행한 결과를 보여준 것이다.

각 과정에서 pivot을 표시했다.

퀵 정렬 소스코드)

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end:    # 원소가 1개인 경우 종료
        return
    pivot = start   # pivot은 첫 번째 원소
    left = start + 1
    right = end
    while left <= right:
        # pivot보다 큰 데이터 찾을때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # pivot보다 작은 데이터 찾을때까지 반복
        while right >= start and array[right] >= array[pivot]:
            right -= 1
        if left > right:    # 엇갈린다면 작은 데이터와 pivot 교체
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]
        
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right+1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도:

평균 시간 복잡도: O(NlogN)

최악 시간 복잡도: O(N^2) => 데이터가 이미 정렬되어 있을 경우!

계수 정렬(Count Sort)

특정한 조건이 부합할 때만 사용할 수 있는 알고리즘. 매우 빠르다!

최악의 경우에도 O(N + K)를 보장한다.(K: 데이터 중 최댓값)

하지만, 데이터의 크기 범위가 제한되어 정수 형태로 표현 가능할 경우에만 사용할 수 있다.

일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 사용 가능하다.

위에 해당하는 이유는 모든 범위를 담을 수 있는 크기의 배열을 선언해야 하기 때문이다.

방법:

가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담긴 하나의 리스트 생성 -> 리스트의 모든 데이터를 0으로 초기화 -> 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가

예시)

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

데이터 7에 해당하는 인덱스의 값을 1 늘려준다.

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

데이터 5에 해당하는 인덱스의 값을 1 늘려준다.

이를 반복하면 다음과 같다.

7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 횟수가 기록된다.

이것 자체가 정렬된 형태라고 볼 수 있다!

출력만 하면 완료됨!!

계수 정렬 소스코드)

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1    # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end = ' ')

# 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

시간 복잡도: O(N + K)

공간 복잡도: O(N + K)

계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 적합하다!

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

OO이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다.

캐릭터의 움직임을 설정하기 위해 정해놓은 매뉴얼은 이러하다.

1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.
2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.
3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

OO이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 매뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력조건

• 첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3<=N,M<=50)
• 둘째 줄에 게임 캐릭터가 잇는 칸의 좌표 (A, B)와 바라보는 방향 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.
  • 0: 북  1: 동  2: 남  3: 서
• 셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외곽은 항상 바다로 되어있다.
  • 0: 육지 1: 바다
• 처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력조건

• 첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

풀이)

이 문제는 전형적인 시뮬레이션 문제다!

내 풀이: #틀렸으니 주의!#

N, M = map(int, input().split())
x, y, now_direction = map(int, input().split())
full_map = []
for _ in range(N):
    detail_map = list(map(int, input().split()))
    full_map.append(detail_map)

# 반시계 방향이므로 북 서 남 동
direction = [0, 3, 2, 1]
# 순서대로 북, 서, 남, 동
moving = [[-1, 0], [0, -1], [1, 0], [0, 1]]
count = 1
next_direction = -1
turn_count = 0
full_map[x][y] = 2   # 처음 시작점은 방문했다고 함


for index, dir in enumerate(direction):
    if now_direction == dir:
        next_direction = direction[(index + 1) % 4]
        next_x = x + moving[(index + 1) % 4][0]
        next_y = y + moving[(index + 1) % 4][1]

        # 안 가본 육지면
        if full_map[next_x][next_y] == 0:
            now_direction = next_direction
            x = next_x
            y = next_y
            full_map[x][y] = 2  # 간 곳은 2로 표시
            count += 1
            turn_count = 0

        # 가보거나(2) 바다면
        elif turn_count < 4 and (full_map[next_x][next_y] == 2 or full_map[next_x][next_y] == 1):
            now_direction = next_direction
            turn_count += 1
            continue

        # 다 돌아봤는데 가본 칸일 때(turn_count = 4) 후진
        else:
            x = x - moving[index][0]
            y = y - moving[index][0]
            count += 1

print(count)

# 문제: 북으로 시작 안하면 망함.
# while문 사용해야함.

이 문제는 다시 풀어도 틀렸던 문제다. 다음에 다시 또 풀어봐야지!!

왼쪽으로 방향을 틀 때 어떻게 잡아야 할지 헷갈렸고, 전체 맵에서 방문한 육지를 어떻게 표현하고 조건에 따라 어떻게 이동할지 잘 정리를 못했다. 그리고 마지막으로 캐릭터를 이동시키는걸 어떻게 구현해야 하나 고민이 컸다. 이게 가장 중요한거지만ㅎㅎ

#정답 풀이#

N, M = map(int, input().split())
# 방문한 위치를 저장하기 위한 맵을 생성하여 0으로 초기화
d = [[0] * M for _ in range(N)]
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)

나는 반시계 방향으로 방향이 전환되니 방향 자체를 '북, 서, 남, 동'으로 해결하려 했는데 꼭 그럴 필요는 없었다.(그래서 index 이용하려 했지...) 오히려 문제에 나와있는대로 작성 후 if문 처리하면 쉽더라...;;

그리고 전체 맵을 array로, 방문했는지 체크하는 용도로 d를 만드는 것이 조건으로 체크하기 더 편했다. 다음에는 이렇게 이용해봐야지!

while문 내에서 왼쪽으로 회전한 이후(매뉴얼 1번) 크게 두 가지 케이스로 나눴다.

1. 가보지 않은 칸 존재
2. 가보지 않은 칸 존재하지 않음

특히 2번을 수행한 후 네 방향을 다 돌았는지 체크하기 위해 turn_time을 증가시킨다.(매뉴얼 2번)

만약 turn_time이 4일경우 네 면을 다 돌았는데도 불구하고 갈 수 없는 경우이므로 매뉴얼 3번에 해당한다. 따라서 이 경우는 전체 맵에서 뒤쪽 방향이 육지인지 확인 후 돌아가고 while문을 통해 매뉴얼 1번으로 다시 돌아간다! 만약 뒤가 바다라면 break를 통해 빠져나온다!

그리고 x, y 좌표를 변경하는 법!

이 부분이 항상 나는 헷갈리는 것 같다. 일단 이동을 하기 위해 각 방향별로 이동거리인 dx, dy를 생성해준다. 이때 좌표가 북과 서에서 떨어진 방향이므로 +, - 주의해야 한다!

다음 좌표인 nx, ny를 dx, dy를 이용하여 만들어준다. 이때 index는 현재 방향인 direction으로 이용하면 아주 편리하다. 

그리고 이동한다면 x, y를 nx, ny 값으로 변경해 주면 끝!

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

왕실 정원은 체스판과 같은 8x8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이처럼 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성ㅏ시오.

이때 왕실 정원에서 행 위치를 표현할 때는 1부터 8, 열 위치를 표현할 때는 a부터 h로 표현한다.

입력 조건

• 첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이루어진다.

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오

풀이)

행은 숫자로 받지만 열은 문자로 받으므로 아스키 코드를 이용해서 숫자로 만들어준다.

문제에서 이동할 수 있는 방법은 크게 2가지 였지만 수평으로 양 옆 이동, 수직으로 위 아래 이동을 모두 다 합하면 각 가짓수마다 4가지 이동 경우의 수가 나온다. 총 8가지 이므로 이것을 moving이라는 2차원 list로 저장해준다.

주어진 위치에서 모든 moving에 대하여 next_row, next_col에 각각 다음 행, 다음 열 위치를 저장해준다.

그리고 다음 위치가 8x8 체스판에서 벗어나는지만 확인해주고 count를 늘려주면 완료된다.

이 문제는 시뮬레이션 문제로 볼 수 있겠다.(주어진 이동 방법이 있으므로)

location = input()
row = int(location[1])
col = ord(location[0])-ord('a')+1
moving = [[2, 1], [2, -1], [-2, 1], [-2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2]]
count = 0
for move in moving:
    #next = [row, col] + move
    next_row = row + move[0]
    next_col = col + move[1]
    if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8:
        count += 1
print(count)

코드를 작성하다가 실수한 부분이 있었는데, list + list를 할 경우엔 list가 합쳐진 결과가 나온다.(ex: [1, 1] + [0, -1] = [1, 1, 0, -1])

각 요소가 더해진 결과가 나오지 않는다는 점!!! 기억하자!!!

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성해라.

입력 조건

• 첫째 줄에 정수 N이 입력된다.(0 <= N <= 23)

출력 조건

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

풀이)

모든 시각의 경우의 수를 세면 가능한 문제다. 즉, 이 문제는 완전 탐색 문제이다.

시간, 분, 초를 3중 반복문을 이용하여 3이 존재하는지 확인한다.

3이 존재하는지 확인하는 방법을 생각했을 때 int로는 확인하기 어려우므로 string으로 바꾸어서 시, 분, 초를 합친 후 3이 존재하는지 확인한다. 

예를 들어 03시 11분 05초의 경우 string으로 바꾸어 합치면 '3115'이므로 count 한다. (0을 꼭 포함해서 넣을 필요는 없으니까!)

N = int(input())
num = range(60)
count = 0
for i in range(N+1):
    for j in num:
        for k in num:
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

"이것이 코딩테스트다" 책 문제 _ 구현 문제

문제)

사람 A는 N x N 크기의 정사각형 공간위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이고, 가장 오른쪽 아래 좌표는 (N, N)이다. A는 상, 하, 좌, 우 방향으로 이동할 수 있고, 시작 좌표는 항상 (1, 1)이다.

이때 A가 이동할 계획이 적힌 계획서가 있는데, 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀있다. 이 문자의 의미는 다음과 같다.

• L: 왼쪽으로 한 칸 이동
• R: 오른쪽으로 한 칸 이동
• U: 위쪽으로 한 칸 이동
• D: 아래쪽으로 한 칸 이동

이때 A가 N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1) 위치에서 L 혹은 U를 만나면 무시된다.

입력 조건

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 <= N <= 100)
• 둘째 줄에 A가 이동할 계획서 내용이 주어진다. (1 <= 이동횟수 <= 100)

출력 조건

• 첫째 줄에 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

풀이)

1. 내 풀이

이 문제는 x, y 좌표만 계산을 해 주면 간단한 문제이다.

이때 주의할 점은 L, R은 y 좌표에 영향을, U, D는 x 좌표에 영향을 준다는 것이다. (일반적인 좌표평면이 아니라서 그렇다.)

따라서 반복문을 이용하여 계획서 내 L, R, U, D 각각에서 이동할 수 있는 조건에 해당하면 x, y좌표가 이동하도록 조건문을 작성했다.

N = int(input())
moving = input().split()

x = 1
y = 1

for i in moving:
    if y < N and i == 'R':
        y += 1
    elif y > 1 and i == 'L':
        y -= 1
    elif x > 1 and i == 'U':
        x -= 1
    elif x < N and i == 'D':
        x += 1

print(x, y)

2. 답지 풀이

이 문제는 구현 문제에서 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점에서 시뮬레이션에 해당한다. 

또한 연산 횟수가 이동 횟수에 비례하게 되어서 시간 복잡도가 O(N)이므로(이때, 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)

문제를 푸는 알고리즘은 내가 풀었던 방식과 같다. 하지만 풀이에선 L, R, U, D에 따른 이동 거리를 dx, dy로 만들어 주었고 nx, ny라는 변수에 이동한 좌표를 저장해 주었다. 공간을 벗어나지 않을 땐 nx, ny를 x, y로 갱신해주고, 공간을 벗어나는 경우에는 x, y를 갱신하지 않음으로써 예외처리를 해 주었다.