AndroidTeacher

문제 설명

https://www.acmicpc.net/problem/2448

문제의 별찍기 패턴을 보고 규칙을 유추하여 코드를 작성하는 문제이다.

풀이 과정

먼저, 백준에서 정답을 얻기 위해서는 공백을 포함한 그래프 전체를 출력해야 한다.

( 이 부분은 백준님이 정답코드를 잘못 기입하신 문제라고 한다. )

즉, N=24인 별찍기를 할 때 맨위에 별이 가운데 하나있을 때에도 양 옆으로 11개씩 공백을 모두 출력해야 한다.

처음 코드를 제출했을 때, 이 부분을 구현하지 않아 출력형식이 잘못되었다는 오류 결과를 받았다.

그래서, 별이 몇개든지 간에 별이 없는칸은 무조건 공백이 나오도록 코드를 수정하였다.

이 부분을 해결하면서 두 가지 풀이로 모두 풀어보았다.

풀이를 보기 전, 다음 규칙을 알고 보는것이 도움이 될 것이다.

현재의 별찍기 모양은, 이전 별찍기 모양을 좌우로 두배 복사한 모양이다.

그래서 N = 6일 때는, N = 3 일때의 별모양이 양 옆으로 복사가 된 모습이다.

마찬가지로, N = 12일 때는 N = 6의 별모양이 양옆으로 복사가 되어 나타난다.

이 규칙을 인지하고 풀이를 보면 이해하기 훨씬 수월할 것이다.

풀이①

먼저 n=3일 때는 가장 기본모형이므로 재귀문을 돌지않고 바로 출력하도록 하였다.

n=6일 때 부터 재귀문을 돌게되는데,

before는 이전 별찍기 모양, after는 현재 별찍기 모양을 저장한 리스트이다.

N줄 까지는 이전 별찍기 모양을 그대로 복사하면 되는데,

이 때, 백준제출을 성공하기 위해선 별을 제외한 양옆의 모든 칸을 공백으로 채워야 한다.

그래서 범위를 반드시 [N : (N+2*N) - 1] 으로 명시하여 지정한 부분 외에는 공백을 지키도록 해야한다.

N줄부터 2N줄까지는 이전 그래프의 모양을 양 옆으로 복사를 해야한다.

마찬가지로 공백을 지켜야 하기 때문에 범위 제한에 신경을 써주어야 한다.

이러한 방식으로 마지막 줄에 도착할 때 까지 계속 재귀를 돌려주면 된다.

n = int(input())

graph = [[" ", " ", "*", " ", " "], [" ", "*", " ", "*", " "], ["*", "*", "*", "*", "*"]]


def recursive(N, before):
    after = [[" "] * (2 * 2 * N - 1) for _ in range(2 * N)]
    for i in range(N):
        after[i][N:N+2*N-1] = before[i]

    k = 0
    for i in range(N, 2 * N):
        after[i][:2*N] = before[k]
        after[i][2 * N:2 * N+len(before[k])] = before[k]
        k += 1

    if 2 * N == n:
        return after

    return recursive(2 * N, after)


if n == 3:
    result = graph
else:
    result = recursive(3, graph)

for i in result:
    print("".join(i))

풀이②

풀이2는 풀이1처럼 이전그래프를 양옆으로 복사한다는 개념보다는

맨 처음 n = 3 일때의 그래프를 계속 양옆으로 복사해 나가는 방식이다.

n = 3일 때의 가장 기본모양을 바탕으로,

다음 모양부터는 좌표만을 계산하여 재귀적으로 그리면 된다.

n = int(input())
graph = [[' '] * 2 * n for _ in range(n)]


def recursive(x, y, N):
    if N == 3:
        graph[x][y] = '*'
        graph[x + 1][y - 1] = graph[x + 1][y + 1] = '*'
        for i in range(-2, 3):
            graph[x + 2][y + i] = '*'
    else:
        nextN = N // 2
        recursive(x, y, nextN)
        recursive(x + nextN, y - nextN, nextN)
        recursive(x + nextN, y + nextN, nextN)


