항해99를 시작한지 겨우 3주(21일)밖에 안지났는데 하루 최소 12시간 이상 씩 매일 하다보니 체감상 3달은 된거 같습니다. 적은 일수로 많은 것을 해내기 위해 필요한 것들만 배울 수 있도록 커리큘럼이 짜여져 있어 항해 99가 끝난 후에 어떻게 되었을지 기대가 많이 됩니다.
몰랐던 알고리즘(백트래킹, 분할정복, 다익스트라)을 적용해야만 풀 수 있는 문제도 있어 혼자 고민하면서 시간을 흘러보내며 결국 인터넷을 찾아봐서 알게되었지만 문제를 해결하려고 시도한 덕분에 알고리즘에 더욱 익숙해질 수 있었습니다.
2주동안 배우고 연습했던 알고리즘으로 3/20 Startup Coding Festival을 지원해 시험을 봤습니다. 4시간동안 총 6문제를 풀면되는데, 6문제 중 2문제만 정답으로 처리되고 2문제는 예제만 통과해 많이 아쉬웠고, 열받았습니다. 알고리즘 공부를 나름 열심히 했다고 생각했는데 더욱 더 열심히 해야하는 생각이 들었습니다. (지속적으로 최소 하루에 2~3문제는 풀기)
다음 커리큘럼(3/19) 부터 각자 선택한 주특기(Spring)에 대해 배우게 되는데, 이제 본격적으로 서비스를 만드는 준비를 하는거 같아 설렘을 느끼고있습니다.
아래 <그림 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과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.
(2) 입력
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
(3) 출력
첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.
(4) 예제 입력 및 출력
(5) 코드
import sys
import math
square_length = int(sys.stdin.readline())
square_list = []
square_store = []
count_zero = 0
count_one = 0
def is_zero_one(square_store, square_arrow_list):
is_zero = False
is_one = False
global count_one
global count_zero
for row in square_arrow_list:
if not is_one or not is_zero:
if 1 in row:
is_one = True
if 0 in row:
is_zero = True
else:
break
if is_one and is_zero:
square_store.append(square_arrow_list)
elif not is_zero:
count_one += 1
else:
count_zero += 1
for i in range(square_length):
square_list.append(list(map(int, sys.stdin.readline().split())))
is_zero_one(square_store, square_list)
while square_store:
square = square_store.pop(0)
half_size = len(square) // 2
square_left_up_list = []
square_rigth_up_list = []
square_left_down_list = []
square_right_down_list = []
for i in range(half_size):
temp_left_up_list = []
temp_rigth_up_list = []
temp_left_down_list = []
temp_right_down_list = []
for j in range(half_size):
#왼쪽 위
temp_left_up_list.append(square[i][j])
#오른쪽 위
temp_rigth_up_list.append(square[i][j + half_size])
#왼쪽 아래
temp_left_down_list.append(square[i + half_size][j])
#오른쪽 아래
temp_right_down_list.append(square[i + half_size][j + half_size])
square_left_up_list.append(temp_left_up_list)
square_rigth_up_list.append(temp_rigth_up_list)
square_left_down_list.append(temp_left_down_list)
square_right_down_list.append(temp_right_down_list)
is_zero_one(square_store, square_left_up_list)
is_zero_one(square_store, square_rigth_up_list)
is_zero_one(square_store, square_left_down_list)
is_zero_one(square_store, square_right_down_list)
print(count_zero)
print(count_one)
