꽁치대디의 개발일기

[자료구조] Swift 로 Heap 구현하기 Heap 은 이진트리 형태의 자료구조로 최대값 및 최소값을 빠르게 탐색할수 있도록 설계되었습니다. Heap 에는 2가지 종류가 있는데, 부모노드의 키값이 자식노드의 키값보다 항상 큰 경우는 Max Heap, 부모노드의 키값이 자식노드의 키값보다 항상 작은 경우는 Min Heap 이라고 합니다. 그렇기 때문에 Max Heap 의 루트노드에는 항상 최대값이 저장되고 Min Heap 의 루트노드에는 항상 최소값이 저장됩니다. Heap 은 이진트리 형태로 구현되었기 때문에 삽입과 삭제에서 O(logN) 의 시간복잡도를 가집니다. 삽입 MaxHeap 을 예로 들어보겠습니다. Heap 의 삽입은 트리의 가장 바깥쪽 노드에서 시작됩니다. 먼저 삽입할 노드를 트리의 가장 바..

[알고리즘] 동적 계획법 (Dynamic Programming) 다이나믹 프로그래밍은 하나의 큰 문제를 여러개의 작은 문제들로 나눠서 해결하는 방식입니다. 그렇기 때문에 다이나믹 프로그래밍을 이용하여 문제를 해결하려면 2 가지 조건을 만족해야 합니다. - 부분 반복 문제 (Overlapping Subproblem) 다이나믹 프로그래밍은 전체 문제를 여러개의 작은 문제들로 나눈 다음 그 결과값들을 이용해 전체의 답을 도출해냅니다. 그렇기 때문에 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능합니다. - 최적 부분 구조 (Optimal Substructure) 최적 부분 구조는 전체 문제의 최적해가 부분 문제들의 최적해로 이루어진 경우를 말합니다. 그렇기 때문에 특정 문제의 정답은 문제의 크기에 상..

[알고리즘] 탐욕법 (Greedy) 탐욕법이란 현재 상황에서의 최적해를 쫓는 알고리즘입니다. 하지만 현재 상황에서의 최적해만을 추구하는 것이 전체적으로 어떤 영향을 끼칠지는 고려하지 않기 때문에 항상 옳은 결과를 장담하지는 않습니다. Local minimum & Global minimum 그래프 위 시작점 X 에서 최소값을 찾는 프로그램을 작성한다고 할 때, 탐욕법을 이용한다고 가정해보겠습니다. 탐욕법은 앞서 말했듯이 현재 상황에서의 최적해를 찾는 알고리즘이기 때문에 시작점 X 에서 최소값을 찾으려면 무조건 지금의 값보다 낮은 왼쪽으로 향하게 될 것입니다. 왼쪽으로 진행하던 점 X 는 어느 순간 값이 커지는 변곡점을 맞게 될 것이고, 프로그램은 해당 변곡점을 그래프의 최소값이라고 생각할 것입니다. 하지만..

[자료구조] Swift 로 Queue 구현하기 코딩테스트 문제를 풀다보면 Queue 자료구조를 이용해야하는 경우가 종종 있습니다. 모든 경우에서는 잘 모르겠지만... Queue 자료구조를 import 해서 사용할 수 있는 Java 와 Python 등과는 달리 Swift 에서는 Queue 자료구조를 제공하고 있지 않습니다. 저는 그래서 코딩테스트 문제를 풀며 필요한 자료구조들을 struct 로 구현해둔 다음 필요할때마다 가져다 사용하는 편입니다. 오늘은 그 중 Queue 를 구현하는 2가지 방법에 대해 알아보겠습니다. Array 를 Queue 처럼 사용하기 Array 의 내장 메소드 중에 removeFirst() 와 removeLast() 등이 존재하기 때문에 이를 잘 활용한다면 사실 Queue 와 비슷한..