본문 바로가기

Algorithm144

[백준] 1074 Z (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 현재 주어진 2차원 배열을 4사분면으로 쪼갠 후, 각 사분면에 대해 다시 또 4사분면으로 쪼개면서 각 사분면이 1칸이 될 때 까지 계속 쪼갠 후 방문 순서를 정하는 문제이다. 결국, 내가 입력한 r행 c열을 몇 번째로 방문하는지 구하는 문제이다. 풀이 과정 여기서 주의깊게 봐야할 점은 항상 왼쪽위(1사분면) -> 오른쪽위(2사분면) -> 왼쪽아래(3사분면) -> 오른쪽아래(4사.. 2021. 9. 21.
[백준] 1780 종이의 개수 (Python 파이썬) https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 설명 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종.. 2021. 9. 19.
[백준] 1992 쿼드트리 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 위 링크의 문제 설명을 보고 문제를 이해하기 어려울 수 있는데, 한 구역안에 점들이 모두 같은 숫자로 이루어져있지 않으면 왼쪽 위-> 오른쪽 위-> 왼쪽 아래 -> 오른쪽 아래 순 (지그재그 모양)으로 나누어 나타낸다는 것을 이해하면 쉽다. 풀이 과정 이 문제는 큰 구역을 작은 구역으로 계속 쪼개어 나타내는 분할 정복 문제이다. 문제의 예시처럼, 다음과 같은 배열이 주어졌을.. 2021. 9. 19.
[백준] 2447 별 찍기 - 10 (Python 파이썬) https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 설명 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기.. 2021. 9. 17.
[백준] 2133 타일 채우기 (Python 파이썬) https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 설명 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 풀이 과정 먼저, 벽을 체울 수 있는 경우의 수를 구해보자. 벽의 가로길이가 홀수라면 벽을 가득 체울 수 없다. 예를 들어, N = 1 이라면 아래 한 칸이 남기 때문에 벽을 체울 수 없다. (타일은 2x1과 1x2만 존재하기 때문에) N = 2 일때는 다음과 같이 3가지 경우의 수가 존재한다. N = 4 일 때는 가로를 반으로 나눠 N = 2가 2개 있다고 생각할 수 있다. 그래서 앞의 3가지 x 뒤의 3가지 = 9.. 2021. 9. 14.
[백준] 2098 외판원 순회 (Python 파이썬) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 설명 자세한 문제 설명은 위 링크를 참조해 주세요 1번부터 N번까지의 도시가 있고, 어느 한 도시를 출발하여 모든 도시를 찍고 다시 출발지점으로 돌아오는데 드는 최소 비용을 구하는 문제이다. 풀이 과정 이 문제는 비트마스킹 + DP + DFS 를 모두 활용하는 문제로 난이도가 있는 문제이다. 각 도시를 방문했는지의 여부는 비트마스킹( 0001, 0002 .. 2021. 9. 14.

티스토리툴바