Algorithm/Theory
-
Permutation 순열Algorithm/Theory 2020. 6. 11. 12:48
안녕하세요. 문제를 풀다가 순열 관련 부분에서 머리가 터져버려(?) 순열에 대해 공부해보고자 합니다. 순열은 순서가 있는 열, 순서를 가지고 줄세우는 경우의 수 라고 생각하시면 됩니다. 1번과 2번의 사람이 있다면 이 둘을 줄세우는 경우의 수는 1, 2 2, 1 이렇게 2가지 경우가 있겠죠. 1, 2, 3 세 명의 사람이라면 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 이렇게 총 6가지 경우가 있습니다. 맨 앞 자리에 올 수 있는 사람의 수는 3 맨 앞자리가 정해졌다면 그 다음에 올 수 있는 사람의 수는 2 그 다음은 1 즉 순열의 경우의 수는 n! 이 됩니다. 여기까지는 많이들 알고계셨던 내용이겠죠? 이제 이를 코드로 구현하려면 어떻게 해야하는지 살펴보겠습니다...
-
Recursion 재귀Algorithm/Theory 2020. 6. 11. 12:21
많은 일들은 대개 작은 조각들로 나누어 볼 수 있습니다. 그리고 한 조각이 작으면 작을수록 일은 단순해지고 반복되는 형태를 띄는 경우가 많습니다. 완전히 같은 코드를 반복적으로 하는 작업이 있다면 이때 재귀 함수(recursion fnction), recursion(재귀 호출)이 유용하게 사용될 수 있습니다. 1~100까지의 합을 구하는 경우를 재귀적으로 생각해봅시다. 1~100까지의 합은 100 + 1~99까지의 합으로 나눠서 생각할 수 있습니다. 마찬가지로 1~99까지의 합은 99 + 1~98까지의 합으로 볼 수 있겠죠. "n + 1~n-1까지의 합" 이라는 과정은 완벽하게 동일합니다. 이를 코드로 구현해보면, func sum(_ n: Int) -> Int { if n == 1 { return 1 }..
-
위상정렬 Topological SortAlgorithm/Theory 2020. 6. 7. 13:21
목표 - 위상정렬 (Topological Sort)를 이해하고 설명할 수 있다. - 위상정렬의 조건을 알고 언제 어떻게 사용하는지 이해한다. 위상정렬? \ 특정한 순서를 가진 조건에서 사용한다. DAG(방향성 비순환 그래프) 에서만 사용할 수 있다. \ "위상" 이라는 사전적 정의에서 알 수 있듯이, 위상정렬이란 어떤 순서를 가지고 있는 경우에 사용할 수 있는 정렬 방법입니다. 게임을 하는데 어떤 스킬을 익히기 위해 반드시 먼저 배워야 하는 사전스킬이 있죠? 이런 식으로 어떤 순서를 가지고 있을 때 사용합니다. 이 말인즉 위상정렬은 방향성을 가지고 있어야 합니다. 그리고 이 의미를 잘 생각해보면 사이클이 생기면 안된다는 것을 알 수 있습니다. A -> B -> C 순서를 가지고 있어야 하는데 여기서 C ..
-
합병정렬 Merge sortAlgorithm/Theory 2020. 5. 14. 20:04
목표 합병 정렬을 이해한다. 합병 정렬을 Swift로 구현한다. 합병 정렬의 시간 복잡도를 이해한다. ( O(nlogN) ) 총 재귀 호출 횟수는 2n-1 합병 정렬 ? 합병 정렬은 분할정복 알고리즘의 하나입니다. 합병 정렬의 아이디어는 이미 정렬된 두 배열이 있다면 각 배열의 첫번째 원소끼리 비교해 정렬된 새로운 배열을 만들 수 있다. 에서 시작합니다. 이 정렬된 두 배열을 얻기 위해 일단 최대한 작게 쪼개고 다 쪼갰다면, 위의 아이디어를 이용해 정렬된 새로운 배열을 만들어 나가는 것이죠. 구체적으로 아래와 같은 과정을 거치게 됩니다. 1. 길이가 1 이하인 리스트는 정렬된 것으로 본다. 2. 분할(divide): 길이가 2이상이면 리스트는 반으로 쪼갠다. 3. 정복(conquer): 분할된 각 부분의..
-
프림 알고리즘Algorithm/Theory 2020. 3. 6. 17:13
- MST(Minimum Spanning Tree)를 만드는 방법 중 하나입니다. - 현재 트리를 기준으로 가장 최소인 점을 찾아나가는 방식입니다. - 사이클을 확인할 필요가 없습니다. (현재트리를 기준으로 하기 때문에 사이클이 생기지 않습니다.) 프림 알고리즘은 현재까지 생성된 트리를 기준으로 가장 최소 비용의 간선을 선택해서 트리를 확장시켜 나갑니다. 현재 트리를 기준으로 한다는 말 속에는 이미 방문한 점은 방문하지 않는다는 말이 포함되어 있습니다. 때문에 자연스럽게 사이클이 생기지 않습니다 :) 과정은 간단합니다. 1. 현재 트리를 기준으로 최소 비용으로 방문 가능한 점을 방문합니다. 2. 새로운 점을 기준으로 최소 간선의 목록을 업데이트 합니다. 직접 문제를 하나 풀어보면 쉽게 이해하실 수 있으실..