본문 바로가기

Algorithm10

[Algorithm] Union-Find(합집합 찾기) ※ Union-Find (합집합 찾기) : 대표적인 그래프 알고리즘으로, 서로소 집합 알고리즘이라고도 한다. 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 위와 같이 여러 개의 노드가 존재한다. 모두 연결되어 있지 않고, 각자 자기 자신만을 집합의 원소로 가지고 있을 때 모든 값이 자기 자신을 가리키도록 표현할 수 있다. 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 이때, 0과 1이 연결되었다고 해보자. 그러면 1의 인덱스 값에 '0'이 들어간다. 일반적으로 합칠 때에는 더 작은 값 쪽으로 합치고, 이를 합침(Union)이라고 한다. 0 1 2 3 4 5 6 7 0 0 2 3 4 5 6 7 1와 2이 연결된 경우는 어.. 2022. 4. 2.
[Algorithm] BFS & DFS ※ 너비 우선 탐색(BFS) : 탐색을 할 때, 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 너비 우선 탐색은 특히 '맹목적인 탐색'을 하고자 할 때 사용할 수 있는 탐색 기법으로 최단 길이를 보장해야 할 때 많이 사용됩니다. 너비 우선 탐색은 큐로 구현이 가능합니다. 너비 우선 탐색(BFS) 1. 맨 처음 시작 노드를 큐에 삽입하고, 방문 처리 2. 큐에서 하나의 노드를 꺼낸다. 3. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다. 4. 위와 같은 과정을 반복한다. 1. A를 큐에 넣는다. 2. A를 큐에서 꺼내고, 해당 노드에 연결된 노드 중 방문하지 않은 B와 C를 큐에 넣어준 후 방문 처리를 해준다. 3. B를 큐에서 꺼내 인접한 노드 중 방문한 적이 .. 2022. 3. 29.
[Algorithm] Stack & Queue ※ Stack? : 모든 원소들의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료구조 ※ Queue? : 컴퓨터의 기본적인 자료 구조의 한 가지로, 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First in First Out) 구조로 저장하는 형식 사실 스택과 큐는 알고리즘이라기보다 자료구조이다. 알고리즘은 스택이나 큐를 이용해서 문제를 해결하는 방법이라고 할 수 있다. 스택과 큐를 구현하는 것은 어렵지 않다. [Python Code - Stack 👩🏻‍💻] => 스택은 마지막으로 들어온 원소가 가장 처음으로 나가는 구조이기 때문에 pop() 함수를 사용해 마지막 값을 삭제한다. 따라서 7,4,9를 차례대로 넣어준 뒤 pop()을 하면 마지막에 들어온 9가 리스트에서 삭제되.. 2022. 3. 18.
[Algorithm] 계수 정렬 ※ 계수 정렬? 크기를 기준으로 세는 알고리즘 계수 정렬은 '범위 조건'이 존재하는 경우에 한해 굉장히 빠른 알고리즘이다. 다음의 5 이하 자연수 데이터들을 오름차순으로 계수 정렬해보자. [1,3,2,4,3,2,5,3,1,2,3,4,4,3,5,1,2,3,5,2,3,1,4,3,5,1,2,1,1,1] 1) 1부터 5까지 숫자의 개수를 셀 list를 만든다. 2) 데이터 셋을 돌면서 나오는 숫자에 해당하는 count를 +1 해준다. 3) 각각 count 한만큼 반복하여 출력(또는 list 원소 추가)한다. 이를 Python으로 구현한 Code는 다음과 같다. [Python Code 👩🏻‍💻] data_set = [1,3,2,4,3,2,5,3,1,2,3,4,4,3,5,1, 2,3,5,2,3,1,4,3,5,1,2.. 2022. 3. 14.
728x90

티스토리툴바