본문 바로가기

computer science/알고리즘17

[알고리즘] Union-Find 알고리즘 Union-Find알고리즘은 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불립니다. 여러 노드가 존재할 때, 선택한 두개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 입니다. Union-Find 알고리즘에서는 두 노드를 Union연산, 즉 두 노드를 같은 그래프에 합치는 과정과 Find연산, 두 노드가 같은 그래프에 존재하는지를 확인합니다. 위에서와 같인 5개의 서로 연결되지 않은 채로 흩어져 있습니다. 여기서 각 노드들의 연결성을 프로그래밍 적으로 파악하기 위해 1차원 배열을 사용할 수 있습니다. index는 노드, index의 값은 부모노드를 의미합니다. 지금은 모두 독립적으로 존재하기 때문에 부모노드의 값을 현재의 index로 초기화 해줍니다. 여기서 두개의 노드.. 2020. 9. 15.
[알고리즘] 기수 정렬(Radix Sort) 이번 시간에는 기수정렬(Radix Sort)에 대해 공부해 보겠습니다. 개인적으로 기수 정렬을 배우면서 이런 방법으로도 정렬할 수 있구나, 라는 생각을 했고 굉장히 신선했습니다. 기수정렬은 각 숫자의 일의 자리, 십의 자리, 백의 자리....를 기준으로 숫자를 정렬하는 방법입니다. 이때 각 기준숫자는 0~9 범위에 포함되는데 이를 관리하기 위해 0 ~ 9, 총 10개의 queue를 만들어 줍니다. [200, 152, 2, 0, 32, 45, 99, 87] 를 한번 보겠습니다. 1. 일의 자리를 기준으로 정렬 이를 배열로 다시 표현해보겠습니다. 0에서 부터 시작하며 queue이기 때문에 선입선출 입니다. [200, 0, 152, 2, 32, 45, 87, 99] 2. 십의 자리를 기준으로 정렬 일의 자리를.. 2020. 5. 26.
[알고리즘] 계수 정렬(Counting Sort) 이번시간에는 계수 정렬에 대해 공부해보겠습니다. 계수 정렬의 시간 복잡도는 O(n)입니다. n번만에 숫자를 정렬할 수 있습니다 ! 다른 빠르다는 정렬 알고리즘도 O(nlongn)시간을 가지는데 계수 정렬은 어떻게 O(n)시간을 가질까요 ? 먼저 다음의 숫자를 계수정렬을 사용하여 정렬해 보겠습니다. 계수정렬은 각 숫자의 빈도수를 체크하여 정렬합니다. 5 0 0 2 3 1 1 3 4 배열에 숫자의 빈도수가 체크되어있고 [2,2,1,2,1,1,] 그대로 출력하면 0 0 1 1 2 3 3 4 5가 됩니다. 하지만 계수정렬에는 몇가지 문제점이 있습니다. 1. 정렬 대상이 단순 정수가 아니라면 ? 만약 { 이름, 주소, 나이 } 정보를 가진 사람을 나이순으로 정렬해야 한다면? 위의 방법이라면 '나이'순으로는 정렬할.. 2020. 5. 26.
[알고리즘] 합병정렬(Merge Sort) 이번 시간에는 합병정렬에 대해 공부해보겠습니다. 합병정렬은 앞서 설명한 퀵정렬화 함께 무척 빠른 정렬속도(O(nlogn))을 자랑하기 때문에, 반드시 알고 있어야 합니다 ! 합병정렬은 분할정복 기법을 사용하여 문제를 해결하는 방법입니다. 분할정복은 해결할 수 없는 큰 문제를 해결할 수 있는 작은 단위의 문제로 나누고(분할) 해결한 후, 다시 합치는 합치는(정복)하는 과정입니다. 이 과정을 계속 반복하면서 정렬해 나가는 방법이 합병정렬 입니다. 일단 글보다는 실제로 정렬을 하면서 설명을 해보겠습니다 !! 여기서 l은 왼쪽부분, r은 오른쪽 부분입니다. [3 8 12 6 22 15 30 1] l r [ 3 8 12 6 ] [ 22 15 30 1 ] l r l r [ 3 8 ] [ 12 6 ] [ 22 15 .. 2019. 6. 1.

티스토리툴바