C++ 코딩 문제 풀이151 [Baekjoon] 11399번: ATM https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 해결 과정 착안 뒤에서 기다리는 사람이 돈을 인출하려면 자신보다 앞 번호에 대기 중인 사람들이 모두 돈을 인출해야하므로, 각 사람이 돈을 인출하는데 필요한 시간의 총합을 최소로 하기 위해서는 인출하는 시간이 짧은 사람을 앞에 배치하여야 한다. 따라서, 우선순위 큐(priority queue) 자료 구조를 이용하여 인출하는 시간의 정보를 저장한 다음, 최소 인출시간인 사람부터 순차적으로 우선순위 큐에서 추출하는 방식을 활용.. 2023. 7. 13. [Baekjoon] 2110번: 공유기 설치 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 해결 과정 착안 공유기를 설치했을 때 가장 인접한 두 공유기 사이의 거리의 최댓값을 찾기 위해, 이진 탐색(binary search, 이분 탐색)을 응용하여 문제를 해결하고자 하였다. 구현 입력받은 $N$ 개의 집 좌표를 배열 Houses[]에 저장하여 오름차순으로 정렬하면, 가장 인접한 두 공유기 사이의 거리를 $c$ 라고 했을 때 설치하.. 2023. 7. 12. [Baekjoon] 1927번: 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해결 과정 착안 힙 트리(heap tree) 자료 구조는 최대 또는 최소를 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전 이진 트리(complete binary tree) 형태의 자료 구조이다. 최소 힙의 특성에 따라 문제에서 요구하는 동작을 구현하여 문제를 해결하고자 하였다. 이전 포스트에서 유사한 내용(최대 힙)을 다루었기 때문에 이번 포스트에서는 구체적인 내용은 .. 2023. 7. 11. [Baekjoon] 14500번: 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해결 과정 착안 표현 가능한 테트로미노의 경우의 수는 아래의 그림과 같이 총 19 가지이므로, 이에 대한 경우의 수를 모두 계산해봄으로써 문제를 해결하고자 하였다. 위와 같이 매우 다양한 테트로미노 케이스에 대해 일일이 계산하는 함수를 작성하여 문제를 해결하는 것은 비효율적이라고 판단하였다. 따라서, 어느 정도의 중복 계산을 허용하기로 하고 깊이 우선 탐색(depth-first search).. 2023. 7. 11. [Baekjoon] 20920번: 영단어 암기는 괴로워 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 문제 해결 과정 착안 문자열을 키로 가지며, 등장하는 빈도 수를 값으로 저장하여 문제를 해결하고자 std::map과 같은 컨테이너를 활용하고자 하였다. 이때 키의 자료형이 문자열 형이므로 해시 테이블(hash table)을 사용하는 것이 일반적으로 속도 측면에서 유리하기 때문에 std::unordered_map 클래스를 사용해 데.. 2023. 7. 9. [Baekjoon] 2108번: 통계학 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 해결 과정 착안 숫자가 입력된 빈도를 나타내기 위한 보조 배열을 선언하여 사용하며, 입력받는 수를 배열에 저장한 다음, 오름차순으로 정렬하여 문제를 해결하고자 하였다. 구현 아래와 같이 입력받는 $n$개의 수를 저장한 다음 오름차순으로 정렬하면 간단하게 문제 해결이 가능하다. 산술평균: 입력받을 때마다 합을 계산하여 마지막에 $n$으로 나누어 계산(-0 처리에 주의). 중앙값: 정렬된 배열의 중간 인덱스 .. 2023. 7. 8. 이전 1 ··· 9 10 11 12 13 14 15 ··· 26 다음
