L'atelier chez moi

쉬운 문제를 어렵게 풀었다. 배열의 요소들을 보면 모두 첫 숫자의 배수임을 알 수 있다. 쉽게 생각해보면 [2, 4, 6, 8, 10] 이 정수 2 의 [2 * 1, 2 * 2, 2 * 3, 2 * 4, 2 * 5] 인 것을 빠르게 알아채내어 정수 x 의 [X * 1, X * 2, X * 3, X * 4, X * 5] 를 추론하면 된다. 이 말로 시작하는 것은 나는 그렇게 하지 못했다......ㅠ 아래를 보자 어쨌든, 결과는 바람직하게 나오긴 한다. 다만 아쉬운 것은 저렇게 하지 않아도 된다는 것. 몇 가지 확인해볼 것이 있기에 부끄럽지만 올린다. x 가 양수가 될 수도 있고, 음수가 될 수도 있어 abs() 함수를 활용했다. * abs() ? - 절대값을 구할 수 있는 함수이다. 그 다음 볼만한 내용은..

문제의 상황은 간단합니다 정수가 하나 주어지고(n 이라 하겠습니다), n이 어떤 양의 정수(x라 하겠습니다)의 제곱인지 아닌지 판단합니다. 주어진 정수 하나가 양의 정수 x 의 제곱에 해당한다면 이 x +1 의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1 을 리턴하는 함수를 만드는 것입니다. 숫자를 넣어보면 간단합니다. 100 이 주어지고, 100이 어떤 양의 정수의 제곱인지 아닌지 판단합니다. 100 이 어떤 양의 정수의 제곱에 해당한다면 그 양의 정수에 1을 더한 값에 제곱을 리턴하고, 100 이 어떤 양의 정수의 제곱에 해당하지 않는다면 -1 을 리턴합니다. 100은 10의 제곱이라는걸 우리는 알고 있기 때문에, 이를 활용하여 다시 작성해봅니다. 100 이 주어지고 100은 10의 ..

'How to Implement Linked List' - LBTA (https://www.letsbuildthatapp.com/course_video?id=4292) 영상을 참고하였습니다. 그래프 탐색을 공부하기 위해 BFS, DFS 를 공부하다가 Queue 에 대해 알게 되었고 Queue 를 공부하다가 링크드 리스트를 갑자기 공부하게 되었다. ...뭐지? 아무튼 나의 첫 링크드 리스트, 시작해보자. 이번에 다뤄볼 리스트는 단방향 링크드 리스트이다. 위의 사진에서 네모 한 칸(보라색 + 파란색)을 노드(Node)라 한다. 보라색 네모는 값을 가지고 있는 Data(or Value) 이고 파란색 네모는 다음 노드의 주소를 나타내고 있는 Pointer(포인터 or Next) 이다. 사진에서는 나..

이진탐색에 대해 알아보자. 오랜만에 프랑스어 단어 'incroyable' 를 찾기 위해서 종이사전을 꺼냈다. 여러번 종이 사전으로 단어를 찾아본 경험이 있지 않더라도, 알파벳 순서는 정렬되어있기 때문에 자연스레 사전을 절반으로 갈라서 펼치는 내 자신을 보았다. 아!!! 여기서 나는 이진 탐색(Binary search)을 나도 모르게 하고 있었음을 깨달았다. 위의 에피소드에서 중요한 내용이 나왔다. 바로 이진 탐색을 하기 위해선 주어진 무엇인가가 정렬(사전은 A,B,C,D 순서로..)되어 있어야 한다는 것이다. 쉽게 생각해서 사전이 abcd 순서로 되어있지 않다면 반을 펼치는 것이 무슨 의미가 있겠는가? 펼쳤는데 A가 나온다면... (절레절레) 이러한 이진 탐색은 주어진 배열에 원하는 원소가 있으면 그 원..

퀵 정렬(Quick Sort, 평균적으로 O(nlog n) 의 속도)은 정렬 알고리즘의 한 종류다. O(n²) 의 속도를 나타내는 선택 정렬보다 훨씬 빠르고 실제로도 자주 사용된다. 물론 퀵 정렬도 최악의 경우에는 O(n²) 의 속도를 내지만 그래도 평균과 최악 최선이 O(n²) 인 것 보다 좋지 않은가?? 또한 퀵 정렬을 구현하기 위해서는 분할 정복 전략(divide and conquer)을 사용한다. 뭔가 나눠서 하나씩 내 것으로 만든다는 듯한 느낌을 주는 전략이다. 일단 코드를 보면서 이야기해보자. let sampleArray = [4, 7, 9, 2, 3, 5, 6, 1, 8] func quickSort(array: [Int]) -> [Int] { if array.count < 2 { // 배열이..