알고리즘 (5) 썸네일형 리스트형 [알고리즘] 유니온 파인드(Union-Find) (Swift) 유니온 파인드 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 서로소 집합, Disjoint-Set 알고리즘이라고도 불림 부모노드를 찾는 Find 연산, 노드를 합치는 Union 연산으로 이루어져있음 위의 이미지에서 1과 6이 같은 그래프에 속하는지 판별할 수 있는 알고리즘 입니다. Find 연산 부모노드를 찾는 Find 연산을 구현하려 합니다. parent 라는 이름을 지어준 Int 배열을 사용할 것이고, parent[1] = 3 의 의미는 1번 노드의 부모는 3이다. 라고 정의할 수 있습니다. 먼저, 아무 노드도 연결되어 있지 않다고 가정한다면 현재 노드의 부모노드는 자기 자신일 것입니다. 0번 인덱스는 사용하지 않고, 단순히 번호를 맞춰주기 위해서 0번 인덱스부터 시작하였습니다. 이 그림과.. [알고리즘] 버블 정렬 (Swift) 버블 정렬이란? 현재 원소와 바로 다음 원소의 값을 비교하여 조건에 맞으면 교환하는 방식으로 정렬합니다. 원소의 이동이 거품이 수면으로 올라오는 것과 비슷한 모습을 보이기에 버블 정렬이라는 이름이 지어졌다고 합니다. 동작 방식 [5, 1, 3, 9, 4, 2, 7, 8, 6] 이라는 Int 배열이 있다고 가정해보겠습니다. 오름차순으로 정렬하려면 어떤식으로 동작할까요? Step 1 현재 원소 5와, 다음 원소 1과 비교합니다. 5가 더 크기 때문에 5와 1의 위치를 변경합니다. 현재 원소 5와 다음 원소 3과 비교합니다. 5가 더 크기 때문에 5와 3의 위치를 변경합니다. 현재 원소 5와 다음 원소 9를 비교합니다. 9가 더 크기 떄문에 위치를 변경하지 않습니다. 이것을 계속 반복하면 배열이 다음과 같이 .. [알고리즘] 에라토스테네스의 체 (Swift) 에라토스테네스의 체 에라토스테네스의 체 알고리즘은 고대 그리스 수학자인 에라토스테네스가 만들어낸 소수를 찾는 알고리즘 입니다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다고 하네요. 방법 예를 들어 1 ~ 100까지의 숫자 중 소수를 찾는다고 생각해 봅시다. 먼저, 1부터 100까지의 수를 쭉 써줍니다. 코드상으로는 101만큼의 크기인 Boolean Array를 true로 초기화를 해줬습니다. 표로 나타내보면, 이렇게 나타낼 수 있겠네요. 1은 소수가 될 수 없기에 제거해줍니다. 2를 제외한 2의 배수를 제거합니다. 3을 제외한 3의 배수를 제거합니다. 이제 다음 차례로는 4를 제외한 4의 배수를 제거해야겠죠? 하지만 4는 2의 배수이기 때문에, 이미 다 지워졌습니다. 다음.. [알고리즘] 간단한 소수 판별 알고리즘 (Swift) 소수 소수(Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다. 간단한 소수 판별 알고리즘 그렇다면 해당 수가 소수인지 아닌지 어떻게 판별할까요? 아주 간단한 방식으로 소수인지 판별할 수 있습니다. 단순히 2부터 자기 자신의 수 - 1 까지의 수 중에서 나누었을 때, 나머지가 0이 되는 수가 하나라도 존재하면 소수가 아닙니다. 이 방식의 경우 시간 복잡도는 $O(n)$이 될 것입니다. 시간 복잡도를 줄일 수 있는 방법이 있을까요?? 개선된 소수 판별 알고리즘 X를 2로 나누었을 때, 나머지가 0이라면 2는 X의 약수입니다. 그렇다면 X는 절대로 소수가 될 수 없겠죠? X를 2로 나누었을 때, 몫 도 X의 약수 입니다. 이러한 성질을 이용해서 시간 복잡도를 줄일 수.. [알고리즘] 그리디(Greedy) 알고리즘 (Swift) 그리디 알고리즘에 대해 알아보고 대표문제를 Swift로 한 번 풀어보겠습니다. 그리디 알고리즘이란? 그리디 알고리즘을 번역하면 탐욕 알고리즘 이라고 한다. 말 그대로 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 즉, 매 순간마다 최선의 경우를 고르고 다른 경우는 고려하지 않는다. 그리디 알고리즘의 어려운 점은 이 문제가 그리디가 맞는지 판별하는 것이 가장 어려운 것 같다. 계속해서 반례가 있는지 확인해야하고 고민해야 한다. 그리디 알고리즘은 정렬 알고리즘과 주로 짝을 이루기도 한다. 대표 문제 백준 5585 거스름돈 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 .. 이전 1 다음
