알고리즘

이모티콘 [백준 14226] - python

from collections import deque import sys input = sys.stdin.readline def BOJ14226() : S = int(input().strip()) graph = [[-1 for _ in range(S+1)] for _ in range(S+1)] # 개수 별 최소 시간 graph[1][0] = 0 def bfs() : queue = deque() queue.append([1, 0]) while queue : curr_node, curr_clip = queue.popleft() # 클립 보드에 현재 화면에 있는 것을 넣는 과정 if graph[curr_node][curr_node] == -1 : graph[curr_node][curr_node] = graph..

멀티탭 스케줄링 [백준 1700] - python

INF = 1e6 import sys input = sys.stdin.readline def BOJ1700() : N, K = map(int, input().split()) arr = list(map(int, input().split())) count = 0 plugins = [] for i in range(K) : if arr[i] in plugins: continue if len(plugins) < N : plugins.append(arr[i]) continue after_use_index = [] remains = arr[i:] for j in range(N) : if plugins[j] not in remains : after_use_index.append(101) continue after_us..

감소하는 수 [백준 1038] - python

# 조합을 이용한 코드 from itertools import combinations import sys input = sys.stdin.readline def BOJ1038() : N = int(input()) answers = [] for i in range(1, 11) : for comb in combinations(range(0, 10), i) : comb = list(comb) comb.sort(reverse=True) answers.append(int("".join(map(str, comb)))) answers.sort() try : print(answers[N]) except : print(-1) BOJ1038() # https://ryu-e.tistory.com/59 # 재귀를 이용한 코드..

사탕 게임 [백준 3085] - python

풀이 접근 방법 : 1. 브루트 포스로 풀어주었다. O(n^4)이 나올걸로 예상했는데 최대 N의 크기가 50이라 괜찮을것 같았다. 2. 백트래킹을 잘 적용했고 행과열 에서 최댓값 가져오는 로직도 잘 나온것 같다 import sys input = sys.stdin.readline def BOJ3085() : directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] def getMaxiMumCandy(arr) : n = len(arr) answer = 1 for i in range(n) : cnt = 1 for j in range(1, n) : if arr[i][j] == arr[i][j-1] : cnt += 1 else : cnt = 1 answer = max(answer, c..

최소비용 구하기 [백준 1916] - python

INF = 1e10 import heapq import sys input = sys.stdin.readline def BOJ1916() : N = int(input()) M = int(input()) graph = [[INF for _ in range(N+1)] for _ in range(N+1)] for _ in range(M) : A, B, C = map(int, input().split()) graph[A][B] = min(graph[A][B], C) start, end = map(int, input().split()) dist = [INF for _ in range(N+1)] # 다익스트라 def dijkstra(start) : dist[start] = 0 heap = [] heap.append(..

동전 2 [백준 2294] - python

import sys input = sys.stdin.readline def BOJ2294() : n, k = map(int, input().split()) coins = [] for _ in range(n) : coins.append(int(input().strip())) dp = [1e6 for _ in range(k+1)] dp[0] = 0 for i in range(1, k + 1) : for coin in coins : if i - coin >= 0 : dp[i] = min(dp[i], dp[i-coin] + 1) if dp[-1] == 1e6 : print(-1) else : print(dp[-1]) BOJ2294() 접근 방법 : 1. 입력받은 가치를 만들어 낼 수 있는 동전의 최소개수를 구하..

부분 문자열 [백준 16916] - python

import sys input = sys.stdin.readline def BOJ16916() : # 접두사와 접미사 개념 def make_table(pattern) : table = [0 for _ in range(len(pattern))] j = 0 for i in range(1, len(pattern)) : while j > 0 and pattern[i] != pattern[j] : j = table[j-1] if pattern[i] == pattern[j] : j += 1 table[i] = j return table def KMP(parent, pattern, table) : j = 0 for i in range(len(parent)) : while j > 0 and parent[i] != pa..

부분합 [백준 1806] - python

import sys input = sys.stdin.readline def BOJ1806() : N, S = map(int, input().split()) l = list(map(int, input().split())) f_p = 1 s_p = 0 result = 1e10 s = [0, l[0]] for i in range(1, len(l)) : s.append(l[i] + s[i]) if S > s[-1]: print(0) return while f_p

빙산 [백준 1062] - python

from dataclasses import replace from itertools import combinations import sys input = sys.stdin.readline def BOJ1062() : def replace_antatica(words) : words = words.replace('a', '') words = words.replace('n', '') words = words.replace('t', '') words = words.replace('i', '') words = words.replace('c', '') return words N, K = map(int, input().split()) words = [] for _ in range(N) : words.append(in..

빗물 [백준 14719] - python

import sys input = sys.stdin.readline def BOJ14719() : H, W = map(int, input().split()) l = list(map(int, input().split())) graph = [[0 for _ in range(W)] for _ in range(H)] for i in range(H) : for j in range(W) : if l[j] == H - i : graph[i][j] = 1 l[j] -= 1 for i in range(H) : start = -1 end = -1 for j in range(W) : if graph[i][j] == 1 : if start != -1 : end = j for k in range(start + 1, end) :..