본문 바로가기

C++ 코딩 문제 풀이/백준113

[Baekjoon] 1629번: 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 해결 과정 착안 단순하게 반복적으로 같은 수를 곱하며 거듭제곱을 계산하면 지수 $E$에 대해 $O(E)$의 시간 복잡도를 소요하므로, 재귀를 활용하여 지수를 절반씩 줄여나가 $O(\log E)$의 시간 복잡도로 계산하고자 하였다. 한편, 나머지 연산(modulo operation)의 특성에 따라 다음과 같은 성질들이 성립함을 이용하였다. 자연수 $A, B, C$에 대하여 $A$를 $C$로 나눈 나머지를 $a \space (0 \leq a < C)$ 라고 할.. 2023. 7. 31.
[Baekjoon] 13305번: 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 해결 과정 착안 아래와 같이 탐욕(greedy) 알고리즘에 기반하여 문제를 해결할 수 있다. 현재 위치해 있는 도시의 주유 비용을 기준으로 삼는다. 순차적으로 우측 도시를 탐색하며 현재 도시의 주유 비용보다 주유 비용이 더 저렴한 도시를 탐색한다. 탐색에 성공하면, 현재 도시에서 주유하여 해당 도시까지 한 번에 이동한다. 탐색에 실패하면, 현재 도시에서 마지막 도시까지 한 번에.. 2023. 7. 28.
[Baekjoon] 16234번: 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 과정 착안 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 응용하여 날짜 별로 연합이 존재할 수 있는지 탐색해보고, 연합이 존재한다면 각 연합 별로 연합에 속하는 나라들의 인구를 산술평균 값으로 갱신하는 과정을 통해 문제를 해결하고자 하였다. 연합이 존재할 수 있는지 판단하는 과정에서, 인접한 나라와 직접적으로 국경선이 개방되어 연결되지 않더라도.. 2023. 7. 26.
[Baekjoon] 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 해결 과정 착안 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)에 따라 문제에서 요구하는 도시 간 거리를 계산하고자 하였다. 음수 가중치 간선이 없기 때문에 일반적인 방법으로 문제를 해결하고자 하였다. 구현 알고리즘을 구현함에 있어서, 삼중 반복문의 루프 변수 배치 순서 및 시작 도시와 도착 도시 사이의 연결이 없는 경우를 0으로 표시하는 부분에 유의하여 프로그래밍 하였.. 2023. 7. 25.
[Baekjoon] 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 과정 착안 주어지는 $n$개의 동전의 가치를 편의상 각각 $c_i \space (1 \leq i \leq n)$라고 하면, 종류가 다른 동전이 하나하나 주어질 때마다 아래와 같은 원리에 의해 단계별로 사용하는 동전의 수를 늘려가면서 가치의 총 합이 $k$ 이하의 자연수가 되도록 만드는 경우의 수를 귀납적으로 구할 수 있다. [전제조건] 1) 동전들을 사용하여 만들 수 있는 가치의 총 합은.. 2023. 7. 24.
[Baekjoon] 2447번: 별 찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 해결 과정 착안 메모리를 절약할 수 있는 더 좋은 방법이 있을 수 있지만, 간편한 방법으로 문제를 해결하고자 하였다. 프랙탈(fractal) 형태를 먼저 재귀적으로 구하여 저장한 다음, 한 행씩 문자열로 변환하여 출력해 문제를 해결하고자 하였다. 구현 프랙탈 모양의 형태를 최대한 적은 메모리를 사용해 저장해보려고 bool 형 배열을 이용해보았다. 별이 찍히는 부분을.. 2023. 7. 24.

티스토리툴바