도지와 나

[백준] 2461.대표 선수 (Swift) https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net 풀이 각 배열마다 수를 하나씩 뽑아 그 중 최대값과 최소값의 차이가 제일 작은 경우를 구하는 문제입니다. 처음에는 Heap 을 이용해 최소값을 모두 뽑은 다음, 최대값과 최소값의 차이를 계산한 뒤 그 중 최소값들을 삭제하고 다시 값을 뽑는 식으로.. 진행할 계획이었습니다. 입출력 예시는 모두 맞았지만, O(n^2) 정도로 코드를 작성하다보..

[백준] 1655.가운데를 말해요 (Swift) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 시간복잡도를 고려해야하기 때문에 힙을 사용하는 문제입니다. 풀이를 위해선 최대힙과 최소힙을 모두 사용하는데, Swift 는 힙 자료구조를 제공하지 않아 직접 구현해야 합니다. 힙에 관한 설명과 Swift 를 이용해 작성된 코드는 아래 링크에서 확인하실 수 있습니다. https://trumanfromkorea.tistory.com..

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