CS/알고리즘

유니온 파인드(Union Find)유니온 파인드는 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.유니온 파인드는 노드가 어떤 경로에 있는지 보다 서로 연결되어 있는지를 확인하기 위한 알고리즘이다. (같은 집합인지 확인)대표 노드를 저장하는 배열을 초기화한다. 최초에는 인덱스 값을 그대로 저장 배열에 넣어준다. 처음에 각 노드들이 연결되어 있지 않고 서로 독립적으로 세팅되기 때문에 자기 자신이 대표 노드가 된다.유니온 연산을 통해서 하나의 집합 즉, 노드간 연결을 해준다. (대표 노드를 비교하여 더 작은 값을 대표 노드로 설정한다.)처음에 유니온 연산이 가능한 이유는 초기에는..

정렬(Sort)정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.그럼 정렬은 왜 하는 걸까??내가 편의점에서 아르바이트할 때를 생각해 보면 음료 진열대 뒤쪽에서 음료들을 하나씩 넣어가면서 진열해야 된다. 여기서 중요한 것은 유통기한이 빠른 순서대로 넣는 것이다. 하지만 창고에 쌓인 음료들을 보면 유통기한이 빠른 순서대로 정렬되지 않은 경우를 많이 경험했다.창고에 있는 음료들의 유통기한을 빠른 순서대로 정렬하면 진열대에 음료를 넣을 경우 더 빠르게 작업을 할 수 있을 것이다.이러한 정렬 알고리즘에는 어떤 종류가 있는지 확인해 보면종류설명시간복잡도메모리안정성최고평균최악버블 정렬(Bubble Sort)데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는..

DFS(깊이 우선 탐색)그래프 완전 탐색 기법 중 하나로 코딩 테스트에서 가장 많이 사용되는 알고리즘이다.DFS(너비 우선 탐색)의 원리그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.재귀 함수 or 스택 자료구조를 이용하여 구현한다. (후입 선출 특성을 가지고 있음)시간 복잡도는 O(V + E) - V: 노드 수, E: 에지 수한 번 방문한 노드는 다시 방문하면 안되며 따라서 노드 방문 여부를 체크할 배열이 필요하다.위의 그래프를 사진과 같이 인접 리스트로 표현할 수 있다.※ DFS를 구현할 경우 재귀 함수를 이용하기 때문에 스택 오버플로우에 유의해야 한다.DFS는 어떤 한 분기를 먼저 최대 깊이까지 ..