본문 바로가기

C++ 코딩 문제 풀이151

[Baekjoon] 10866번: 덱 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 해결 과정 착안 덱(deque) 자료 구조는 double-ended queue를 의미하며, 양방향에서 데이터의 삽입 및 출력이 가능한 큐 자료 구조이다. 큐를 구현할 때와 마찬가지로 데이터의 입출력 과정에서 Front와 Rear 변수를 제어함으로써 덱 자료 구조를 표현하고자 하였다. 편의상 배열 형태로 구현하고자 하였고, Front, Rear 변수를 각각 현재 존재하는 데이터.. 2023. 7. 2.
[Baekjoon] 4134번: 다음 소수 https://www.acmicpc.net/problem/4134 4134번: 다음 소수 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 과정 착안 소수를 빠르게 찾기하기 위한 유명한 알고리즘 중의 하나로 에라토스테네스의 체(Sieve of Eratosthenes) 라는 것이 있는데, 해당 알고리즘은 2 이상의 자연수부터 시작하여 어떤 자연수 $n \space (n \geq 2)$ 까지의 수들이 소수인지 아닌지를 판단하는 데에 유리한 방법이다. 그러나 위의 방법은 구하고자 하는 소수가 $n$보다 큰 경우에 활용하기가 어렵기 때문에 다른 방법을 이용하여 문제를 해결하고자 하였다. * 소수가 .. 2023. 7. 2.
[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.

티스토리툴바