알고리즘 썸네일형 리스트형 [알고리즘] disjoint-set(union find) 알고리즘 1. union find(disjoin-set)란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 다수의 노드들 중에 연결된 노드를 찾거나, 노드들을 합칠 때 사용하는 알고리즘 1~10까지 있다고 가정할 때, 아래와 같은 연결 구조를 가지고 있다고 가정하자. [ 진행과정 ] 1과 2가 연결되었으면, 원소 2의 정보를 1로 바꾼다. 1, 2, 3, 4가 모두 연결되어있어 같은 집단에 속하지만, 처음에는 각자의 부모노드를 작성한다. 3과 2는 연결되어있다. -> 3의 연결정보를 2로 바꾼다. -> 2와 1은 연결되어있다. -> 3과 1은 연결되어있으므로 3의 연결정보를 1로 바꾼다. 구현 초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화 Union(합치.. 더보기 [알고리즘] LCS 알고리즘 1. LCS 알고리즘이란? - LCS = 최장 공통부분 문자열 - Substring : 연속된 부분 문자열 ex. x = 'CCAYCKP' y = 'CCAPCAK' - Subsequence : 연속되지 않은 부분 문자열 ex. x = 'ACAYKP' y = 'CAPCAK' 2. LCS 알고리즘 구현 (LCS 길이찾기) 문제 : [백준] 9251. LCS https://www.acmicpc.net/problem/9251 [풀이과정] 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 3 3 4 P 0 1 2 3 3 3 4 x와 y에 가장 최근에 추가된 글자가 서로 같으면 b.. 더보기 이전 1 다음
