본문 바로가기

C++ 코딩 문제 풀이/백준113

[Baekjoon] 14889번: 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 해결 과정 착안 총 $N$ 명의 인원을 $(N / 2)$ 명씩 두 팀으로 나누는 모든 방법에 대하여, 능력치 값을 계산해보고 능력치 차이의 최솟값을 구하고자 하였다. 이때 팀 이름에 관계 없이 점수 차이만 계산하면 되므로, 중복하여 계산할 필요 없이 가장 처음 번호의 인원(1번 사람)은 반드시 첫 번째 팀에 포함된다고 가정할 수 있다(예를 들면 1번 사람이 속한 팀을 무조건 스타트 팀이라고 가정하는 것과 같음)... 2023. 7. 2.
[Baekjoon] 2630번: 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제 해결 과정 착안 분할 정복(divide and conquer) 알고리즘을 통해 정사각형 모양의 색종이가 균일한 색깔을 가지는지 확인하고, 균일한 색으로 이루어져 있지 않다면 동일한 크기의 4 개의 작은 색종이로 나누어가며 색종이 내부의 색깔이 일정한지 확인하는 과정을 반복하여 해결하고자 하였다. 구현 배열의 인덱스를 좌표와 같이 사용하여 색종이의 좌상단 좌표와 한 .. 2023. 6. 29.
[Baekjoon] 2805번: 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 해결 과정 착안 이전 포스트에서의 방법과 동일하게, 이진 탐색(binary search, 이분 탐색) 알고리즘을 응용하여 해결하고자 했다. 구현 직전의 포스트에서와 거의 유사한 문제이므로 구체적인 구현 내용은 생략하였다. 문제에서 주의할 점은 역시 정수 오버플로(integer overflow)를 염두에 두어 변수의 자료형을 사용해야 한다는 점과, 이진 .. 2023. 6. 27.
[Baekjoon] 1654번: 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 해결 과정 착안 캠프에서 사용할 랜선을 만들기 위해 목표로 하는 $N$ 개 이상의 랜선을 얻으면서, 가능한 최대의 랜선 길이를 구해야하므로 주어진 랜선 길이를 여러 번 잘라보며 최대 길이를 구해야 한다. 이때, 목표로 하는 $N$ 개 이상의 랜선을 만들기 위해 가장 작은 길이인 1부터 시작하여 랜선을 잘라 계산을 하다보면 주어지는 입력 값이 어떤지에 따라 랜선 길.. 2023. 6. 27.
[Baekjoon] 10814번: 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 문제 해결 과정 착안 가입한 사람들의 정보를 구조체를 활용해 저장한 뒤 이를 배열로 저장하여 정렬하고자 하였다. 나이가 같은 경우, 가입한 순으로 정렬하기 위해 별도로 가입한 순서를 표시하기 위한 변수를 구조체에 포함하였다. 구현 STL의 헤더에 포함된 std::sort() 함수를 사용하고, 정렬하는 기준을 람다 표현식(lambda expression)의 형태로 전달하여 구현하였다. [스포 주의] 아래.. 2023. 6. 25.
[Baekjoon] 1021번: 회전하는 큐 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 문제 해결 과정 착안 양방향에서 요소를 삽입(enqueue) 및 제거(dequeue) 할 수 있는 큐 자료 구조인 덱(deque) 자료 구조를 활용하는 것을 유도한 문제인 것 같은데, 다음과 같은 원리에 의해 한 방향으로만 요소를 삽입/제거하는 큐(queue) 자료 구조를 이용해도 문제를 해결할 수 있다. 덱의 크기를 $N$, 특정 요소를 맨 앞으로 보내기 위한 2번 연산의 실행 횟수를 $k_.. 2023. 6. 25.

티스토리툴바