문제 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할정복이란 큰 문제를 작은 문제로 나누어 해결하는 재귀적인 알고리즘이다. 일반적으로 세 단계로 구성된다. - 분할(Divide): 주어진 문제를 더 작은 부분 문제들로 분할한다. 부분 문제들은 원래 문제와 동일한 형태를 가진다. - 정복(Conquer): 부분 문제들을 재귀적으로 해결하여 부분 해를 구한다. - 통합(Combine): 작은 부분 문제들의 해를 결합하여 원래 문제의 해를 구한다. 문제는 분할정복을 활용하여 종..

문제 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 풀이 숫자야구는 일반적으로 세 자리나 네 자리의 숫자를 임의로 설정하여 상대방의 숫자를 맞추는 게임이다. 숫자를 맞추기 위해서는 서로에게 상대방의 숫자를 불러 결과를 확인한다. 결과는 숫자와 위치가 일치하면 스트라이크, 숫자는 맞지만 위치가 다르다면 볼로 판정하고 상대방에게 알려준다. 예를 들어 임의의 수가 456 이고 확인하는 수가 469 인 경우 1스트라이크 1볼이라고 상대방에게 알려준다. 만약 숫자가 하나도 맞지않는다면 아웃으로 처리하고, 3아웃이면 ..

문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 하노이의 탑 문제는 큰 부분을 작은 부분으로 나누어 해결하는 재귀적 접근으로 해결할 수 있다. 원판을 모두 목적지로 옮기기 위해서는 먼저 가장 큰 원판을 목적지로 옮겨야한다. 따라서 나머지 원판들을 목적지가 아닌 곳으로 옮긴다. 모두 옮기고 나면 가장 큰 원판을 목적지로 옮기고 그 후에 나머지 원판들을 목적지로 옮기면 된다. 위의 과정은 재귀를 이용해 해결할 수 있는데, 두번째로 큰 원판 또한 목적지로 옮기기위해 나머지 원판들을 목적지가 아..

문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 LectureTime 데이터 클래스를 정의하여 Comparable 인터페이스를 구현한다. 시작시간을 기준으로 오름차순 정렬하도록 고 만약 시작시간이 같다면 종료시간을 기준으로 정렬한다. 입력받은 시간을 LectureTime 배열에 저장하고 이 배열을 정렬해준다. 우선순위 큐를 선언하고 첫번째 수업의 종료 시간을 큐에 넣는다. 배열을 순회하면서 만약 현재 강의의 시작 시간이 우선순위 큐의 최상단의 강의의 종료 시간보다 작거나 같으면 해당 강의는 해당 강의실에서 진행 가능하므로 우선순위 큐에서 poll(..

문제 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 풀이 Boolean 배열 visited를 활용하여 초대 인원을 구하였다. 먼저, 인접리스트를 생성하고 입력받은 친구 관계를 기록한다. 그 후, 1번과 직접 연결된 리스트를 방문 표시하고, 이와 연결된 리스트들의 친구들도 방문 표시를 한다. 방문 배열에서 true로 표시된 개수에서 1(자기 자신)을 뺀 값이 초대할 친구의 수가 된다. 코드 fun main() { val br = System.`in`.bufferedReader() val bw =..