Algorithm

문제 링크 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ 문제 해설 Idea root부터 조건을 만족하는 깊이까지 재귀적으로 자식 노드를 탐색하면서 p 또는 q 노드를 발견한 경우 해당 노드를 호출한 함수에게 반환 최종적으로 좌,우에 각각 p와 q가 있을 경우 깊이가 가장 깊은 부모 노드를 반환하고, 한쪽 방향에 p와 q가 몰려있을 경우 둘 중 부모 관계에 있는 노드를 반환 Time Complexity O(N) = 10^5 Data Size nodes: [2, 10^5] val: -10^9 <= int <= 10^9 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 # Definition for a binary tree node....

문제 링크 https://www.acmicpc.net/problem/10026 문제 해설 Idea 모든 방문하지 않은 칸에 대해 BFS 탐색하면서 같은 구역을 방문 적록색약의 경우 R과 G를 같은 구역으로 판단하고 탐색 각각의 경우에 대한 BFS 호출 횟수를 서로 다른 구역의 수로 판단하여 출력 Time Complexity BFS: O(N^2) = 10,000 Data Size N: 1 <= int <= 100 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 from collections import deque import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/21758 문제 해설 Idea 벌이 같은 방향을 향하는 경우 상자까지의 총합에서 두 벌의 시작 위치에 있는 값을 제외 벌이 다른 방향을 향하는 경우 상자까지의 총합에 절댓값을 취해서 더함 Data Size N: 3 <= int <= 100,000 arr[i]: 1 <= int <= 10,000 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 N = int(input()) arr = list(map(int, input().split())) forward, backward = [arr[0]]+[0]*(N-1), [0]*(N-1)+[arr[-1]] for i in range(1,N): forward[i] = forward[i-1] + arr[i] backward[N-i-1] = backward[N-i] + arr[N-i-1] answer = 0 for i in range(1,N-1): answer = max(answer, forward[N-1]*2-forward[0]-forward[i-1]-arr[i]*2) answer = max(answer, backward[0]*2-backward[N-1]-backward[N-i]-arr[N-i-1]*2) answer = max(answer, forward[i]-arr[0]+backward[i]-arr[-1]) print(answer)

문제 링크 https://www.acmicpc.net/problem/5547 문제 해설 Idea 전체 좌표 평면의 외곽에 1만큼의 여백을 추가하고 x,y 좌표가 0부터 시작한다고 판단 y가 홀수 일 때, 인접한 좌표는 상하좌우와 함께 우상단,우하단을 포함 y가 짝수 일 때, 인접한 좌표는 상하좌우와 함께 좌상단, 좌하단을 포함 건물이 없는 좌표를 BFS 탐색하면서 건물과 만나는 지점을 카운트 Time Complexity BFS: O(N^2) = 10,000 Data Size W, H: 1 <= int <= 100 해설 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 from collections import deque import sys input = sys....

문제 링크 https://www.acmicpc.net/problem/1308 문제 해설 Idea 각각의 날짜에 대한 문자열을 date 타입으로 변환하고, today 기준 1000년 후 날짜와 dday를 비교 조건이 맞을 경우 ‘gg’를 출력하고, 아니면 두 날짜의 차이를 출력 Data Size y,m,d: 1,1,1 <= int*3 <= 9999,12,31 해설 코드 1 2 3 4 5 6 7 from datetime import date strptime = lambda: date(**{k:int(v) for k,v in zip(['year','month','day'],input().split())}) today, dday = strptime(), strptime() if dday >= today.replace(today.year+1000): print('gg') else: print('D-'+str((dday-today)....