문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 풀이 먼저, 문제에 있는 표를 배열로 나타내어 그래프라고 생각하고, 시작 노드인 (0, 0)부터 상, 하, 좌, 우로 탐색을 시작한다. 알고리즘 포스팅에..
전 시간에는 트리와 그래프를 순회하여 알고리즘이 어떻게 작동하는지 알아보았습니다. 이번엔 직접 코드로 옮겨봅시다. BFS 소스코드 def BFS(start): visit = [] queue = [] queue.append(start) visit.append(start) while queue: now_node = queue.pop(0) print(now_node, end='') for i in range(7): if matrix[node][i] == 1 and not i in visit: queue.append(i) visit.append(i) BFS 방식으로 그래프를 순회하는 소스코드입니다. matrix는 1차시에서 만들어둔 그래프를 사용하시면 되겠습니다. 먼저, 매개변수로 시작 정점을 입력받습니다. 시..
전 시간에 보았던 이 그래프를 탐색하는 방법에 들어가기 전에, DFS와 BFS를 좀 더 쉽게 이해시켜줄 '이진 트리'를 DFS와 BFS로 탐색해봅시다. 트리 순회 - BFS 더 간단한 BFS먼저 보도록 하겠습니다. 시작 노드는 늘 그렇듯 1번입니다. BFS의 경우는 너비 우선 탐색이라는 이름에 걸맞게 현재 노드의 자식노드를 전부 행선지에 넣고, 다음 노드에서도 반복하는 방식인데요, 그림으로 한번 보겠습니다. 1번 노드를 방문합니다. 다음 행선지는 2와 3이 되겠네요. 2번 노드를 방문합니다. 마찬가지로 2의 자식인 4와 5를 행선지에 추가합니다. 3번 노드를 방문합니다. 3의 자식은 6과 7을 행선지에 추가합니다. 이후 순차적으로 방문합니다. 한 그림으로 정리하면 다음과 같습니다. 다음과 같이, 1-2-..
우선, DFS와 BFS는 그래프를 순회하는 알고리즘이기 때문에 이 게시글에선 위 그래프를 예제로 사용하겠습니다. 간단하게 알아보자면 DFS는 Depth First Search, 깊이 우선 탐색이며 BFS는 Breadth First Search, 너비 우선 탐색이라고 알아두시면 되겠습니다. 탐색을 하려면 일단 그래프를 각 정점(vertex, v)들의 연결 상태를 나타내는 이중리스트(matrix)로 정의해야합니다. 매트릭스는 위와 같이 생겼습니다. 정점들의 연결상태를 우선 파란 칸(연결됨), 빨간 칸(연결되지 않음)으로 나누어 색칠하겠습니다. 먼저 자신이 자신과 연결되어있진 않으니 자신과 만나는 쌍을 전부 빨간색으로 색칠합니다. 다음은 이어진 점들의 쌍을 파란색으로 색칠합니다. 단, 간선의 방향이 없는 그래..
문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로..
문제 입학 OT때 누구보다도 남다르게 놀았던 당신은 자연스럽게 1학년 과대를 역임하게 되었다. 타교와의 조인트 엠티를 기획하려는 당신은 근처에 있는 학교 중 어느 학교가 술을 가장 많이 먹는지 궁금해졌다. 학교별로 한 해동안 술 소비량이 주어질 때, 가장 술 소비가 많은 학교 이름을 출력하여라. 풀이 이 문제는 이중리스트나 튜플로도 풀 수 있지만 나는 평소에 잘 안썼던 딕셔너리로 풀어보고 싶어져서 그렇게 풀었다. 먼저, 딕셔너리의 '키'로 술 소비량인 L을 저장하고, 값으로 학교 이름을 저장한다. (반대로 해도 되지만 이 편이 출력하기 편하다) 키를 하나씩 반복하면서 제일 큰 키 값을 찾고 대응되는 값(학교명)을 출력한다. for T in range(int(input())): dic = {} max = ..
문제 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다. "OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다. OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오. 풀이 막힘 없이 풀다가 맞은 개수에 따라서 점수가 오르는게 아닌 연속 정답 수에 따라서 점수가 오르는걸 깨닫고 코드 몇 부분을 수정해야 했다. 내가 생각한 방법은 이러하다. 점수 뿐 아니라 '스택'이라는 변수를 따로 만들어서 정답일때마다 스택을 1씩 올려주고, 틀렸을때는 0으로 초기화한다. 물론 점수는 그때그때 스택으로만..
문제 최백준은 음하철도 구구팔에 탔다. 문제는 구구팔의 기장인 조교 김재홍이 반쯤 미쳐서 열차를 멈추지 않는다는 것이다. 그래서 최백준은 달리고 있는 열차에서 뛰어내려야 한다. 그런데 뛰어내릴 때 정류장 까지 거리가 너무 멀면 마이 아플 수 있다. 그래서 철도가 정류장에 가장 많이 근접했을 때 뛰어내리고자 한다. 어디서 뛰어내려야 하는가? 풀이 처음에 예제를 보고 의아했다. 처음 위치인 (2, 1)에서 (2, 4)의 속도로 움직이는데 최백준 씨는(3, 3)에서 뛰어내렸다. 즉, (2, 1)에서 (1, 2)만큼 이동한 위치에서 뛰어내리신 것. 따라서 속도를 공약수로 나눌 필요가 있었고, 함수 f를 정의했다. 차례차례 주어지는 입력값을 각각 정류장의 위치인 (x, y), 현재 위치인 (X, Y), 속도인 (..