💯 문제 → N은 2, 4, 8, 16, 32, 64, 128 중 하나이며, 정사각형으로 이루어 져있고 그 정사각형 안의 숫자가 모두 같은 숫자로 이루어져 있으면 하나의 묶음이 완성되는 문제인듯 ! 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 계속해서 크기를 나누어 정사각형을 만드는 방식을 사용하여 문제 풀면 될 듯
<💭 방법>
🎈 1 분할정복을 사용하는 방법
- 일단 들어온 입력을 모두 리스트에 저장을 하는 한 후, 그 리스트를 나누기 시작
- 나누는 방법은 입력된 리스트를 일단 가로세로 반으로 나눔
- 반으로 나눈 리스트가 모두 같은 수로 이루어져 있는지 확인
- 만약 다르다면 다시 가로세로 반으로 나눔
- 나누기 위한 함수를 만듦 (재귀 사용)
문제점 : 나누기 위해 리스트를 계속해서 생성해야되는 문제가 생김 .. 그럼 메모리 낭비가 너무 심해지고, 미리 배열들을 선언해 놔야됨 .. 그리고 여기서 궁금한 점 ! 분할정복은 일단 가장 작은 문제로 분할해서 거기서 답을 찾으면 병합하는 것 아닌가 .. ? 근데 문제에서는 나누면서 답을 찾는 것 같은데 .. 음 ..
🎈 2 분할정복을 사용하는 방법
- 일단 들어온 입력을 모두 리스트에 저장
- 리스트에 모두 같은 수가 들어있는지 확인
- 만약 아니라면, 탐색할 부분의 시작 X,Y 값과 N/2 값을 전달해 줌
- 결국에는 가로세로 2등분을 하면 4개의 등분이 나오게 되는것이므로 재귀를 4번 전달 값을 다르게 하여 호출함
- 리스트 안의 값이 모두 같고 만약 그것이 0이면 하얀색, 1이면 파란색으로 간주함
문제점 : 분할 정복에 대해 잘못 알고 있었던점 .. 최대한으로 문제를 분할 한 뒤, 해답을 구하면 병합을 통해 다음 큰 문제에 적용하는 것이었다 ㅠㅠ .. 근데 나는 분할을 하면서 탐색을 함 .. 그래서 코드가 잘 안짜짐 ..
🎈 3 분할정복을 사용하는 방법
- 들어온 입력을 모두 배열에 저장
- 쪼갤수 있을 만큼의 최대한 작은 문제로 먼저 분할 (가로, 세로 N/2씩)
- 반씩 분할하게 되면 총 4개의 구역이 생기는데, 구역에서 반환하는 값을 이용하여 그 구역에 같은 수가 들어있는지 확인
- 만약 반환하는 수가 모두 같은 수라면 색종이 하나 완성
<😥 첫번째 코드>
next_N = N // 2
for i in range(x, x + next_N):
for j in range(y, y + next_N):
if paper[x][y] == 0:
Paper(x, y, next_N)
Paper(x + next_N, y, next_N)
Paper(x, y + next_N, next_N)
Paper(x + next_N, y + next_N, next_N)
count += 1안된 이유 : 재귀함수를 많이 호출했다는 오류가 뜬는데 ,,,, 이유를 살펴보니, 일단 먼저 리스트로 받은 모든 원소를 돌면서 0일 경우 호출을 한다는 큰 문제가 있었다 ,,, 저걸 한 이유는 일단 먼저 1일 경우 부터 골라서 세아리려고 했는데 ,,, 지금 뭔가 단단히 잘못됐다 ,,,
<😍 두번째 코드>
def Paper(x, y, N):
global paper, white, black
next_N = N // 2
if N == 1:
return paper[x][y]
a = Paper(x, y, next_N)
b = Paper(x + next_N, y, next_N)
c = Paper(x, y + next_N, next_N)
d = Paper(x + next_N, y + next_N, next_N)-
가장 작은 문제로 분할을 한다. 이 과정에서는 재귀 함수를 사용하고, 각 구역의 시작 지점을 전달하고 구역의 크기를 전달한다.
-
만약 크기가 1로 가장 작은 문제로 분할이 완료가 되면, 각 원소의 값을 반환한다.
if a == b == c == d == 1:
return 1
elif a == b == c == d == 0:
return 0
else:
if a == 1 :
white += 1
elif a == 0:
black += 1
if b == 1:
white += 1
elif b == 0:
black += 1
if c == 1:
white += 1
elif c == 0:
black += 1
if d == 1:
white += 1
elif d == 0:
black += 1
return 2-
각 구역의 반환값이 모두 같으면 그 값에 따라 반환값이 달라지고, 만약 반환값이 모두 다르다면 2를 반환해준다.
-
이렇게 반환을 하는 이유는 먼저 각 구역의 반환값이 다를 경우, 색종이가 하나로 완성이 되지 않는다. 이유는 리스트 안은 모두 같은 값을 가지고 있지 않기 때문이다. 그래서 종이가 더 이상 병합이 되도 색종이가 완성이 안되니 바로 각각의 값을 올려주는 것이다.
-
하지만 모두 같은 값을 가지는데 값을 올려주지 않는 이유는 다음 병합 때 나누어지는 구역들과 같은 값이 존재 할 수 있기 때문이다.
느낀점
나누는 방법을 고민하는데 많은 시간이 걸렸다 ㅠㅠ 아무리 생각을 해도 리스트를 이용해서 나누는 방법밖에 생각이 안났는데 ,, 왠지 알고리즘만 잘 짜면 코딩은 쉬울 것 같다는 생각을 했다 ㅎㅎ .. 하지만 .. ㅠㅠ 예상 외로 리스트 안의 값이 모두 같은지를 판단하는 부분이 가장 어려웠다 ... 예상외로 시간이 꽤나 오래 걸렸던 문제였다 .. 이번 문제는 뭔가 가장 핵심인 부분은 바로 찾아내서 풀었는데 return 값이나 이러한 부속적인 부분이 나를 많이 힘들게 하였다 .. 그래도 풀었으니 뿌듯 !
