C++ 코딩 문제 풀이151 [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. [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. 이전 1 ··· 12 13 14 15 16 17 18 ··· 26 다음
