10000COW

문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 더보기 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 예제 입력 1 복사 ACAYKP CAPCAK 예제 출력 1 복사 4 문제 유형 DP 문제 풀이 문제를 풀기 위해서 한 문자열을 기준으로 잡고, 한 글자씩 추가하면서 지금까지의 부분 문자열의 'LCS(최장 공통 부분 수열)'이 몇 개인지 기록해나간다. 주어..

2-3-4 트리란? 탐색트리 중 하나로, 이진 트리가 아니다. 즉, 자식 노드가 2개보다 많을 수 있다. 특징으로 1. 이름처럼 자식 노드의 개수는 2개 또는 3개 또는 4개를 가질 수 있다. (즉, 최소 2개 ~ 최대 4개) 2. 모든 leaf 노드가 같은 level에 존재한다. 3. 삽입 시, leaf 노드에 삽입한다. 삽입 추가할 key가 root부터 leaf 노드까지 내려가면서, 4-노드이면 split하면서 내려간다. split할 때 중간 값은 부모 노드로 무조건 올라갈 수 있는데, 그 이유는 key가 내려오면서 4-노드인 경우 split을 이미 해놨기 때문이다. split하는데 O(1)이 걸리고, 최악의 경우 leaf노드까지 내려가면서 매번 split 해야하므로(log n번), 삽입 시의 시간복..

벨만-포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 음의 가중치를 갖는 edge(간선)이 있을 때 사용하는 알고리즘이다. 다익스트라 알고리즘과 차이는 무엇인가? 다익스트라 알고리즘 - 매번 방문하지 않는 노드 중에서 최단거리가 가장 짧은 노드를 선택해 최단 거리를 구해나간다. - 음의 가중치를 갖는 edge(간선)이 없다면 최적의 해를 찾을 수 있다. - 시간 복잡도가 빠르다. 벨만-포드 알고리즘 - 매 단계마다 모든 edge(간선)을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. - 음의 가중치를 갖는 edge가 있어도 최적의 해를 찾을 수 있다. - 시간 복잡도가 느리다. 즉, 모든 edge의 가중치가 양수일 때는 다익스트라 알고리즘을, 음의 가중치를 갖는..

들어가기 전에 다익스트라 알고리즘을 이해하기 위해 여러 유튜브와 블로그를 방문했었는데 대체로 설명이 어렵거나 생략이 많다.. 코드 설명도 자세하지 않아 아쉬움이 있었다. (특히, 블로그에 있는 표나 그림은 왜이렇게 딱딱한걸까.. 잘 모르는 사람에겐 거부감이 든다) 직접 하나하나 그려가보며 이해한 나의 깨달음을 다른 분들께 자세하고 쉽게, 마치 아무것도 모르는 어린 아이에게 설명하듯이 설명해보려고 한다. 그리고 시간이 지나면 잊어버리는 미래의 나를 위하여 상세히 기술해보았다. 자세한 예시부터 점점 과정을 추상화해나가므로 이해하기 쉬울 것이라고 생각한다. 다익스트라 알고리즘이란? 그래프의 한 정점(Vertex 또는 Node)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘으로, 최단 경로 문제에 사용된다..

B-트리란? B-트리(B-tree)는 데이터베이스와 파일 시스템에 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드에 여러 개의 데이터를 저장한다. 차수가 p인 B-트리의 특성 1)적어도 노드의 반은 채워야 한다. 즉, root와 leaf를 제외한 모든 노드의 pointer 수 = 서브트리 수 = 최소 ⌈p / 2⌉개, 최대 p 개 2) root는 pointer를 2개 이상 가져야 한다. 즉, root의 서브트리의 수 >= 2 3) 모든 leaf는 같은 level (즉, 균형 트리이다) 4) 노드의 key 개수 leaf가 아닌 노드: pointer 수 - 1 개 = 서브트리 수 - 1개 (아래 B-트리 기본 구조 그림을 보면, key의 개수는 (pointer 개수 - 1)일 수 밖..