2021.03.19 TIL 알고리즘 공부

이제 알고리즘 공부 2주차도 끝이다.. 

생각보다 공부한 시간에 비해 내가 배운건 별로 없는 느낌이라 속상하다 .. 

 

이번주에 공부한 개념들에서 기억에 남는 개념은 분할 정복과 백트래킹 그리고 최단 경로다 . 

 

 

분할 정복

분할 정복은 답을 구하는 과정에서 쪼개고 쪼개서 작은 픽셀에서 계산이 되도록 하는 문제였다 .

DSF와 BFS를 공부할 때 풀었던 토마토 문제와 비슷한 느낌으로 시작점을 기준으로 쭉 검사를 진행하지만 조건이 더 추가되고 구간을 나눠서 문제를 푼다는 점이 달랐다. 

 

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

문제 

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

 

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

 

예제 입력

8
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

 

 

예제 출력

9
7

풀이

n = int(input());  #한 변의 길이

paper = [list(map(int, input().split())) for _ in range(n)] #입력받은 변의 길이만큼 데이터 받기

white , blue = 0, 0;  #흰색과 파란색 구역을 카운트할 변수

def cut(x,y,cnt):
    global white, blue
    now_color = paper[x][y]   #현재 지점의 색을 읽어오고
    for i in range(x,x+cnt):  #하나씩 이동하며 현재의 색과 비교
        for j in range(y,y+cnt):
            if now_color != paper[i][j]:  #다른 색이 존재한다면
                cut(x,y,cnt//2)   #구역을 절반씩 나눠 4개로 분리시켜 다시 함수에 넣어준다
                cut(x,y+cnt//2,cnt//2)
                cut(x+cnt//2,y,cnt//2)
                cut(x+cnt//2,y+cnt//2,cnt//2)
                return
    if now_color == 0 :  #모두 같은색이라면
        white += 1;      #색에 맞는 변수에 +1
        return
    else :
        blue += 1
        return
cut(0,0,n)
print(white)
print(blue)        

 

생각해보면 간단한 문제인데 내가 찾는 조건과 다를 때 4개로 나눠 다시 넣어주는걸 설계하는게 처음엔 어려웠다 .

여러번 실패끝에 변의 길이를 이용해서 반으로 줄여나가는 형태를 사용해서 성공했다. 시작점이 0,0 이라는 게 도움이 됐던 문제.

 

추가적으로 이와 비슷한 문제가 하나 더 있었다.

www.acmicpc.net/problem/1992

1992번: 쿼드트리

유사한 문제지만 나눠진 구역마다 가로 안에 넣어 출력하는 문제였다.

이 부분은 함수 마지막에 4구역으로 나눠서 다시 돌려줄 때 시작과 끝에 가로를 열고 닫도록 해주니 쉽게 풀렸다. :) 

 

백트래킹

최적의 값을 찾아내려고 쭉 탐색해 나가다가 막히는 부분이 생기면 그 전으로 돌아와 다른 길로 가야했던 백트래킹... 

이론은 머리로 이해가 가는데 코드로 구현하는게 정말 정말 어려웠다.. 

그냥 손으로 풀거나 설명하면 간단한 문제인데 이렇게나 어렵다니.. 새삼 알고리즘과 코딩이 정말 쉽지 않다는 걸 느끼게 해준 문제.. 

이 문제에서 웃긴 점은 퀸의 위치를 찾는 문제에서 힌트랍시고 진짜 퀸의 노래를 링크로 넣어놨다..  

전혀 도움 되지 않는데요...... 🤬

 

www.acmicpc.net/problem/9663

9663번: N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력

8

예제 출력

92

풀이

n, ans = int(input()), 0  
a, b, c = [False]*n, [False]*(2*n-1), [False]*(2*n-1)  
#같은 열과 왼쪽, 오른쪽 대각선 방향은 오지 않도록 표시해주기 위함

def solve(i):
    global ans
    if i == n: #함수가 끝까지 가는데 성공했다면  +1
        ans += 1
        return
    for j in range(n):
        if not (a[j] or b[i+j] or c[i-j+n-1]): #같은 열과 대각선이 아니라면
            a[j] = b[i+j] = c[i-j+n-1] = True #참으로 표시해주고 계속해서 진행
            solve(i+1)
            a[j] = b[i+j] = c[i-j+n-1] = False #다른 위치를 탐색하기 위해 초기화

solve(0)
print(ans)

 

하루종일 이 문제를 붙들고 있었는데 계속 실패하는 바람에 결국 다른 블로거들의 도움을 받았다 .. 

단순히 1차 배열을 이용해서 같은 열과 대각선을 비교할 수 있었다니............... 

정말 처음 머리로 생각했던 풀이처럼 코드도 간단하게 나왔다.. 너무 신기한 알고리즘의 세계.. 좀 더 노력하겠습니다. 

 

최단 경로

마지막으로 최단 경로를 공부하고 있는 중이다..

이론은 이해 했으나 내가 구현한 함수는 배열을 이용해서인지 답안으로 제출하면 메모리 초과 메세지가 떴다. 

찾아보니 배열로 진행하면 통과할 수 없는 문제라고 한다... 😥😥

heapq 모듈이라는 것을 사용해 문제를 풀어나가야만 메모리 한도 내에서 결과를 찾아낼 수 있다고 한다..

현재 힙 큐 모듈을 공부중인데 일단 평소에 쓰던 리스트와 비슷하고 pop을 사용하는 것이 스택과 비슷했다. 

다만 굉장히 신기한게 트리처럼 위 아래 수를 비교해 순서를 정해 정렬한다는 점.. 

 

공부를 하면 할수록 수열을 이용할 때 itertools의 combinations 내장 함수를 사용하는 것처럼 자꾸만 파이썬의 새로운 기능들이 발견되고 있다... 

처음에는 내가 충분히 함수로 구현할 수 있는 혹은 했었던 함수들이 내장 함수 명령어를 통해 쉽게 사용하는 것에서 시작했지만, 이제는 정말 복잡하고 긴 코드들을 단순하게 명령어를 이용해 사용한다는 점이 신기했다.

하지만 한편으로 내가 이런 함수들을 사용하지 못하게 됐을 땐 어떤 방식으로 문제를 풀어나가야 할 지 고민하는 자세가 필요하다고 생각한다. 다른 대다수의 사람들은 이 문제를 풀 때 어떤 순서로 접근하는지, 어떻게 생각을 펼치는지 너무 궁금했던 한 주였다.