느낌표 공장

n, k = map(int, input().split()) # 물품의 수 n, 버틸 수 있는 무게 k arr = [[0, 0]] + [list(map(int, input().split())) for _ in range(n)] # [물건의 무게, 물건의 가치] dp = [[0 for _ in range(k+1)] for _ in range(n+1)] for i in range(1, n+1): w = arr[i][0] # 현재 물건의 무게 v = arr[i][1] # 현재 물건의 가치 for j in range(1, k+1): if j < w: # 무게 j보다 현재 물건의 무게가 더 무겁다면 dp[i][j] = dp[i-1][j] # 바로 이전 물건, 같은 무게로 채우기 else: # 무게 j보다 현재 물건..

for문 풀이 n, s = map(int, input().split()) # 숫자 개수 n, 목표 합 s numbers = list(map(int, input().split())) # 숫자들 tmp_sum = 0 # 임시 숫자들의 합을 저장할 변수 answer = 128349127598217598718296792 # 길이 크게크게 설정 (가장 짧은 것을 구하는 것이므로) p = 0 # 움직일 포인터 (왼쪽) for i in range(n): # i == 오른쪽 포인터 tmp_sum += numbers[i] # i번째 숫자 더하기 if s

Dijkstra 알고리즘이란 ? 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 음의 간선이 존재하지 않는, 간선의 값이 0 이상의 양수일 때 정상적으로 동작한다. 우선 순위 큐(heapq)를 사용한다. 동작 원리 단계 인접 리스트를 만든다. 최단 거리 테이블을 무한대의 값으로 초기화한다. 현재 노드에서 갈 수 있는 노드 다 가져온다. 현재 노드에서 다음 노드로 가는 간선 비용을 계산하여 가중치 테이블을 업데이트 한다. 3번과 4번을 반복한다. 문제 SWEA - 5251. 최소이동거리

Union-Find 란? Disjoint Set을 표현할 때 사용하는 알고리즘 그렇다면 Disjoint Set(서로소 집합, 상호 배타 집합) 이란 ? 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다. 집합에 속한 하나의 특정 멤버(root node)를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 상호 배타 집합을 표현하는 방법 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 연결 리스트보다 효율적이다. 연결 리스트 같은 집합의 원소들은 하나의 연결 리스트로 관리 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다. 상호 배타 집합 연산 m..

from itertools import combinations def solution(relation): relation_r = list(zip(*relation)) # 돌린거 col = len(relation_r) # 컬럼 개수 row = len(relation) # 행 개수 result = 0 # 유일성 만족하는 컬럼 1개 개수 not_candi = [] # 유일성 만족하지 못하는 컬럼 for i in range(col): if row == len(set(relation_r[i])): # 유일성을 만족하면 result += 1 # +1 else: not_candi.append(i) # 유일성을 만족하지 못하는 컬럼 리스트에 추가 make_candi = [] for i in range(2, len(no..

def solution(n, t, m, timetable): timetable.sort() # 타임테이블 정렬 crew_n = len(timetable) # 타임테이블 개수 for i in range(crew_n): # 시간표를 분으로 전환 hour, minutes = map(int, timetable[i].split(':')) timetable[i] = hour * 60 + minutes bus_time = 9 * 60 - t # 버스 처음 시간 p = 0 # 크루 포인터 for bus in range(1, n + 1): bus_time += t # 버스 시간 passenger = 0 # 탑승 크루 수 for crew in range(p, crew_n): # 안탄 크루들 태우기 if timetable[..

def solution(record): id_nick = {} # id에 따른 닉네임 저장 log = [] # 들어왔다 나갔다 기록 for rec in record: rec = rec.split() # 띄워쓰기 기준으로 분리 if rec[0] == 'Enter': # 채팅방에 들어온 경우 id_nick[rec[1]] = rec[2] # id를 키로, nickname을 value로 저장 log.append((rec[1], '님이 들어왔습니다.')) # 채팅방 출입 기록에 저장 elif rec[0] == 'Leave': # 채팅방 나간 경우 log.append((rec[1], '님이 나갔습니다.')) # 채팅방 출입 기록에 저장 else: # 닉네임 수정한 경우 id_nick[rec[1]] = rec[2] ..

def binary_search(num): s = 1 e = len(lis)-1 while s

def binary_search(t_num): s = 0 # 시작, 마지막 포인트 초기화 e = n1 - 1 while s t_num: # 중간지점 값이 목표 숫자보다 크다면 e = m - 1 # 시작 ~ 중간 범위 설정 else: # 중간지점 값이 목표 숫자보다 작다면 s = m + 1 # 중간 ~ 끝 범위 설정 return 0 # 수첩 1에 숫자 없는 경우 tc = int(input()) for _ in range(tc): n1 = int(input()) # 수첩 1에 적어놓은 정수의 개수 number1 = sorted(set(map(int, input().split()))) # 수첩 1에 적힌 숫자들 n1 = len(number1) n2 = int(input()) # 수첩 2에 적어놓은 정수의 개수..

from collections import deque # 상 하 좌 우 dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] def bfs(sy, sx, hour): queue = deque([(sy, sx, hour)]) # 시작지점 추가하고 시작 visited = [[0 for _ in range(garo)] for _ in range(sero)] # 방문한 곳 다시 방문하지 못하도록 만든 리스트 visited[sy][sx] = 1 # 시작지점 방문처리 while queue: y, x, hour = queue.popleft() # 좌표 하나 가져오기 for i in range(4): ny = y + dy[i] nx = x + dx[i] if 0