study

# 다익스트라 # a가 b에 의존함 => b에서 a로 갈 수 있다 from heapq import * import sys input = sys.stdin.readline t = int(input()) # 테스트 케이스 수 for _ in range(t): n, d, c = map(int, input().split()) # 컴퓨터 수, 의존성 개수, 해킹당한 컴퓨터 번호(시작점) graph = [[] for _ in range(n+1)] # 그래프 초기화 for _ in range(d): a, b, s = map(int, input().split()) # 컴퓨터a, 컴퓨터b, 감염되는데 걸리는 시간 graph[b].append([a, s]) # 의존하는 쪽으로 갈수있으니 b에 추가 time = [1e9] ..

""" 31120KB40ms """ # s를 t로 바꾸는게 가능한지. # 문자열의 뒤에 a 추가하기 # 문자열의 뒤에 b를 추가하고 뒤집기 # t에서 s만큼 될때까지 연산해서 s가 나오는지? s = list(input()) t = list(input()) def text_check(t): if t == s: # t와 s가 같다면 1 출력하고 종료 print(1) exit(0) if len(t) == 0: # t가 모두 삭제될 경우 return 0 if t[-1] == 'A': # A는 문자열의 뒤에 추가. -1에서 찾음 text_check(t[:-1]) if t[0] == 'B': # B는 문자열 뒤에 추가 + 뒤집기 = 앞에 와있음. 0에서 찾고 제거 후 뒤집기 text_check(t[1:][::-1]..

""" 53516KB276ms """ # 최소 여물. 다익스트라 from heapq import * import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b, c = map(int, input().split()) graph[a].append([b, c]) graph[b].append([a, c]) cost = [1e9 for _ in range(n + 1)] heap = [] cost[1] = 0 heappush(heap, [0, 1]) while heap: cur_cost, cur_node = heappop(heap) if cost[..

""" 31120KB44ms """ # 최종후보를 오름차순으로 출력 # 추천 시작 전에는 사진틀이 비어있음 # 추천하면 사진틀에 올라감 # 비어있는 사진틀이 없는 경우 - 추천횟수가 가장 작은거 삭제하고 추가함. 추천 횟수가 적은 학생이 두명 이상이면 오래된거 삭제함 # 게시된게 추천받으면 추천횟수간 증가 # 게시가 삭제되면 추천횟수는 초기화됨 import sys input = sys.stdin.readline n = int(input()) r = int(input()) student = list(map(int, input().split())) nominee = {} for i in student: # 빈 사진틀이 있을때 - 딕셔너리에 후보 : 추천수 로 추가 if len(nominee) < n: if ..

# 17점 # 제일 왼쪽(0)에서 제일 오른쪽(n-1)까지 가는 최소 비용. # 현재 가격이 다음 가격보다 비싸거나 같다면 - 필요한만큼만 사기 # 현재 가격이 다음 가격보다 싸다면 - 다음 길이까지 구매하기 n = int(input()) road = list(map(int, input().split())) oil = list(map(int, input().split())) cost = 0 for i in range(len(oil)-1): if i != 0 and oil[i-1] = oil[i+1]: cost += oil[i] * road[i] elif oil[i] < oil[i+1]: cost += (oil[i] * road[i]) + (oil[i]..

DP (Dynamic Programming) 하나의 문제를 여러개의 작은 문제로 나누어 해결하고 그 결과를 종합하여 정답을 구하는 알고리즘. 접근 방법 상향식 접근법(Bottom-Up) 작은 하위문제부터 시작해 큰 문제까지 차근차근 해결하는 방식 작은 문제들을 해결하고 결과를 저장한 후 그 결과를 이용해 보다 큰 문제를 해결함 보통 반복문을 이용해 구현함 하향식 접근법(Top-Down) 큰 문제를 작은 하위 문제들로 재귀적으로 나누어 해결하는 방식 재귀적인 호출을 이용해 작은 문제를 해결하고 그 결과를 이용해 큰 문제를 해결함 일반적으로 메모이제이션(Memoization, 결과를 구하고 나중에 다시 활용함) 기법을 사용해 중복 계산을 피함 예시) 피보나치 1 재귀로 구현 def fibonacci(n): ..

그리디(Greedy) 각 단계에서 최선의 선택을 하는 방식으로 문제를 해결하는 알고리즘. 각 단계에서 최선의 선택(부분 문제의 최적해)를 모두 합쳤을때 전체에서의 최선의 선택과 다르다면 풀이가 성립하지 않는다. 따라서 그리디하게 문제를 풀때는 풀이의 정당성을 증명해야한다. 보통 최적화 문제에서 사용된다. 특징 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 쪼개어 해결할 수 있는 문제 구조를 가진다. 그리디 알고리즘은 각 단계에서 부분 문제의 최적해를 찾는 방법으로 전체 문제의 최적해를 찾는다. 탐욕적 선택 속성 (Greedy Choice Property) 각 단계에서 최적해를 찾기 위해 가장 최선의 선택을 한다. 이 선택이 나중에 문제의 해결에 대한 최적해에 영향을 미치..

문제 설명 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데,..

문제 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다. 1초 동안 아래 적힌 일이 순서대로 일어난다. 미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다. (r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다. 인접..

1. 브루트 포스(Brute-force) 문제를 해결하기 위해 가능한 모든 경우를 다 따지며 해를 찾는 간단하고 직관적인 알고리즘. 모든 가능한 해를 찾아내는데 유용하지만, 문제의 크기가 커질수록 실행시간이 급격하게 증가하고 효율성이 낮아서 대부분은 다른 최적화 기법이나 다른 알고리즘을 사용한다. 보통 다음과 같은 과정으로 이루어진다. 후보 생성 : 모든 가능한 후보 해를 생성한다. 후보 평가 : 후보들을 평가하여 주어진 조건에 부합하는지 확인한다. 적합한 해 선택 : 문제의 요구조건에 따라 최적의 후보 해를 선택한다. 예시) 백준 1182번 부분 수열의 합 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램..