대학원생이 쉽게 설명해보기

def half_check(check_num, check_list):
    list_len = len(check_list)
    
    if(list_len == 0):
        return print('0')
    
    index = list_len // 2
    
    if(check_list[index] == check_num):
        return print('1')
    elif(check_list[index] > check_num):
        return half_check(check_num, check_list[:index])
    else:
        return half_check(check_num, check_list[index + 1:])

import sys
input = sys.stdin.readline    

N = int(input())
A = list(map(int, input().split()))
sorted_A = sorted(A)

M = int(input())
M_list = list(map(int, input().split()))

for check_num in M_list:
    half_check(check_num, sorted_A)

설명에 어렵다고 하길래 해봤더니, 직접 짠 코드는 시간초과...

이번 문제는 다량 참조하였다. 이 문제를 푼다면 '꼭' closest point 문제에 대한 이론적 개념을 이해하고 넘어가길 바란다. 보다보면 재밌다.

시간초과 코드 참고: https://hon6036.github.io/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5/2261/
이론 참고: https://casterian.net/archives/92
(이론 블로그는 위 블로그에서 연결되어 있습니다.)

def dist(x1, x2):
    return (x1[0] - x2[0])**2 + (x1[1] - x2[1])**2

# 이론 블로그 참고
def solve(coords, N):
    # 점이 두 개일때는 두점 거리만 구하면 됩니다.
    if(N == 2):
        return dist(coords[0], coords[1])
    # 점이 세 개일때는 각 두점 사이의 거리를 구해서 최솟값을 구하면 됩니다.
    elif(N == 3):
        return min(dist(coords[0], coords[1]), dist(coords[1], coords[2]), dist(coords[0], coords[2]))
    
    mid = (coords[N//2][0] + coords[N//2-1][0]) // 2
    # x축을 기준으로 짧은 거리 d를 구합니다.
    d = min(solve(coords[:N//2], N//2), solve(coords[N//2:], N//2))
    
    # x 축 기준을 잊지 말것
    # 유효 거리 d보다 짧거나 같은 것을 제외하고 나머지는 제외시킵니다.
    # 즉, 두점 거리가 d보다 먼 경우는 제외합니다.
    short_check = []
    for subset in coords:
        if((mid - subset[0])**2 <= d):
            short_check.append(subset)
    short_check.sort(key = lambda x:x[1])
    
    if(len(short_check) == 1):
        return d
    else:
        y_check = d
        
        # x축만 고려하면 아직 고려해야할 점의 개수가 많이 남아있어 시간초과가 뜨게 됩니다.
        # 따라서 y축을 고려해주어 y축 기준의 d보다 긴 경우는 전부 제외시켜 주어야 합니다.
        # 세 가지 경우는 필수로 제외합니다.
        for i in range(len(short_check) - 1):
            for j in range(i+1, len(short_check)):\
                # y축 기준, 기본적으로 최소 길이 d보다 사이 거리가 긴 경우 제외
                if(short_check[i][1] - short_check[j][1]) ** 2 > d:
                    break
                # 두 점 모두 왼쪽에 있는 경우
                elif(short_check[i][0] < mid and short_check[j][0] < mid):
                    continue
                # 두 점 모두 오른쪽에 있는 경우
                # 두 점이 mid를 지나는 점과 비교해보세요
                elif(short_check[i][0] > mid and short_check[j][0] > mid):
                    continue
                y_check = min(y_check, dist(short_check[i], short_check[j]))
                
    return y_check

import sys

# input = sys.stdin.readline
N = int(input())
coords = [list(map(int, input().split())) for _ in range(N)]

# 중복되는 점은 제거
# 블로그 참고
coords_set = list(set(map(tuple,coords)))
if len(coords_set) != len(coords):
    print("0")
else:
    coords_set.sort() # sorted(coords, key=lambda x:-x[0])
    print(solve(coords_set, N))

1. 시간 초과(단순 코딩)

def solve(index, heights):
    cur_height = heights[index]
    
    left_cand = 0
    right_cand = 0
    
    # 왼쪽 높이부터 계산
    if(index > 0):
        for li in range(index - 1, -1, -1):
            if(cur_height <= heights[li]):
                left_cand += 1
            else:
                break
                
    for ri in range(index + 1, n, 1):
        if(cur_height <= heights[ri]):
            right_cand += 1
        else:
            break
                
    left_area = cur_height * left_cand
    right_area = cur_height * right_cand
    total_area = cur_height + left_area + right_area
    
    return total_area

while True:
    n, *heights = list(map(int, input().split()))
    if(n == 0):
        break
    result = []
    
    for i in range(n):
        result.append(solve(i, heights))
    
    print(max(result))

2. stack 개념을 활용

while True:
    n, *heights = list(map(int, input().split()))
    if(n == 0):
        break
    
    # 첫 시점의 계산을 위해 0을 맨 앞에 추가하고,
    heights.insert(0, 0)
    # 마지막 사각형 계산을 위해 0을 끝에 추가합니다.
    heights += [0]
    checked = [0]
    area = 0
    
    # 현재 높이보다 이전 높이가 높으면, while에 진입합니다.
    # 현재 높이가 더 낮은 경우, 넓이를 이어서 계산할 수 없으므로
    # 이전 시점까지 저장됬던 사각형의 높이를 계산합니다.
    # 끝 사각형도 고려해야 하므로, n+1까지 반복합니다.
    for i in range(1, n + 2):
        # heights[checked[-1]]은 이전 시점의 사각형 높이
        # heights[i]는 현재 시점의 사각형 높이
        # heights[checked[-1]] > heights[i]는 현재 높이보다 이전 높이가 높은지 확인
        while(checked and (heights[checked[-1]] > heights[i])):
            # 비교할 사각형 index
            cur_height = checked.pop()
            # (i - 1 - checked[-1])은 cur_height와 현재 시점 사이에 몇 개의 사각형이 존재하는지를 판단
            area = max(area, (i - 1 - checked[-1]) * heights[cur_height])
        checked.append(i)
    print(area)

def make_matrix(A, matrix):
    dummy_matrix = [[0 for _ in range(2)] for _ in range(2)]
    
    for i in range(2):
        for j in range(2):
            for k in range(2):
                dummy_matrix[i][j] += (matrix[i][k] * A[k][j])
            dummy_matrix[i][j] %= 1000000

    return dummy_matrix

def matmul(A, B):
    if(B == 1):
        for i in range(2):
            for j in range(2):
                A[i][j] %= 1000000
       
        return A
    
    elif((B%2) == 1):
        matrix = matmul(A, B-1)
        new_matrix = make_matrix(A, matrix)
    
        return new_matrix
    
    else:
        matrix = matmul(A, B//2)
        new_matrix = make_matrix(matrix, matrix)
    
        return new_matrix

N = int(input())

A = [[1, 1], [1, 0]]
result = matmul(A, N)

print(result[0][1] % 1000000)

def make_matrix(A, matrix):
    # [[0]*2]*2 로 하면 리스트가 공유되서 다른 결과가 나옴
    dummy_matrix = [[0 for _ in range(N)] for _ in range(N)]
    
    # 행렬곱에서 사용한 방법은 시간 초과
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dummy_matrix[i][j] += (matrix[i][k] * A[k][j])
            dummy_matrix[i][j] %= 1000

    return dummy_matrix

def matmul(A, B):
    if(B == 1):
        for i in range(N):
            for j in range(N):
                A[i][j] %= 1000
       
        return A
    
    # 홀수인 경우엔, A를 마지막에 곱해주어야 합니다.
    # ex) AAAAA -> (A^2)^2 * A
    elif((B%2) == 1):
        matrix = matmul(A, B-1)
        new_matrix = make_matrix(A, matrix)
    
        return new_matrix
    
    # 짝수인 경우엔, 제곱수로 계속해서 곱해집니다.
    # ex) AAAA -> (A^2) = AA -> (A^2)^2 = AAAA
    else:
        matrix = matmul(A, B//2)
        new_matrix = make_matrix(matrix, matrix)
    
        return new_matrix

N, B = map(int, input().split())

A = []
for _ in range(N):
    A.append(list(map(int, input().split())))

result = matmul(A, B)

for row in result:
    print(*row)