본문 바로가기

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

[Baekjoon] 2580번: 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 빈 칸에 들어갈 숫자를 구하는 과정까지는 빠르게 구현했는데, 백트래킹 알고리즘 구현에서 빈 칸에 들어갈 숫자를 실시간으로 구해서 대입했어야 하는데 그 부분을 실수해서 디버깅에 한참을 소비하고 말았당 문제 해결 과정 착안 빈 칸으로 표시된 칸마다 재귀적으로 현재 칸에 넣을 수 있는 숫자를 넣고, 넣을 수 있는 숫자가 없는 경우에는 이전 단계로 돌아가 다른 숫자를 넣도록 하는 백트래킹 알고리즘을 통해.. 2023. 12. 11.
[Baekjoon] 동전 뒤집기 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 해결 과정 착안 $N^2$ 개의 동전의 초기 상태로부터 뒷면(T)인 동전의 갯수가 최소가 되도록 행 또는 열을 뒤집는 경우를 찾기 위해서는 가능한 모든 경우를 확인해보아야 한다. 이때, 행이나 열을 뒤집는 동작을 수행할 때 선택된 행과 열 중에서 어느 것을 먼저 뒤집더라도 결과가 동일하므로, 편의상 항상 행을 먼저 다 뒤집은 다음에 열을 뒤집는 경우만 살펴볼 수 있다. 행 또는 열을 뒤집.. 2023. 12. 9.
[Baekjoon] 9084번: 동전 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 서로 다른 $n$ 가지 동전의 가치를 $c_1, c_2, \cdots, c_n$, 특정한 금액 $m$을 만들기 위한 경우의 수는 1) $c_1$ 짜리 동전만 사용하여 만드는 경우 (가능하다면) 2) $c_2$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) 3) $c_3$ 짜리 동전을 추가로 사용하여 만드는 경우 (가능하다면) $\cdo.. 2023. 12. 7.
[Baekjoon] 1063번: 킹 https://www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 문제 해결 과정 착안 킹을 움직였을 때, 돌과 위치가 겹쳐지는지의 여부에 따라 조건문 분기를 처리하는 데에 주의하여 문제에서 주어진 조건을 구현하고자 하였다. 구현 킹과 돌을 나타내는 구조체를 만들어 이동을 위한 메서드를 정의할 때 먼저 이동 여부를 판단하고, 이동 가능하다면 해당 위치로 이동시키는 메서드를 구현하였다. 이때 킹 또는 돌이 체스판 밖으로 밀려나는 경우는 이동을 수행하지 않으므로, 편의상 원위.. 2023. 12. 5.
[Baekjoon] 10830번: 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 해결 과정 착안 문제에서 행렬을 곱하는 횟수 $B$가 매우 커서 단순하게 행렬 하나씩 곱하며 계산하면 제한 시간 내에 문제를 해결할 수 없으므로, 자기 자신 행렬을 제곱할 때마다 지수가 2의 거듭제곱으로 증가하는 것을 활용하고자 하였다. 구현 우선 임의의 $n \times n \space (1 \le n \le 5) $ 크기의 정사각행렬 $M_1, M_2$를 곱하여 결과를 도출하는 함수를 구현하고 테스트한.. 2023. 12. 4.
[Baekjoon] 1068번: 트리 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 해결 과정 착안 트리 내의 $i$번째 노드에 대해 방문 여부를 표시하면서 삭제될 노드인지를 확인 및 표시하고, 이러한 과정을 부모 노드가 존재하는 경우 재귀적으로 반복 수행하고자 하였다. 구현 위의 방법과 같이 트리 내의 모든 노드에 대해 재귀적으로 상위 노드로 접근하는 경우는 중복된 노드를 계속해서 방문하게 되어 알고리즘의 시간 복잡도가 증가하게 되므로, 노드의 방문 여부를 별도로 표.. 2023. 12. 1.

티스토리툴바