도지와 나

[백준] 9012.괄호 (Swift) https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 스택을 이용해 해결할 수 있는 간단한 문제입니다. 괄호는 무조건 한 쌍으로 이루어져야 하며 괄호가 열리면 무조건 괄호는 닫혀야 합니다. 스택을 이용해 괄호의 유효성을 판단하는것은 굉장히 간단합니다. ( 가 나오면 스택에 push 하고 ) 가 나오면 pop 하는 것이 전부입니다. 하지만 pop 할 시 스택이 비어있다면 해당 괄..

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

[백준] 5639.이진 검색 트리 (Swift) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 전위순회 입력대로 트리를 구성하여 후위순회로 출력하는 방법은 시간초과가 발생합니다. 따라서 전위순회 결과에서 규칙을 찾는 과정이 필요한 문제입니다. 전위순회는 루트 노드로부터 시작해 왼쪽 자식, 오른쪽 자식 순으로 진행되기 때문에 전위순회의 가장 첫번째 값은 루트 노드가 됩니다. 이진 탐색 트리의 특성 상 왼쪽 자식은 루트노드보다 ..

[백준] 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 의 삽입은 트리의 가장 바깥쪽 노드에서 시작됩니다. 먼저 삽입할 노드를 트리의 가장 바..

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