전체 글

다이나믹 프로그래밍(DP : Dynamic Programming) 동적 계획법 목적 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장 한 번 해결한 문제는 다시 해결하지 않음 메모리를 사용해서 중복 연산을 줄임 배열 or 자료구조를 만듬 중복 연산을 줄여서 수행 속도를 개선 연산한 결과를 배열에 담음 기억하며 풀기(기억하기 알고리즘) 판단 기준 최적 부분 구조(Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 중복되는 부분 문제(Overlapping Substructure) 동일한 작은 문제를 반복적으로 해결 방식 탑 다운(Top-Down) : 하향식 -> 재귀로 구현 메모이제이션(Memoization) : 한 번 ..

LCS(Longest Common Subsequence) 최장 공통 부분수열(Longest Common Subsequence) : BCDF 또는 BCDE 최장 공통 문자열(Longest Common Substring) : BCD → F, E는 문자열을 건너뛰기 때문에 문자열로 인식하지 않음 점화식 if i == 0 or j == 0: # 마진 설정 LCS[i][j] = 0 elif string_A[i] == string_B[j]: # 문자열 앞에까지만 비교하고 마지막 끝에 값이 같으니 +1 LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]) 1. LCS[i - 1][j]와 LCS[i][j - 1]는 어떤..

1. 시간제한(30분 ~ 1시간)2. 안풀리면 과감히 답지보기3. 답지 한줄 한줄 이해할 때까지 보기https://www.youtube.com/watch?v=LBup2VMVHXw&t=11s날짜문제 번호유형복습일2024.04.051931.회의실 배정그리디 알고리즘2024.04.092024.04.061541. 잃어버린 괄호그리디 알고리즘2024.04.09 11047. 동전 0DP, 배낭 문제2024.04.092024.04.0912865. 평범한 배낭DP, 배낭 문제2024.04.10 1946. 신입사원DP, 정렬2024.04.11 9084. 동전DP, 배낭 문제 2024.04.167576.토마토BFS 2024.05.089012.단어 뒤집기문자열

2637. 장난감 조립 위상 정렬(Topological Sort)를 사용해 구현 진입 차수(in-degree) 완성품(7번)부터 큐에 추가 비용을 저장하는 배열을 선언하고 시작 지점(7번)의 비용을 1로 초기화(나머지는 0) 큐에 넣은 것을 빼고 인접한 노드들을 탐색하면서 비용을 갱신 갱신한 노드들의 진입 차수를 -1하고 진입 차수가 0인 것을 다시 큐에 추가하고 반복 cost[목적지] += cost[출발지] * 가중치(비용) arr2 배열을 통해 진입 차수가 없는 기본 부품을 판별하여 출력 import sys from collections import deque input = sys.stdin.readline n = int(input()) m = int(input()) arr1 = [[] for _ i..

2178. 미로탐색 BFS(Breadth First Search, 너비 우선 탐색)으로 해결 시작점을 1로 두고 기존값을 더해가면서 최단 거리 계산 import sys from collections import deque input = sys.stdin.readline y, x = map(int, input().split()) graph = [list(map(int, input().strip())) for _ in range(y)] for i in range(y): for j in range(x): if graph[i][j] == 1: graph[i][j] = 0 else: graph[i][j] = -1 visited = [[0] * x for _ in range(y)] deq = deque() dx =..

트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 장점 M개의 문자로 구성된 문자열을 추가와 탐색하는 시간 복잡도는 O(M) 문자열을 빠르게 탐색할 수 있음 단점 필요한 메모리의 크기가 너무 큼 모두 소문자로만 이루어졌다고 해도, 26개의 공간이 필요 플로이드 와샬(Floyd-Warshall) 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 알고리즘(방향, 음수 상관없음 / 싸이클이 발생하면 안됨) 단계마다 ‘거쳐 가는 노드’를 기준으로 알고리즘 수행 2차원 테이블에 최단 거리 정보를 저장 DP 알고리즘에 해당 시간 복잡도는 O(N^3) 노드의 개수가 N개 일 때, N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려한다. ..

1260. DFS와 BFS DFS(Depth First Search, 깊이 우선 탐색), BFS(Breadth First Search, 너비 우선 탐색)으로 구현 Stack과 Queue를 사용하고 방문처리를 통해 탐색 import sys from collections import deque input = sys.stdin.readline n, m, v = map(int, input().split()) arr = [[] for i in range(n + 1)] visited = [False for _ in range(n + 1)] deq = deque() for i in range(m): a, b = map(int, input().split()) arr[a].append(b) arr[b].append(a)..