recursive(0, n - 1, n)
for i in graph:
    print("".join(i))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/2630

풀이 과정

먼저, N x N 배열이 모두 같은 색으로만 이루어져 있지 않으면 ( 즉, 1로만 이루어져있거나 0으로만 이루어져있지 않으면)

4등분을 해야한다.

예를 들어, 8 x 8 배열에서 처음 종이를 자르게 된다면 8 / 2 x 8 / 2 ( = 4 x 4 ) 모양의 색종이로 4등분을 하게 된다.

그리고 이렇게 4등분된 색종이 중 하나가 또 모두 같은 색으로 이루어져 있지 않다면,

그 색종이를 이전과 같은 방식으로 N / 2 x N / 2 모양의 색종이로 4등분을 하게 된다.

이렇게 계속 같은 방식으로 나누기 때문에, 재귀적으로 접근을 해야 하며

또, 하나의 구역을 작은 구역들로 나누고, 또 그 작은 구역들을 더 작은 구역들로 나눠 문제를 해결해야 하므로

분할 정복 문제라고 볼 수 있다.

이를 파이썬으로 나타낸 코드는 다음과 같다.

n = int(input())


def recursive(x, y, N):
    flag = False

    for i in range(x, x + N):
        if flag:
            break

        for j in range(y, y + N):
            if graph[x][y] != graph[i][j]:
                recursive(x, y, N // 2)
                recursive(x, y + N // 2, N // 2)
                recursive(x + N // 2, y, N // 2)
                recursive(x + N // 2, y + N // 2, N // 2)

                flag = True
                break

    if not flag:
        if graph[x][y] == 0:
            count[0] += 1
        else:
            count[1] += 1


graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

count = [0, 0]

recursive(0, 0, n)
for i in count:
    print(i)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/1074

현재 주어진 2차원 배열을 4사분면으로 쪼갠 후, 각 사분면에 대해 다시 또 4사분면으로 쪼개면서

각 사분면이 1칸이 될 때 까지 계속 쪼갠 후 방문 순서를 정하는 문제이다.

결국, 내가 입력한 r행 c열을 몇 번째로 방문하는지 구하는 문제이다.

풀이 과정

여기서 주의깊게 봐야할 점은 항상 왼쪽위(1사분면) -> 오른쪽위(2사분면) -> 왼쪽아래(3사분면) -> 오른쪽아래(4사분면) 의 방향을 지키면서 각 칸을 방문한다는 것이다. (Z모양)

처음 8x8 배열이 있으면,

처음에는 (0, 0) ~ (3, 3) 까지인 1사분면을 방문할 것이고,

또 그 1사분면을 4 x 4 배열 하나로 본 후, 4사분면으로 쪼개 1, 2, 3, 4 사분면으로 나눠 방문 순서를 정할 것이다.

이 때, 문제에서 N은 15이하의 수이므로

2 ^ 15 x 2 ^ 15칸을 모두 방문하게 되면 시간초과가 나게 된다.

따라서, 내가 찾는 칸이 현재 범위에 없다면 N * N 만큼 칸을 스킵하도록 해야 한다.

예를 들어, 내가 찾는 칸이 3사분면에 있다면 1사분면과 2사분면은 모두 검사할 필요 없이 단순히 스킵하면 된다.

이 부분이 if not (x <= r < x + N and y <= c < y + N) 부분이다.

n, r, c = map(int, input().split())
num = -1


def recursive(x, y, N):
    global num

    if N == 2:
        for i in range(x, x + N):
            for j in range(y, y + N):
                num += 1
                if i == r and j == c:
                    print(num)
                    exit(0)
        return

    if not (x <= r < x + N and y <= c < y + N):
        num += N * N
        return

    for i in range(x, x + N, N // 2):
        for j in range(y, y + N, N // 2):
            recursive(i, j, N // 2)


recursive(0, 0, 2 ** n)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/1780

문제 설명

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

풀이 과정

이전에 올렸던 쿼드트리(https://hongcoding.tistory.com/86?category=973613) 문제와 굉장히 유사하다.

쿼드트리 문제가 4구역으로 나눈 분할정복 문제라면

이번 문제는 9구역으로 나눈 분할정복 문제이다.

푸는 방식도 동일하다.

한 구역안에 모든 숫자가 같은 숫자로 이루어져 있지 않으면

같은 숫자로 이루어질 때 까지 계속 구역을 분할하며 풀어나가는 분할 정복 문제이다.

파이썬 코드는 다음과 같다.

n = int(input())


def recursive(x, y, N):
    flag = False

    for i in range(x, x + N):
        if flag:
            break

        for j in range(y, y + N):
            if graph[x][y] != graph[i][j]:
                recursive(x, y, N // 3)
                recursive(x, y + N // 3, N // 3)
                recursive(x, y + (N // 3 * 2), N // 3)
                recursive(x + N // 3, y, N // 3)
                recursive(x + N // 3, y + N // 3, N // 3)
                recursive(x + N // 3, y + (N // 3 * 2), N // 3)
                recursive(x + N // 3 * 2, y, N // 3)
                recursive(x + N // 3 * 2, y + N // 3, N // 3)
                recursive(x + N // 3 * 2, y + (N // 3 * 2), N // 3)

                flag = True
                break

    if not flag:
        if graph[x][y] == -1:
            count[0] += 1
        elif graph[x][y] == 0:
            count[1] += 1
        elif graph[x][y] == 1:
            count[2] += 1


graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

count = [0, 0, 0]
recursive(0, 0, n)

for i in count:
    print(i)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/1992

위 링크의 문제 설명을 보고 문제를 이해하기 어려울 수 있는데, 한 구역안에 점들이 모두 같은 숫자로 이루어져있지 않으면 왼쪽 위-> 오른쪽 위-> 왼쪽 아래 -> 오른쪽 아래 순 (지그재그 모양)으로 나누어 나타낸다는 것을 이해하면 쉽다.

풀이 과정

이 문제는 큰 구역을 작은 구역으로 계속 쪼개어 나타내는 분할 정복 문제이다.

문제의 예시처럼, 다음과 같은 배열이 주어졌을 경우를 생각해보자.

11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

8 x 8 배열의 모든 원소가 0으로만 이루어지거나 1로만 이루어지지 않고, 0과 1이 섞여있으므로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 4개의 구역으로 나누어 다시 압축을 해야한다.

4개로 나눈 구역 중 왼쪽 위의 구역(4x4)은 그럼 다음과 같이 나타날 것이다.

1111
1111
0001
0001

마찬가지로 0과 1이 섞여있으므로 여기서 또 다시 구역을 나누어야 한다.

나눈 구역 중, 왼쪽 위와 오른쪽 위는 모두 1로만 이루어지게 되고

왼쪽 아래도 모두 0으로만 이루어지기 때문에 분할을 멈출 수 있으며

오른쪽 아래는 아직

01

01    이기 때문에 다시 한 번 구역을 나누어야 한다.

여기서 더 구역을 나누게 되면 한 구역의 크기는 1 (1x1)이 되므로 무조건 한 구역에는 한 숫자만 존재하게 된다.

따라서, 구역 나누기를 멈추면 된다.

이러한 방식으로 왼쪽 위 부터 오른쪽 아래 까지 검사를 해주면 된다.

이를 아래의 파이썬 코드로 구현하였다.

여기서, 재귀문을 실행하기 전에, 압축이 가능한 상태면

재귀문을 실행하지 않고 바로 끝낼 수 있도록 구현하였다.

재귀문 안에서, 0으로만 이루어지거나 1로만 이루어질 경우에만 answer배열에 0 or 1을 추가해주고

그렇지 않으면 계속 재귀문을 돌도록 하였다.

n = int(input())
graph = []
answer = []


def recursive(x, y, N):
    answer.append("(")
    for i in range(2):
        for j in range(2):
            count0, count1 = 0, 0
            tmpGraph = []
            for k in range(N):
                tmpGraph.append(graph[x + i * N + k][y + j * N:y + (j + 1) * N])
                if '0' in tmpGraph[k]:
                    count0 = 1
                if '1' in tmpGraph[k]:
                    count1 = 1

            if count0 == 1:
                if count1 == 1:
                    recursive(x + i * N, y + j * N, int(N / 2))
                else:
                    answer.append(0)
            elif count1 == 1:
                answer.append(1)

    answer.append(")")


contain0 = 0
contain1 = 0
for i in range(n):
    graph.append(list(input()))
    if '0' in graph[i]:
        contain0 = 1
    if '1' in graph[i]:
        contain1 = 1


if contain0 == contain1:
    recursive(0, 0, int(n / 2))
    for i in answer:
        print(i, end='')

else:
    if contain0 == 1:
        print(0)
    else:
        print(1)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/2447

문제 설명

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***

* *

***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

풀이 과정

이 문제는 분할 정복 문제로, 큰 문제를 작은 문제로 쪼개어 해결한다음 이를 이용해 큰 문제를 해결하는 문제이다.

먼저, 문제를 풀기 위해선 규칙부터 찾아야 한다.

가장 작은 3 x 3 부터 살펴보자.

5번 째 칸을 제외하고는 모두 별로 채워져 있다.

5번째 칸의 특징은 x, y 좌표 모두 1이라는 것이다. (1, 1)

그럼 이제 3 x 3을 3배 늘린 9 x 9를 살펴보자.

위 테이블을 보면 알 수 있듯이, 9 x 9 는 3 x 3의 테이블의 패턴이 똑같이 반복되어 나타남을 알 수 있다.

여기서, 9 x 9안에서의 3 x 3 하나를 한 칸이라고 생각해보자.

(즉, 3 x 3 패턴 하나를 한 칸으로 생각해보자.)

그럼, 9 x 9 테이블을 3 x 3 으로 생각해볼 수 있다.

이 때, 마찬가지로 가운데 부분만 비어있음을 알 수 있다.

3 x 3 에서 가운데 부분인 (1, 1) 만 비어있듯이,

9 x 9 에서 가운데 부분인 (3, 3) 부터 (5, 5) 까지의 부분만 비어있다.

마찬가지로 9 x 9 테이블을 3배 늘린 27 x 27 은

위의 9 x 9 의 패턴을 한 칸으로 취급하여 3배 늘린 모양이며, 가운데가 비어있다.

여기서 비어있는 곳의 특징이 있다.

처음엔 (1, 1), 그 다음엔 (3, 3)~(5, 5), 그 다음엔 (9, 9) ~ (17, 17) 이다.

이는 모두 각 행,열을 3^N으로 나누었을 때 몫이 1이라는 특징이 있다.

처음에는, 1로 나누었을 때의 몫이 1

그 다음에는, 3으로 나누었을 때 몫이 1

그 다음에는, 9으로 나누었을 때 몫이 1인 행,열 인 것이다.

이를 이용한 코드는 다음과 같다.

n = int(input())
star = ["***", "* *", "***"]
cnt = 0


def getStars(star):
    mat = []
    for i in range(3 * len(star)):
        if i // len(star) == 1:
            mat.append(star[i % len(star)] + " " * len(star) + star[i % len(star)])
        else:
            mat.append(star[i % len(star)] * 3)
    return mat


while n > 3:
    n /= 3
    cnt += 1

for i in range(cnt):
    star = getStars(star)

for i in star:
    print(i)

가장 기본적인 모양인

***

* *

*** 을 만들어 주고

n이 3 이상일 때 부터 반복패턴을 만들어 주기 위해 while문을 통해 몇 번 반복해야 할 지를 정한다.

그리고 나서 그 횟수만큼 반복하여 그려준다.

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !