C++ 코딩 문제 풀이/백준113 [Baekjoon] 10816번: 숫자 카드 2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 문제 해결 과정 착안 (최초 접근 방법) STL의 헤더에 포함된 std::unordered_map 클래스를 활용하여 입력되는 숫자를 키, 반복되는 개수를 값으로 가지도록 구현하고자 하였다(기본 오버로딩 되어있는 [] 연산자 활용). (다른 접근 방법) 이전에 다른 문제들을 풀어보는 동안 숫자형 키 값을 사용할 때 std::unordered_map 클래스를 사용하.. 2023. 6. 25. [Baekjoon] 2331번: 반복수열 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 과정을 통해 숫자를 만들어 어떠한 컨테이너에 요소로서 순차적으로 추가하여 수열을 만든다고 가정하면, 반복수열이 처음 형성되는 숫자가 입력되는 순서가 몇 번째인지만 알면 반복수열을 제외한 수열의 길이를 쉽게 알 수 있다. 이를 구현하기 위해 중복된 키 값을 허용하지 않는 컨테이너인 std::unordered_map 클래스를 활용하고자 하였다. Key 는 만들어지는 숫자로, Value는 해당 숫자가 몇 번째로 입력받는지를 계산하여 해당 컨테이너에 추가하고자 하였다. try_.. 2023. 6. 22. [Baekjoon] 1931번: 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결 과정 착안 문제를 처음 접하고 어떻게 해결할 지 막연해서 꽤 오래 고민을 했다. 최대한 많은 회의에 대해 회의실을 배정하려면 어떻게 해야할지 열심히 생각해보다가, 아래와 같은 조건들이 문제 해결의 핵심이라고 생각을 했다. 처음 생각한 조건 회의 시간이 짧은 회의들을 가능한 한 많이 배정한다. 회의실이 비는 시간을 최소로 한다(단, 회의실 배정 가능한 시간에 대해 별도의 제약이 없음에 유의) 위의 조건을 만족하면서 회의를 순차적으로 배정하다보면 결과적으로 최대한 많은 회의에 대해 회의실을 배정할 수 있을.. 2023. 6. 21. [Baekjoon] 10844번: 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해결 과정 착안 문제에서 말하는 계단수의 특성을 활용하여 동적계획법(dynamic programming)을 통해 계산하고자 하였다. 길이가 $n (n \geq 2)$ 인 계단수를 만들기 위해서는 길이가 $(n-1)$인 계단수의 맨 뒤 자릿수에 숫자 하나를 붙여 새로운 계단수를 만드는 과정을 생각해볼 수 있다. 이때 길이가 $(n-1)$인 계단수의 뒤에 이어붙이는 숫자가 0인 경우: 길이가 $(n-1)$인 계단수 중, 끝자리가 0인 수의 뒤에만 붙일 수 있다. 9인 경우: 길이가 $(n-1)$인 계단수 중,.. 2023. 6. 20. [Baekjoon] 2559번: 수열 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 문제 해결 과정 착안 $n$ 번째 숫자 $a_n$ 부터 $(n+K-1)$ 번째 숫자 $a_{n+K-1}$ 까지 연속된 $K$ 개의 숫자를 더한 값을 $S_n$ 이라고 하면, $$S_{n+1} = S_n + a_{n+K} - a_n \quad(n \geq 1,\space 2 \leq K \leq N)$$ 이므로, 이전 단계의 합의 값을 알면 숫자 두 개만 더하고 뺌으로써 다음 번째의 연.. 2023. 6. 18. [Baekjoon] 1966번: 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 해결 과정 착안 얼핏 보았을 때 우선순위 큐와 같은 동작인 것처럼 보이나, 현재 문서의 우선순위보다 우선순위가 높은 문서가 큐에 하나라도 있는 경우 현재 문서를 큐의 가장 뒤쪽으로 보내는 작업 때문에 std::priority_queue 클래스를 사용해봤자 해결에 별 도움이 되지 않을 것이라 판단하였다. 본래 큐 클래스는 Front의 값에 대해서만 확인 가능하고 큐의 중간에 있는 요소들은 접근할 .. 2023. 6. 17. 이전 1 ··· 6 7 8 9 10 11 12 ··· 19 다음
