제로베이스 20220412 코테 연습
1. 직각삼각형
- 과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다.
- 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오.
입력
- 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다.
- 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다.
출력
- 각 입력에 대해 직각 삼각형이 맞다면 “right”, 아니라면 “wrong”을 출력한다.
풀이
import sys
while True:
a,b,c = list(map(int,sys.stdin.readline().split()))
if a == 0 and b == 0 and c == 0: break
print("wrong" if max(a,b,c) ** 2 != sum([x**2 for x in [a,b,c] if x != max(a,b,c)]) else "right")
채점 결과
- 정답
리뷰
-
피타고라스 정리를 활용한다.
-
가장 긴 변을 찾아 제곱하고, 나머지 두개를 제곱한 값과 비교하는 방식으로 풀었다.
2. 체스판 다시 칠하기
-
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
-
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
-
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
출력
- 첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
풀이
import sys
N, M = list(map(int, sys.stdin.readline().split()))
board = [[-1 for x in range(0, M)] for x in range(0, N)]
sample_board_0 = [["WBWBWBWB"], ["BWBWBWBW"]] * 4
sample_board_1 = [["BWBWBWBW"], ["WBWBWBWB"]] * 4
for i in range(0, N):
board[i] = sys.stdin.readline().strip()
min_ = 65
for n in range(0, N - 7):
for m in range(0, M - 7):
cnt0 = 0
cnt1 = 0
for i in range(n, n + 8):
for j in range(m, m + 8):
if board[i][j] != sample_board_0[i - n][0][j - m]:
cnt0 += 1
if board[i][j] != sample_board_1[i - n][0][j - m]:
cnt1 += 1
cnt = min(cnt0, cnt1)
if cnt < min_:
min_ = cnt
print(min_)
채점 결과
- 정답
리뷰
- 이중반복문을 통한 탐색으로 두 타입의 보드중 바꿔야할 사각형 개수가 적은것을 채택한다.
더 나은 풀이
- 풀이 출처 : 아이디 wider93님의 풀이
import sys
from itertools import accumulate as acc
input = sys.stdin.readline
n, m = map(int, input().split())
y = [[0]*(m+1)]
for i in range(n):
ac = [0]
ac.extend(acc([((s=='W')+i+j) % 2 for j, s in enumerate(input().rstrip())]))
y.append([k + j for k, j in zip(ac, y[-1])])
res = 32
for i in range(n-7):
for j in range(m-7):
u = y[i+8][j+8]-y[i+8][j]-y[i][j+8]+y[i][j]
res = min(res, u, 64-u)
print(res)
더 나은 풀이 리뷰
-
itertools.accumulate
-
누적 합계나 다른 이항 함수(선택적 func 인자를 통해 지정됩니다)의 누적 결과를 반환하는 이터레이터를 만듭니다.
-
func가 제공되면, 두 인자를 취하는 함수여야 합니다. 입력 iterable의 요소는 func에 대한 인자로 허용될 수 있는 모든 형일 수 있습니다. (예를 들어, 기본 더하기 연산에서 요소는 Decimal이나 Fraction을 포함하는 모든 더할 수 있는 형일 수 있습니다.)
-
출처 : https://docs.python.org/ko/3/library/itertools.html#itertools.accumulate
-
반복합을 뽑아내는 함수인데, for문으로 뽑아내는것에 비해 압도적인 성능을 지닌다.(성능비교 관련 블로그 정리글)
-
-
enumerate(iterable)
- (index, iter)로 출력.
[((s=='W')+i+j) % 2 for j, s in enumerate(input().rstrip())]는 입력받은 값이- 홀수줄에서는 “WBWB…“로 이루어진 체스판의 줄
- 짝수줄에서는 “BWBW…“로 이루어진 체스판의 줄
- 에 대해 일치하는 인덱스에 1, 불일치시 0을 저장한 배열을 return한다.
-
ac는 위의 배열에 대해 반복합을 구한것이므로, 체스판과 다른 모양이 있는 구간이 있는 경우 그 부분부터 1 증가한 값을 가지는 배열을 return한다.
- ex) WBWBWBWB => 0,1,2,3,4,5,6,7,8
- ex) WBWBBBWB => 0,1,2,3,4,4,5,6,7
- 즉, ac의 누적합인 y는 다음과 같은 사항이 적용된다.
- WBWB..로 시작하는 체스판에 대해서 완전 일치할때 64
- 틀린 부분이 발생시 63,62,..로 감소
- BWBW..로 시작하는 체스판에 대해서 완전 일치할때 0
- 틀린 부분이 발생시 1,2,..로 증가
- WBWB..로 시작하는 체스판에 대해서 완전 일치할때 64
y[i+8][j+8]은 i~i+8까지, j~j+8까지의 체스판이 가지는 누적 오차를 의미한다.- 이때 y[i+8][j]와 y[i][j+8]를 빼는 이유는 i,j이전 열과 행들의 오차에 영향을 받지 않기 위함이다.
- 단, y[i+8][j]와 y[i][j+8]을 두번 뺌으로 인해 중복해서 제거된 영역인 y[i][j]를 더해주어야 한다.
-
res는 해당 체스판에서 가장 적은 오차를 의미하며, 전부 바꿔야하는 경우(32)를 기본값으로 모든 판을 순회하며 누적 오차중 가장 적은 값을 저장한다.
-
내가 봐온 모든 정답자 코드중에서 가장 해석하기 난해한 코드였던것 같았다.
-
코드 해석을 진행하며 계속 수정을 덧붙여서 표가 안나겠지만, 이 코드 해석에만 3~4일 정도 사용한것 같다.
-
언젠간 나도 저런 코드를 짤수 있을 날이 오려나, 다시한번 공부의 부족함을 실감한 며칠이었다.
-