사람들을 눈뜨게 하고 새로운 세상을 열려고 한 어느 천재 소년의 경이로운 행적 기본 정보 1994년 발간된 히가시노 게이고의 SF 판타지 소설로 빛의 음악인 '광악'을 소재로 한다. 한국의 출간은 2014년, 재인공방에서 옮긴이 '김난주'역으로 출간되었다. 줄거리 어느 날 밤, 야경을 구경하던 서로 다른 이들에게 빛이 보이기 시작한다. 그 빛은 그저 조명의 빛 같았으나 여러 색으로 조금씩 점등과 점멸을 반복하며 꼭 그들에게 말을 거는 듯 했다. '이리 와요.' 라고. 시야 끝에서 무언가가 반짝거린 것은 그녀가 베란다 난간에 두 손을 걸쳤을 때였다. 그녀는 그쪽으로 얼굴을 돌렸다. 빛이 또 깜박거렸다. 반짝, 반짝, 반짝. 부드럽고 신비한 리듬이었다. 저 멀리서 빛나는 그 빛이 오직 자신만을 위해 깜박이는..

문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수..

문제 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 = ..