CSE STUDY BLOG

LCS(Longest Common Subsequence, 최장 공통 부분 수열) LCS (Longest Common Subsequence)최장 공통 부분 수열두 문자열이 주어졌을 때, 두 문자열 모두에 순서를 유지하며 등장하는 가장 긴 부분 수열ex ) ACAYKP와 CAPCAK의 LCS는 길이가 4인 ACAK만약 brute force로 길이가 N인 문자열에 대해서 부분 수열을 구한다면? - > 2^N의 시간복잡도이를 다시 길이가 M인 문자열에 대해 확인해본다면 대략 O(2^N × M) .. 시간 초과DP (동적 계획법, Dynamic Programming) LCS는 문자열 각 문자의 위치에 대한 연산이 반복됨DP는 작은 문제의 답을 저장해두고, 이를 이용해 큰 문제의 답을 빠르게 구하는 방식ACAYKP..

DFS( Depth-First Search ), BFS( Breadth-First Search ) DFS (Depth-First Search, 깊이 우선 탐색)시작 정점을 방문한 후 하나의 인접 정점을 따라 계속 방문.더 이상 방문할 정점이 없으면 되돌아와 다른 정점을 탐색함.재귀 함수나 스택으로 구현 가능 스택의 LIFO(Last In Frist Out)를 고려해서 스택에 담기는 노드의 순서는 다음과 같다.EMPTY18,7,28,7,6,38,7,6,5,48,7,6,58,7,68,7812,912,11,1012,1112EMPTYBFS (Breadth-First Search, 너비 우선 탐색)시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문Queue 사용 (LinkedList로 구현) 큐의..

DFS + Backtracking 을 이용한 구현DFS (Depth-First Search, 깊이 우선 탐색)트리나 그래프를 탐색하는 방식 중 하나한 갈래를 끝까지 파고든 뒤, 막히면 되돌아가서 다른 갈래 탐색재귀 함수나 스택으로 구현 가능백트래킹 (Backtracking)DFS의 일종의 응용 기법어떤 조건을 만족하지 않으면, 그 분기에서 더 이상 탐색하지 않고 되돌아감(백트랙)즉, 가능성이 없는 경로는 일찍 포기함으로써 탐색 효율을 높임 순열/조합은 가능한 모든 경우를 탐색 - > DFS조건(중복 방지, 순서 조건 등)에 맞지 않는 경우를 잘라냄(Pruning) -> Backtracking 관련 문제백준 N과 M 시리즈https://www.acmicpc.net/workbook/view/7315 1...