이것저것 개발 블로그

정렬(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)

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

"이것이 코딩테스트다" 책 문제 _ DFS/BFS 문제

문제)

NxM 크기의 직사각형 형태의 미로가 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구해라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력조건

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력조건

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

풀이)

이 문제는 BFS 문제로 해결했다! (1, 1)에서 시작하여 주변을 탐색하며 1이 있는 부분을 택해서 가기 때문에 모든 노드를 탐색하므로 BFS가 편리하다고 생각했다. 사실 BFS로 해결을 하는 부분까진 감을 잡았는데 최소 이동 칸의 개수를 세는 방법을 잘 캐치를 못했다.

코드는 다음과 같다.

from collections import deque
N, M = map(int, input().split())
maze = []
for i in range(N):
    maze.append(list(map(int, input())))

# 첫 번째 칸 무조건 포함
count = 1
# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

#bfs
def bfs(x, y):
    que = deque()
    que.append((x, y))
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if maze[nx][ny] == 0:
                continue
            if maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1
                que.append((nx, ny))
    return maze[N-1][M-1]


print(bfs(0, 0))
print(maze)


# 결과: 10
# maze
# [[3, 0, 5, 0, 7, 0], 
#  [2, 3, 4, 5, 6, 7], 
#  [0, 0, 0, 0, 0, 8], 
#  [14, 13, 12, 11, 10, 9], 
#  [15, 14, 13, 12, 11, 10]]

노드를 방문했을때 길이 존재한다면 '이전 노드 값 + 1'을 저장한다!

맨 마지막 노드까지 bfs를 진행한다면 맨 마지막 노드에는 전체 거리 값이 저장된다.

다만 여기에서 maze 전체를 출력해본 값을 본다면 알 수 있듯이 시작 위치가 1이 아닌 3으로 변경된다.

왜냐하면 코드 상에서는 첫 번째 노드를 다시 방문할 수 있게 되어있기 때문이다!!

하지만 문제를 푸는 데에는 이상이 없기 때문에 참고 사항으로 알아두면 좋을 것 같다.

"이것이 코딩테스트다" 책 문제 _ DFS/BFS 문제

NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생서오디는 총 아이스크림의 개수를 구하는 프로그램을 작성해라.

예시) 4x5 얼음틀 : 아이스크림 3개 생성

입력조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다.(1 <= N, M <= 1000)
• 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려잇는 부분은 0, 그렇지 않은 부분은 1이다.

출력조건

• 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

풀이)

이 문제는 DFS로 풀어보았다! 전형적인 문제가 아닐까 생각한다.

N, M = map(int, input().split())
ice = []
for i in range(N):
    ice.append(list(map(int, input())))


def dfs(x, y):
    global N, M
    if x < 0 or x >= N or y < 0 or y >= M:
        return False
    if ice[x][y] == 0:
        ice[x][y] = 1
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

count = 0
for i in range(N):
    for j in range(M):
        if dfs(i, j) == True:
            count += 1

print(count)

얼음판 ice 구조를 이중 list로 저장해주고, (0, 0)부터 차례로 순회한다.

순회할때는 좌표 범위를 확인하고 0일경우 1로 바꿔준다.

dfs를 실행중인 좌표 기준으로 좌, 우, 상, 하를 똑같이 dfs로 순회한다.

return 값이 True로 끝나면 순회 완료! False 일 경우는 범위를 넘었거나 1인 경우이다.

또한 BFS로도 풀어보았다!!! (책은 DFS에 해당하는 풀이만 나와있다.)

from collections import deque

N, M = map(int, input().split())
ice = []
for i in range(N):
    ice.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(i, j):
    queue = deque()
    if ice[i][j] == 0:
        queue.append([i, j])
        while queue:
            x, y = queue.popleft()
            for p in range(4):
                nx = x + dx[p]
                ny = y + dy[p]
                if 0 <= nx < N and 0 <= ny < M:
                    if ice[nx][ny] == 0:
                        ice[nx][ny] = 1
                        queue.append([nx,ny])
                    else:
                        continue
                else:
                    continue
        return 1
    else:
        return 0



count = 0
for i in range(N):
    for j in range(M):
        count += bfs(i, j)
print(count)

좌, 우, 상, 하 이동을 dx, dy를 생성하여 만들었다. dfs와 같이 순회는 (0, 0) 부터 시작한다.

Ice가 0일 경우만 queue에 삽입 후 bfs를 진행하고, 아닐 경우는 없는 경우로 판단해 return 0한다.

다음 좌표의 ice가 0일 경우 1로 바꾸고 queue에 삽입한다. 이것을 queue가 다 끝날때까지 반복!

queue가 다 끝나면 해당 좌표의 bfs가 끝난 것이므로 1을 return해준다.

그리고 bfs 개수를 모두 더해주면 끝!!

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

문제)

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)