개발로그

문제 동빈이는 온라인으로 컴퓨터 공학 강의를 듣고 있다. 이때 각 온라인 강의는 선수 강의가 있을 수 있는데, 선수 강의가 있는 강의는 선수 강의를 먼저 들어야만 해당 강의를 들을 수 있다. 예를 들어 '알고리즘' 강의의 선수 강의로 '자료구조'와 '컴퓨터 기초'가 존재한다면, '자료구조'와 '컴퓨터 기초'를 모두 들은 이후에 '알고리즘' 강의를 들을 수 있다. 동빈이는 총 N개의 강의를 듣고자 한다. 모든 강의는 1번부터 N번까지의 번호를 가진다. 또한 동시에 여러 개의 강의를 들을 수 있다고 가정한다. 예를 들어 N=3일 때, 3번 강의의 선수 강의로 1번과 2번 강의가 있고, 1번과 2번의 선수 강의는 없다고 가정하자. 그리고 각 강의에 대하여 강의 시간이 다음과 같다고 가정하자. 1번 강의 : 3..

문제 동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 머리를 맞대고 회의 중이었다. 마을은 N개의 집과 그 집을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가..

문제 학교에서 학생들에게 0번부터 N번까지 번호를 부여했다. 처음에는 모든 학생이 서로 다른 팀으로 구분되어 총 N+1개의 팀이 존재한다. 이때 선생님은 '팀 합치기' 연산과 '같은 팀 여부 확인' 연산을 사용할 수 있다. 1. 팀 합치기 연산은 두 팀을 합치는 연산이다. 2. 같은 팀 여부 확인 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, 같은 팀 여부 확인 연산에 대한 연산 결과를 출력하는 프로그램을 작성하시오. 입력조건 첫째줄에 N, M이 주어진다. 둘째줄부터 M+1번째 줄까지 각각의 연산이 주어진다. 팀 합치기 연산은 0 a b 형태로 주어진다. 같은 팀 여부 확인 연산은 1 a b 형태로 주어진다. 출력 조건 같은 팀 여부 확인 ..

서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조다. 연산 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할 수 있다. union 연산은 2개의 원소가 포함된 집합을 하나로 합치는 연산이고, find 연산은 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산이다. 서로소 집합 자료구조 서로소 집합 자료구조에서 집합을 표현하는 서로소 집합 계산 알고리즘은 다음과 같다. 1. union 연산을 확인해, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 노드 A'와 B'를 찾는다. A'를 B'의 부모 노드로 설정한다. 2. 모든 union 연산을 처리할 때까지 1번 과정을 반복한다...

문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 하면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. X->Y가 있지만 Y->X가 없는 경우 Y에서 X로 메시지를 보낼 수 없다. 어느날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는데까..

문제 방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다. 공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다. 또한 연결된 2개의 회사는 양방향으로 이동할 수 있다. 공중 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정 회사와 다른 회사가 도로로 연결되어 있다면, 정확히 1만큼의 시간으로 이동할 수 있다. 또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다. 방문 판매원 A..

문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. 입력 조건 첫째 줄에 N, M이 주어진다. (1

문제 가로의 길이 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 X 3 크기의 바닥을 채우는 경우의 수는 5가지이다. 입력 조건 첫째 줄에 N이 주어진다. 출력 조건 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다. 풀이 N = 1일 때, 2 X 1 1가지 N = 2일 때, (2 X 1) X 2, (1 X 2) X 2, (2 X 2) 3가지 N = 3일 때, (2 X 1) + (2 X 2), (2 X 2) + (2 X 1), (2 X 1) X 3, (2 X 1) + ..

문제 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량 창고 4개가 다음과 같이 존재한다고 가정하자. { 1, 3, 1, 5 } 이때 개미 전사는 두번째 식량창고와 네번째 식량창고를 선택했을 때 최대값인 총 8개의 식량을..

문제 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. a. X가 5로 나누어 떨어지면 5로 나눈다. b. X가 3으로 나누어 떨어지면 3으로 나눈다. c. X가 2로 나누어 떨어지면 2로 나눈다. d. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최소값이다. 1. 26 - 1 = 25 (d) 2. 25 / 5 = 5 (a) 3. 5 / 5 = 1 (a) 입력 조건 첫째 줄에 정수 X가 주어진다. 출력 조건 연산을 하는 횟수의 최소값을 출력한다. 풀이 a와 d 조건만 있다면, a가 먼저 가능한지 확인하고 안되면 d를 진..