C++ 코딩 문제 풀이/백준113 [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. [Baekjoon] 10866번: 덱 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 해결 과정 착안 덱(deque) 자료 구조는 double-ended queue를 의미하며, 양방향에서 데이터의 삽입 및 출력이 가능한 큐 자료 구조이다. 큐를 구현할 때와 마찬가지로 데이터의 입출력 과정에서 Front와 Rear 변수를 제어함으로써 덱 자료 구조를 표현하고자 하였다. 편의상 배열 형태로 구현하고자 하였고, Front, Rear 변수를 각각 현재 존재하는 데이터.. 2023. 7. 2. [Baekjoon] 4134번: 다음 소수 https://www.acmicpc.net/problem/4134 4134번: 다음 소수 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 과정 착안 소수를 빠르게 찾기하기 위한 유명한 알고리즘 중의 하나로 에라토스테네스의 체(Sieve of Eratosthenes) 라는 것이 있는데, 해당 알고리즘은 2 이상의 자연수부터 시작하여 어떤 자연수 $n \space (n \geq 2)$ 까지의 수들이 소수인지 아닌지를 판단하는 데에 유리한 방법이다. 그러나 위의 방법은 구하고자 하는 소수가 $n$보다 큰 경우에 활용하기가 어렵기 때문에 다른 방법을 이용하여 문제를 해결하고자 하였다. * 소수가 .. 2023. 7. 2. 이전 1 ··· 4 5 6 7 8 9 10 ··· 19 다음
