자료구조

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 배열에서 자기 자신보다 오른쪽에 있는 가장 가까운 큰 수를 찾는 문제이다. 처음 구현한 방법은 이중 for문을 활용하였으나, 배열의 크기가 클 땐 O(n^2) 의 시간복잡도를 감당할 수 없어 시간초과가 나왔다. 실패 코드 import Foundation let n = Int(readLine()!)! var numbers = readLine()!.split { $0 == " " }.map { Int(String($0))! } var result : [Int] = [] for ..

1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 추가하는 건 맨 뒤에서, 빼는 건 양쪽 방향에서 해줄 수 있는 큐가 필요하다. 덱(double ended queue)을 구현해주면 되는데, 해당 문제에서는 양방향으로 추가해줄 필요가 없어서 기존에 구현했던 큐를 일부 수정, 변형하였다. 회전하는 큐 구현 struct Queue { var left = [Int]() var right = [Int]() var count: Int { left.count + right.count } var isEmpty: Bool ..

Swift같은 개발 언어 중에는 힙, 큐, 덱같이 기본적으로 다른 언어에서 제공해주는 라이브러리가 따로 있지 않다. 따라서 직접 구현해줘야 한다. 알아야 될 것 1. 완전 이진트리로 부모 노드를 탐색하려면, 시작 인덱스를 1부터 시작해야 한다. 2. 힙은 우선순위 큐를 위한 자료형이다. 3. 우선순위 큐의 목적은 값을 추가할 때 부모 노드에 최댓값 or 최솟값을 넣기 위함이다. 4. 따라서 입, 출력을 할 때만 연산이 수행되고, 전체 힙의 값을 확인하면 오름차순이나 내림차순으로 정렬되지 않을 수 있다. struct Heap { var heap: Array = [] // 초기화 1. 아무 것도 넣지 않을 때 init() { } // 초기화 2. 시작부터 넣을 때 init(_ data: [Int]) { he..