Problem Solving
[백준] 9372번 상근이의 여행 (feat. 그래프 이론, 최소 신장 트리)
[백준] 9372번 상근이의 여행 (feat. 그래프 이론, 최소 신장 트리)
2023.04.11https://www.acmicpc.net/problem/9372 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) - 문제 요약 N개의 국가를 여행하려고 함. 비행 스케줄이 주어졌을 때, 가장 적은 종류의 비행기를 탈 수 있도록 하는 프로그램을 작성할 것. 한 국가에서 다른 국가로 이동할 때, 다른 국가를 겨쳐 가도됨. - 입력 첫 번째 줄에는 테스트 케이스의 수 T(T
[백준] 20040번 사이클 게임 (feat. 자료 구조, 유니온 파인드)
[백준] 20040번 사이클 게임 (feat. 자료 구조, 유니온 파인드)
2023.04.04https://www.acmicpc.net/problem/20040 문제 분석 첫 번째 단계 (문제 요약 및 조건 파악) 사이클 게임은 두 플레이어가 차례대로 돌아가며 진행하는 게임. 선 플레이어가 홀수 번째 차례 진행 후 플레이어가 짝수 번째 차례 진행 게임 시작 시 0부터 n - 1 까지 고유한 번호가 부여된 평면상의 점 n개가 주어지며, 이중 어느 세 점도 일직선 위에 놓이지 않음.(그래프 형태라는 뜻으로 해석함) 매 차례마다 플레이어는 두 노드를 선택해 간선을 연결함. 이전에 있던 간선을 다시 그을수는 없지만, 이미 있는 간선과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하면 게임종료. 노드의 갯수 n과 m번쨰 차례 까지의 게임진행 상황이 주어지면, 사이클이 완성 되었는지를 ..
[백준] 11286번 절댓값 힙 (feat. 자료 구조, 우선순위 큐)
[백준] 11286번 절댓값 힙 (feat. 자료 구조, 우선순위 큐)
2023.04.02https://www.acmicpc.net/problem/11286 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 절대값 힙은 다음과 같은 연산을 지원하는 자료구조다. 1. 배열에 정수 x(x != 0)을 넣는다. 2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거 만약, 절댓값이 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거 단, 프로그램은 처음에 비어있는 배열로 시작. - 입력 첫째 줄에 연산의 개수 N(1
[백준] 1927번 최소 힙 (feat. 자료 구조, 우선순위 큐)
[백준] 1927번 최소 힙 (feat. 자료 구조, 우선순위 큐)
2023.04.01https://www.acmicpc.net/problem/1927 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) - 문제 요약 최소 힙을 이용하여 다음 연산을 지원하는 프로그램을 작성할 것. 1. 배열에 자연수 x를 넣는다. 2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. - 입력 첫째 줄에 연산의 개수 N(1
[백준] 11279번 최대 힙 (feat. 자료 구조, 우선순위 큐)
[백준] 11279번 최대 힙 (feat. 자료 구조, 우선순위 큐)
2023.03.31https://www.acmicpc.net/problem/11279 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성할 것. 1. 배열에 자연수 X를 넣는다. 2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작한다. - 입력 첫째 줄에 연산의 개수 N (1
[백준] 1516번 게임 개발 (feat. 위상 정렬, 다이나믹 프로그래밍)
[백준] 1516번 게임 개발 (feat. 위상 정렬, 다이나믹 프로그래밍)
2023.03.30https://www.acmicpc.net/problem/1516 문제 분석 첫 번째 단계(문제 요약 및 조건 파악) - 문제 요약 특정 건물을 짓기 전에 선행되어야 하는 건물이 존재. 모든 건물을 짓는데 걸리는 최소의 시간을 구해라. - 입력 첫째 줄에 건물의 종류 수 N(1 2번 건물 짓는데 걸리는 시간 10, 선수 건물 1번 건물. . . . - 출력 N개의 각 건물이 완성되기까지 걸리는 최소시간 출력 할 것. 두 번째 단계(문제 핵심 파악) 전형적인 위상정렬 문제로 판단된다.(선수 과목 문제와 비슷) 그런데, 출력조건을 잘 살펴보자. N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력해야한다. N개의 각 건물이 완성되는 시간에 대해서 생각해보자. 처음에 진입차수가 0인 건물은 건축 소요시간이 ..