C++ 코딩 문제 풀이151 [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. [Baekjoon] 1780번: 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 해결 과정 착안 이전 포스트에서의 분할 정복(divide and conquer) 알고리즘 문제와 해결 방법이 유사하여 해당 코드를 변형하여 문제를 해결하였다. 정사각형 모양의 색종이가 균일한 색깔을 가지고 있는지 판단하여, 그렇지 않다면 가로를 3등분, 세로를 3등분한 다음, 동일한 크기의 9 개의 작은 색종이에 대해 다시 균일한 색깔을 가지는지 판단하는 과정을 반복하여 문제를 해.. 2023. 7. 5. [Baekjoon] 1992번: 쿼드 트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 해결 과정 착안 주어진 데이터가 0 또는 1의 값으로 균일한지 판단하고, 균일하지 않다면 주어진 데이터를 4 개의 균등한 영역으로 나눈 다음 각각의 영역이 다시 0 또는 1의 값으로 균일한지 판단하는 분할 정복(divide and conquer) 알고리즘의 코드를 작성하여 문제를 해결하고자 했다. 구현 주어진 영역이 0 또는 1의 값으로 균일한 상태인지 판단하는 함수를 구현하여 .. 2023. 7. 4. [Baekjoon] 14891번: 톱니바퀴 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 해결 과정 착안 문제에서 요구하는 출력 형식에서 힌트(?)를 얻었는데, 톱니바퀴의 각 8 개 톱니의 N극, S극 상태를 비트 형태로 저장하고 비트 연산(bitwise operation)을 활용하여 문제를 해결하고자 하였다. 비트 연산을 사용하고자 한 곳은 아래와 같다. 톱니바퀴 정보에 대한 입력 처리 톱니바퀴의 회전 이웃한 톱니바퀴가 서로 맞물려 있는지를 판정 문제에서 출력으로 요구하는.. 2023. 7. 3. [Baekjoon] 11279번: 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 해결 과정 착안 힙 트리(heap tree) 자료 구조는 최대 또는 최소를 찾아내는 연산을 빠르게 수행하기 위해 고안된 완전 이진 트리(complete binary tree) 형태의 자료 구조이다. 최대 힙의 특성에 따라 문제에서 요구하는 동작을 구현하여 문제를 해결하고자 하였다. 완전 이진 트리 형태의 자료 구조 특성상, 배열 형태로 구현하면 부모와 자식 노드를 나타.. 2023. 7. 2. 이전 1 ··· 10 11 12 13 14 15 16 ··· 26 다음
