C++ 코딩 문제 풀이/백준113 [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. [Baekjoon] 1916번: 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해결 과정 착안 음의 가중치 간선이 존재하지 않으며 방향이 있는 그래프에 대한 최단 경로 탐색을 요구하는 문제이므로, 최단 경로 탐색 알고리즘 중 하나인 데이크스트라 알고리즘(Dijkstra's algorithm)을 사용하여 문제를 해결하고자 했다. 구현 데이크스트라 알고리즘을 정상적으로 구현했음에도 불구하고 시간 초과가 발생하여 한참 고민하다가 질문 게시판.. 2023. 7. 7. [Baekjoon] 2156번: 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 해결 과정 착안 이전에 풀었던 코딩 문제 중, 유사한 문제가 있는데 동적계획법(dynamic programming)을 통해 문제를 해결할 수 있다는 점은 동일하지만 문제에서 주어지는 규칙이 약간 달라 이 부분에 유의하여 문제를 해결하고자 하였다. 문제에서 요구한 규칙을 지키면서 최대한 많은 양의 포도주를 마시는 경우를 생각해보면 포도주 잔을 연속해서 3 잔을 마실 수 없다. 최대한 많은 잔을 .. 2023. 7. 6. 이전 1 ··· 3 4 5 6 7 8 9 ··· 19 다음
