iOS 를 매우매우 좋아하는 개발자의 노트 iOS 를 매우매우 좋아하는 개발자의 노트

Greedy Algorithm 은, 그때 그때의 최선을 택하는 방법으로 진행하는 알고리즘이에요. 전과 후를 생각하지 않고 당장 최선의 결과를 낼 수 있는 방향으로 진행됩니다. 어떠한 경우에는 순간순간의 앞을 내다보지 않는 선택을 통해 실제로도 최고의 결과값을 가질 수 있지만, 그렇지 않을 때도 있기 때문에 Greedy Algorithm 을 사용해도 될지 먼저 판단하는게 중요해요. 'Greedy' 라는 단어의 어감이 그리 좋게 느껴지지 않으실 수는 있겠지만, 종종 매우 효율적이고 간단한 답을 낼 수 있는 방법 중 하나에요. Dynamic programming 처럼 optimization problems 를 풀 때 사용되기도 하지만, Dynamic 과 크게 다른 점 하나는 훨씬 간단하다는 거죠. Dynami..

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의 뒤에 있으면 좋겠네요. 그렇게 하기 위..

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 에 대해서 다루고자 합니다. Dynamic Programming 에서는 Divide & Conquer 과 같이 덩어리를 조각조각 내어 해를 구합니다. 하지만 둘 사이 가장 다른 점은 그 조각조각의 연관성이라 할 수 있겠습니다. 나눈 것들이 서로 관련이 전혀 없을 때 Divide & Conquer 을, 관련이 있어서 이전에 구한 값을 활용하면서 해를 구할 때 Dynamic Programming 을 활용한다고 할 수 있겠습니다. 나눈 부분들이 서로 관련이 있는데도 Divide & Conquer 방식으로 해결하고자 하면 Dynamic Programming 방식보다 더 비효율적일 가능성이 매우 높겠죠 ? 이번 글에서는 Fibonacci Sequence 를 ..

Linked List Linked Lists 는 Singly Linked List, Doubly Linked List 두개로 나뉘어요. Linked List 는 우선, List 가 Linked 되어있는... 형태의 Data Structure 입니다. 다시 말하면, 여러개의 요소들 (List) 이 서로 연결되어있는 (Linked) 모양의 띠어요. Singly Linked List Singly Linked List 부터 설명드리면, 가장 앞에 있는 element 는 head 라고 부르고, 이 head 는 값과 다음 값을 가리키는 pointer 를 갖습니다. 만약 다음 값이 없다면 pointer 는 null (Swift 내에서는 nil ) 값을 가지겠지요. 반대로 가장 뒤에 있는 element 는 tail 이..

Stack 과 Queue 는, 아주아주 흔하게 볼 수 있는 DataStructure 입니다. 둘 사이 가장 다른 점은 데이터가 추가, 추출되는 순서겠지요. Stack 의 경우, 가장 늦게 오는 데이터가 가장 일찍 나가고, (Last In, First Out, LIFO) Stack 에서 사용하는 methods 로는 push(_:), pop() 이 있습니다. Queue 의 경우, 가장 일찍 들어오는 데이터가 가장 일찍 나가는 구조입니다. (First In, First Out, FIFO) Queue 에서 사용하는 methods 로는 enqueue(_:), dequeue() 가 있습니다. Stack Stack 은 말그래도 쌓아두는 구조입니다. 팬케이크를 생각하시면 편할 것 같아요. Stack 에서 쓰이는 met..

Insertion Sort 는, 단순한 Sorting Algorithms 중 경우에 따라 비교적 빠를 수 있는 Algorithm 입니다. 특히 대부분이 이미 정렬되어있는 경우 O(n) 까지 빨라질 수 있는데요, 그 원리를 하나하나 알아보겠습니다. Example 1 첫 예시는 다른 Sorting 의 예시들처럼 아래 행렬을 가지고 차례차례 순서를 밟아보겠습니다. [4,3,5,2,1] 1. 첫번째 element 인 4 를 먼저 하나의 상자에 넣습니다. [4] [4, 3, 5, 2, 1] 2. 두번째 element 인 3 과 상자에 있는 수(4) 를 비교합니다. 3이 더 작으므로, 상자 안에 3을 넣을 때 상자의 앞쪽에 넣습니다. [3, 4] [3, 4, 5, 2, 1] 3. 상자 [3, 4] 와 그 다음에 오..

Description Selection Sort 는, 배열 차례대로 하나하나 비교해가며 가장 작은 값을 찾은 후, 가장 낮은 인덱스에 있는 수와 바꾸는 방식을 반복하여 정렬을 진행합니다. 아래는 정렬할 array 의 예시입니다. (Bubble Sort 의 경우와 같은 array 를 대상으로 정렬을 진행하겠습니다. [4, 3, 5, 2, 1] 1. 먼저 4 ( 0번째 index ) 을 기준으로 한 후 3와 비교합니다. 기준이 아닌 수가 기준보다 작으므로 3 를 기준으로 삼습니다. 2. 이제, 새로운 기준 3 과 5 를 비교합니다. 기준이 더 작으므로 다음 수로 넘어갑니다. 3. 3과 2 를 비교합니다. 2 가 기준보다 작으므로, 2 를 새로운 기준으로 삼습니다. 4. 2 와 1 을 비교합니다. 1 이 기준..