[백준] 1802 - 종이 접기

문제

백준 1802번 종이 접기

 

 

알고리즘

분할 정복 (Divide and Conquer)

 

이미지 출처 : https://velog.io/@minjungh63/%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘

* dp와 다른 점?
두 알고리즘 다 문제를 하위 문제로 나누고 재귀적 구조를 가진다는 과정이 유사하지만, 독립성 유무에 따라 달라진다. 분할 정복은 하위 문제들이 독립적이고 결과를 참조하지 않는다. 반대로 DP는 하위 문제들이 서로 의존적이어서 메모이제이션을 통해 결과를 참조한다는 차이점이 있다.

 

따라서 분할 정복 알고리즘은 큰 문제를 소문제로 나누고, 그 소문제들이 같은 매커니즘으로 해결될 수 있을 때 사용하되, 각 소문제들이 독립적일 때 유용하게 쓰일 수 있는 알고리즘이다. (말은 이렇게 써놨지만 아직 완전히 감이 오지 않는다.. 분할 정복 알고리즘 문제들을 더 풀어보고, 언제 적용하면 되는지에 대해 추후 다시 자세하게 업로드할 예정!!)

 

재귀 함수를 통해 자연스럽게 구현된다. 

function F(x):
	if F(x)의 문제가 간단 then:
    	return F(x)를 직접 계산한 값
    else:
    	x를 y1과 y2로 분할
        F(y1)과 F(y2)를 호출
        return F(y1), F(y2)로부터 F(x)를 구한 값

 

분할 정복은 다음과 같은 설계를 가진다.

1. Divide
   원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다. 
2. Conquer
   각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다.
3. Combine
   conquer 한 문제들을 통합하여 원래 문제의 답을 도출한다.

 

📜내용 출처 : 

https://loosie.tistory.com/237

[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)

https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전

 

 

문제 풀이

 

이 문제는 문제에서 제시한 1번, 2번 방법대로 무작위로 접었을 때 나오는 방향에 따른 반시계 방향(0), 시계 방향(1) 의 수열이 가능한지 여부를 출력하는 게 목적이다.

 

처음에 생각한 방식은, 종이를 해당 방식으로 접었을 때, 가운데를 중심으로 1과 0이 대칭이 된다는 것이었다. 같은 방향으로 접히기 때문에 수평으로 펼쳤을 때는 바람개비처럼 같은 방향을 바라보는 방식, 즉 0과 1 중 각각 하나로 반대가 된다는 것을 사용하여 문제를 해결하려고 하였다. 모든 길이는 홀수라는 조건이 있기 때문에 middle 값은 언제나 중심이며, 이때, 길이가 1인 경우 반드시 'YES'를 출력하도록 코드를 작성하였다. 처음 작성한 코드는 다음과 같다.

 

# 오답 코드
import sys

input = sys.stdin.readline

total=int(input())

def func():
    lst=list(map(str,input().rstrip()))
    n=len(lst)
    middle=int(n/2)
    if middle==0:
        return 'YES'
    for i in range(0,middle):
        if lst[i]==lst[n-i-1]:
            return 'NO'
    return 'YES'

for i in range(total):
    print(func())

 

그러나 계속 16% 쯤에 오답으로 판명되었고, 더 이상 혼자 힘으로는 해결할 수 없다고 생각하여 다른 블로그 글들을 찾아보았다. 분할 정복 알고리즘이었는데, 백준 문제풀이에서 거의 처음 접한 알고리즘이라 감을 잡지 못했다. 이후 다음과 같은 블로그를 참고하여 해결 방법을 알 수 있었다.

 

➡️참고한 블로그 링크 : https://velog.io/@rkdwldnjs30/%EB%B0%B1%EC%A4%80python-1802-%EC%A2%85%EC%9D%B4%EC%A0%91%EA%B8%B0

[백준/python] 1802 종이접기

 

내가 쓴 코드의 문제는, 처음 주어진 입력의 가운데만 중심으로 하여 대칭을 확인한다는 것이었다. 이 문제에서는 각 단계에서 정확히 절반의 크기로 접으므로, 매 단계에서 가운데를 기준으로 대칭이어야 한다. 

 

따라서 분할 정복 알고리즘의 방법대로, 주어진 배열을 middle을 중심으로 (middle 값 포함X) left_part와 right_part로 나누어 각각 divide() 함수를 호출한다(분할). 이후 왼쪽과 오른쪽 중 하나에서 False가 나온다면, 즉 대칭이 아니라면 함수에서 False를 리턴하고, 아니라면 left_part와 right_part가 대칭인지 여부를 확인(정복)하는 방식으로 코드를 작성하여 문제를 해결할 수 있었다.

 

코드

# 분할 정복
import sys

input = sys.stdin.readline

total=int(input())

def divide(part):
    n=len(part)
    middle=n//2
    
    # conquer 1
    if n==1:
        return True
    left_part=part[0:middle]
    right_part=part[middle+1:n]

    # divide
    is_left=divide(left_part)
    is_right=divide(right_part)
    
    # combine
    if not is_left or not is_right:
        return False
    
    # conquer 2
    for i in range(middle):
        if left_part[i]==right_part[middle-1-i]:
            return False
    return True
    

for i in range(total):
    lst=list(map(str,input().rstrip()))
    is_result = divide(lst)
    if is_result:
        print('YES')
    else:
        print('NO')