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

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 를 ..

체육복 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution..

문제 설명 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다. Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다. 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 ..

테스트

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 이..

Swift 에서 for statement 내에 종종 .enumerated() 가 쓰일 때가 있어요. ( enumerate: 열거하다, 세다 ) 먼저, 예시부터 드릴게요 ! let names = ["james", "kelvin", "katherine"] for (idx, name) in names.enumerated() { print("idx: \(idx), name: \(name)") } //idx: 0, name: james //idx: 1, name: kelvin //idx: 2, name: katherine 주로 위 예시와 같이 index 와 함께 사용합니다. Syntax 는 위와 같이 (index, element) 로 써주시면 편해요! 이제, option + click 설명과 함께 알아보아요. S..

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..