전체 글

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)..

프로세스(Process) 실행중인 프로그램을 나타냄 프로세스의 문맥(Context) 프로그램이 무엇을 어떻게 실행했고, 현재 시점에 어떠한 상태인지 나타내기 위한 요소 CPU의 수행 상태를 나타내는 하드웨어 문맥 Program Counter 각종 레지스터 프로세스의 주소 공간 code, data, heap, stack 프로세스 관련 커널 자료 구조 PCB(Process Control Block) -> 프로세스가 실행될 때마다 관리하는 구조체 생성(이중 연결 리스트) 운영체제가 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보 OS가 관리상 사용하는 정보 프로세스 ID, 프로세스 상태 스케쥴링 정보, 우선순위 CPU 수행 관련 하드웨어 값 Program Counter, 레지스터 메모리 관련 code, ..