DataStructure + Algorithm
-
-
-
-
Greedy AlgorithmDataStructure + Algorithm/Basic Theories 2021. 10. 22. 01:11
Greedy Algorithm 은, 그때 그때의 최선을 택하는 방법으로 진행하는 알고리즘이에요. 전과 후를 생각하지 않고 당장 최선의 결과를 낼 수 있는 방향으로 진행됩니다. 어떠한 경우에는 순간순간의 앞을 내다보지 않는 선택을 통해 실제로도 최고의 결과값을 가질 수 있지만, 그렇지 않을 때도 있기 때문에 Greedy Algorithm 을 사용해도 될지 먼저 판단하는게 중요해요. 'Greedy' 라는 단어의 어감이 그리 좋게 느껴지지 않으실 수는 있겠지만, 종종 매우 효율적이고 간단한 답을 낼 수 있는 방법 중 하나에요. Dynamic programming 처럼 optimization problems 를 풀 때 사용되기도 하지만, Dynamic 과 크게 다른 점 하나는 훨씬 간단하다는 거죠. Dynami..
-
Quick Sort with SwiftDataStructure + Algorithm/Basic Theories 2021. 10. 21. 23:59
Quick Sort Quick Sort 는, Pivot 을 정해서 Pivot 에 따라 더 작은 값들, 더 큰 값 들을 나눈 후 나뉜 값들에 대해 다시 Pivot 을 정한 후 더 작은 값들, 더 큰 값을 나누는 행위를 반복하면서 마지막에는 정렬된 array 를 합치며 Sorting 하는 방법이에요. 예시를 통해 과정을 설명드릴게요 1.0. 8 개의 element 가 array 에 있다고 가정해볼게요. [6, 5, 3, 1, 8, 7, 2, 4] 1.1. Pivot 을 하나 정합니다. (가장 뒤에 있는 값으로 설정하겠습니다.) 4가 Pivot value 가 되었습니다 ! 1.2. array 에서 가장 앞에 있는 값 6 과 4를 비교합니다. 6 > 4 이므로, 6이 4의 뒤에 있으면 좋겠네요. 그렇게 하기 위..
-
MergeSort (with Swift)DataStructure + Algorithm/Basic Theories 2021. 10. 20. 01:24
Merge Sort 큰 덩어리를 작게 나누고, 나뉘어진 것들을 sorting 한 후 합치면서 정렬하는 방법을 Merge Sort 라고 합니다. 예를 들어 10개의 elements 가 있는 경우, 해당 array 를 sorting 하려면 위에서 썼던 방법들을 사용했을 때 O(n^2), 약 100 번의 과정이 소요된다고 가정해볼게요. 만약 array 를 반으로 나눈 후 sorting, 합칠때 다시 sorting 해주면 과정이 많이 줄어들 수 있습니다. 위와 같은 방식으로 한다면 5^2 이 두번, 그리고 합치는 경우에는 모든 element 들을 한번씩 비교하고 배치해야하니 10번 으로 잡으면 (25 + 25 + 10 ) 60번 이네요. 그런데말입니다, 이러한 과정을 끝없이 (각 element 가 하나가 될 때..
-
Dynamic Programming (with Fibonacci sequence(using Swift and Cache))DataStructure + Algorithm/Basic Theories 2021. 10. 19. 17:44
안녕하세요, 오늘은 Dynamic Programming 에 대해서 다루고자 합니다. Dynamic Programming 에서는 Divide & Conquer 과 같이 덩어리를 조각조각 내어 해를 구합니다. 하지만 둘 사이 가장 다른 점은 그 조각조각의 연관성이라 할 수 있겠습니다. 나눈 것들이 서로 관련이 전혀 없을 때 Divide & Conquer 을, 관련이 있어서 이전에 구한 값을 활용하면서 해를 구할 때 Dynamic Programming 을 활용한다고 할 수 있겠습니다. 나눈 부분들이 서로 관련이 있는데도 Divide & Conquer 방식으로 해결하고자 하면 Dynamic Programming 방식보다 더 비효율적일 가능성이 매우 높겠죠 ? 이번 글에서는 Fibonacci Sequence 를 ..
-
프로그래머스 - 탐욕법 - 체육복 (with Swift)DataStructure + Algorithm/Algorithm 풀이 with Swift 2021. 10. 18. 13:40
체육복 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution..