문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 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)부터 상, 하, 좌, 우로 탐색을 시작한다. 알고리즘 포스팅에..

우선, DFS와 BFS는 그래프를 순회하는 알고리즘이기 때문에 이 게시글에선 위 그래프를 예제로 사용하겠습니다. 간단하게 알아보자면 DFS는 Depth First Search, 깊이 우선 탐색이며 BFS는 Breadth First Search, 너비 우선 탐색이라고 알아두시면 되겠습니다. 탐색을 하려면 일단 그래프를 각 정점(vertex, v)들의 연결 상태를 나타내는 이중리스트(matrix)로 정의해야합니다. 매트릭스는 위와 같이 생겼습니다. 정점들의 연결상태를 우선 파란 칸(연결됨), 빨간 칸(연결되지 않음)으로 나누어 색칠하겠습니다. 먼저 자신이 자신과 연결되어있진 않으니 자신과 만나는 쌍을 전부 빨간색으로 색칠합니다. 다음은 이어진 점들의 쌍을 파란색으로 색칠합니다. 단, 간선의 방향이 없는 그래..

문제 입학 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), 속도인 (..