알고리즘/문제풀이

[구현] BOJ 21608 상어 초등학교

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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 import sys input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().split())) for _ in range(N * N)] arr_dict = {} for a in arr: arr_dict[a[0]] = set(n for n in a[1:]) board = [[0] * N for _ in range(N)] DELTAS = ((1, 0), (0, 1), (-1, 0),..

[DP] BOJ 1509 펠린드롬 분할

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 33 34 import sys sys.setrecursionlimit(10 ** 8) input = lambda: sys.stdin.readline().rstrip() arr = input() N = len(arr) p = [[0] * N for _ in range(N)] dp = [N] * (N + 1) for i in range(N): # 1개짜리 문자열 p[i][i] = 1 for i in range(N - 1): # 2개짜리 문자열 if arr[i] == arr[i + 1]: p[i][i + 1] = 1 for interval in range(..

[DP] BOJ 10942 펠린드롬?

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 import sys input = sys.stdin.readline N = int(input()) + 1 arr = [0] + list(map(int, input().split())) M = int(input()) dp = [[0] * N for _ in range(N)] # dp table initialization for i in range(N): dp[i][i] = 1 for i in range(N-1): if arr[i] == arr[i + 1]: dp[i][i + 1] = 1 for interval in range(2, N): # 간격 설정 for start in range(N-..

[이분탐색] BOJ 1477 휴게소 세우기

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 import sys input = sys.stdin.readline N, M, L = map(int, input().split()) arr = [0] + list(map(int, input().split())) + [L] # ...!! 0과 끝값까지 고려를 해야한다..! arr.sort() def bin_search(arr): start, end = 1, L answer = 0 while start mid: cnt += (arr[i] - arr[i-1] - 1) // mid # -1을 안하면 휴개소 포함 if cnt > M: start = mid + 1 else: a..

[수학] BOJ 1111 IQ Test

전형적인 수학문제로 문제를 풀었다. 나중에 다른분들 풀이 보니까 bruteforce 방식으로도 풀 수 있는 모양. 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 33 34 35 36 37 38 39 40 41 import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) # y = ax + b -> a == 기울기, b == y 절편 # a = x2 - x1 / x1 - x0 -> 기울기는 3개부터 구할 수 있다. # y = ax + b -> arr[i+1] = a * arr[i] + b # b..

[BFS] BOJ 13859 숨바꼭질 3

https://www.acmicpc.net/problem/13549 3개의 연산의 우선순위 때문에 99%에서 자꾸 틀렸다고 떠서 애를 먹었다. 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 33 34 import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) DELTAS = (lambda x: x - 1, lambda x: 2 * x, lambda x : x + 1) # 순서가 반드시 x-1, x*2, x+1의 순으로 진행되어야 함 LIMIT = 100000 # bfs def ..

[정렬] BOJ 18869 멀티버스 Ⅱ

https://www.acmicpc.net/problem/18869 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 import sys import math from collections import defaultdict input = sys.stdin.readline M, N = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(M)] indeces = defaultdict(int) for items in arr: items = {item: i for i, item in enumerate(items)} index = [items[item] for item in s..

[시뮬레이션] BOJ 17144 미세먼지 안녕!

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980import sysimport copyinput = sys.stdin.readline DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))R, C, T = map(int, input().split())arr = [list(map(int, input().split())) for _ in range(R)] # 시뮬레이션 문제 def diffuse(arr): new_arr = copy.deepcopy(arr) for y..

[BFS] BOJ 7576 토마토

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 33 34 35 36 37 38 39 40 41 42 43 44 import sys from collections import deque input = sys.stdin.readline M, N = map(int, input().split()) box = [list(map(int, input().split())) for _ in range(N)] DELTAS = ((1, 0), (0, 1), (-1, 0), (0, -1)) visited = [[-1] * M for _ in range(N)] def bfs(arr, visited): queue = de..

[DP] BOJ 2240 자두나무

https://www.acmicpc.net/problem/2240 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import sys from itertools import combinations input = sys.stdin.readline T, W = map(int, input().split()) tree = [0] + [int(input())-1 for t in range(T)] dp = [[0] * (W + 1) for _ in range(T + 1)] # W * T의 배열 for i in range(1, T+1): # 전혀 움직이지 않았을 경우 초기화 if tree[i] == 0: dp[i][0] = dp[i-1][0] + 1 e..

[백트래킹, 시뮬레이션] BOJ 12100 2048(easy)

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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 import sys import copy input = sys.stdin.readline N = int(input()) board = [list(map(int, input().split())) for _ in ra..

[그래프] BOJ 4195 친구 네트워크

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 33 34 35 36 37 38 39 40 41 42 import sys input = sys.stdin.readline from collections import defaultdict def find(parent, x): if x != parent[x]: parent[x] = find(parent, parent[x]) return parent[x] def union(parent, parent_cnt, a, b): a = find(parent, a) b = find(parent, b) if a != b: parent[b] = a parent_cnt[a..