from palette import colorful_colors

1. 입출력 입출력을 빠르게 하기 위한 헤더 ios::sync_with_stdio(false); cin.tie(NULL); // cin과 cout을 빠르게 하기 위한 방법 // 대신 멀티쓰레드는 불가능, scanf, printf 등 사용 불가 한 줄에 여러개 입력 받기: # 예시: 1 2 4 3 5 를 list로 입력받고 정렬하고 싶을때: number = list(map(int, input().split())) number.sort() 여러줄에 여러개 입력받기 (List Comprehension 활용): comprehension과 list로 map을 묶어준다. # 예시: 라인을 받을 횟수 n을 입력받고 라인마다 push 1 ,.... 이런식으로 여러줄에 여러개가 있을때: n = int(input()) c..

import sys input = sys.stdin.readline # 입력받기 N = int(input()) for i in range(N): d.append(list(map(int, input().split()))) # 초기값 if N > 2: d[1][0] = d[0][0] + d[1][0] d[1][1] = d[0][0] + d[1][1] # 메모이제이션 하면서 계산 for i in range(2, N): for j in range(0, i+1): if j == 0: d[i][j] = d[i - 1][0] + d[i][j] elif j == i: d[i][j] = d[i - 1][j - 1] + d[i][j] else: d[i][j] = max(d[i-1][j-1] , d[i-1][j]) + d[..

점기준 회전으로 풀었다 모든 점들은 체커라는 리스트에 표시해서 나중에 정사각형 계산할때 더 빠르게 계산할 수 있도록 했다 import sys input = sys.stdin.readline N = int(input()) start_curbs = [list(map(int, input().split())) for _ in range(N)] # 시작점, 시작방향, 세대 checker = [[0 for _ in range(101)] for _ in range(101)] curbs = [] dx = [1, 0, -1, 0] # 우상좌아 dy = [0, -1, 0, 1] # a, b를 기준으로 x, y가 90도 회전 def rotate(a, b, x, y): x_tmp, y_tmp = x - a, y - b rot..

정사각형 회전부분만 해설을 참고했다 # 입력부 import sys input = sys.stdin.readline INF = 1e9 N, M, K = map(int, input().split()) # 미로 크기, 참가자 수, 게임시간 array = [list(map(int, input().split())) for _ in range(N)] # 격자 peoples = [] # 참가자들 for _ in range(M): a, b = map(int, input().split()) peoples.append((a - 1, b - 1)) a, b = map(int, input().split()) # 출구 exit_x, exit_y = a - 1, b - 1 total_movement = 0 # 모든 참가자 이동거..

import sys from collections import deque input = sys.stdin.readline N, M, K = map(int, input().split()) # 행, 열, 주사위 이동 횟수 array = [list(map(int, input().split())) for _ in range(N)] # 격자 맵 dice_x, dice_y = 0, 0 # 주사위 위치 dice = [1, 6, 3, 4, 5, 2] # 초기 주사위 (위, 아래, 동, 서, 남, 북) direction = 0 # 초기 방향은 동쪽 result = 0 dx = [0, 1, 0, -1] # 동남서북 dy = [1, 0, -1, 0] def rotate_dice(dice, direction): if dire..

난 상어가 무섭다 import sys from collections import deque input = sys.stdin.readline INF = 1e9 N = int(input()) array = [list(map(int, input().split())) for _ in range(N)] # 필요한 변수 초기화 shark_size = 2 eated_number = 0 # 상어 크기 증가를 위해 필요한 변수 time = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 초기 상어 위치 파악하기, 먹을 물고기 파악하기 for i in range(N): for j in range(N): if array[i][j] == 9: shark_x, shark_y = i, j array[i..

참고서적: 이것이 코딩테스트다 with 파이썬 graph를 이용해 최단거리를 이용하는 방법이다. 다익스트라는 특정 노드에서 다른 노드로 가는 최단거리를 구하는 방법이고, 시간복잡도는 짜는 방법에 따라 O(V^2), O(ElongV)다. (V는 간선의 개수, E는 간선의 개수) 간선은 모두 양수여야 한다. 플로이드 워셜은 모든 노드에서 모든 노드로 가는 최단거리를 구하는 방법이고, DP를 이용해 구한다. 시간복잡도는 O(V^3)이다. 음수 가중치 간선이 있어도 수행할 수 있다. 다익스트라 알고리즘 먼저 거리를 무한으로 초기화하고, 출발노드부터 시작해 방문하지 않은 노드를 선택해 인접한 다른 노드로 가는 비용을 체크한다. 이때 해당 노드를 거쳐 다른 노드로 가는 거리가 다른 노드의 기존 거리보다 작다면 갱신..

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈 메모리 공간을 더 사용하여 연산 속도를 증가시킬 수 있는 방법. ex) 점화식을 이용해 풀기 2가지 방법(top down, bottom up)이 있다. 예시: 피보나치 함수 # 피보나치 함수를 재귀로 구현할때 def pibo(x): if x == 1 or x == 2: return 1 else: return pibo(x-1) + pibo(x-2) print(pibo(4)) 이렇게 단순 재귀로 작성하면 n이 커질 수록 시간복잡도가 기하급수적으로 늘어난다. O(2^N) 따라서 dp를 이용한다. dp를 사용할 수 있는 경우: 1. 큰 문제를 작은 문제로 나눌 수 있다 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하..