Swift
-
백준 1926 그림Algorithm/BOJ 2021. 2. 5. 15:26
출처: https://www.acmicpc.net/problem/1926 분류: BFS 접근방식 BFS 방식으로 풀어봤습니다. bfs를 시작하면서 그림의 개수를 세고, bfs 안에서 queue에서 꺼낼 때마다 카운트 해서 그림의 너비를 계산했습니다. queue는 DoubleStackQueue를 사용했습니다. 해결방법 struct DoubleStackQueue { private var inbox: [Element] = [] private var outbox: [Element] = [] var isEmpty: Bool{ return inbox.isEmpty && outbox.isEmpty } var count: Int{ return inbox.count + outbox.count } var front: El..
-
Queue in SwiftComputer Science/DataStructure 2021. 2. 5. 14:45
- 선형 자료구조 - FIFO (선입선출) - 구현 - LinkedList - DoubleStack Swift에서는 Queue와 LinkedList를 기본 자료구조로 제공하지 않고 있는데요, array를 사용해 queue를 만들면 enqueue 작업이 O(n)이 걸려서 비효율적입니다. 특히 코딩테스트 문제를 풀다보면 queue가 필요한 상황이 많기 때문에 미리 알아두고 구현해둔다면 좋겠죠? 오늘은 간단하게 Queue 에 대해 알아보고 swift에서는 어떻게 구현할 수 있을지 알아보겠습니다. LinkedList를 사용한 구현과, stack 두 개를 사용한 doubleStack 구현을 알아볼텐데요, LinkedList는 제가 구현해서 그런지 doubleStack과 복잡도 차이가 꽤 나더라구요... 😢 코딩테..
-
백준 1759 암호만들기Algorithm/BOJ 2021. 2. 2. 12:08
출처: https://www.acmicpc.net/problem/1759 분류: 백트래킹 접근방식 백트래킹 방식으로 풀어봤습니다. 완성한 암호가 모음 1개 자음 2개 이상인지 확인해야 하는 것만 주의하면 어렵지 않게 풀 수 있을 것 같네요! 체크하는 건 모음 set을 만들어두고 완성된 문자열과 교집합을 구해서 카운트하는 방식으로 풀어봤습니다 :) 해결방법 let lc = readLine()!.split(separator: " ").map { Int($0)! } var alphabets = readLine()!.split(separator: " ").sorted() var available = [Bool](repeating: true, count: lc[1]) var predicted: String = "..
-
백준 15649 N과 M(1)Algorithm/BOJ 2021. 1. 28. 11:29
출처: https://www.acmicpc.net/problem/15649 분류: 백트래킹 접근방식 1~N까지의 수 중에서 중복없이 해당 길이의 모든 경우의 수를 다 찾는 문제였습니다. 가능한 모든 경우의 수를 다 고려하는 백트래킹으로 해결했습니다. 처음엔 원하는 길이만큼 만들어 나가는 dfs를 1~N을 시작점으로 해서 여러 번 돌리는 방식으로 풀었는데요 백트래킹을 공부하고 정통적인 방법으로 다시 풀어봤습니다. 해결방법 1 ~ N을 시작으로 해서 주어진 길이만큼의 배열을 만들어나가는 dfs 방식입니다. protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } exten..
-
백준 2252 줄 세우기Algorithm/BOJ 2021. 1. 27. 22:16
출처: https://www.acmicpc.net/problem/2252 분류: 위상정렬 접근방식 위상정렬로 해결할 수 있는 문제였습니다 :) 특정 순서를 지켜야 하고 방향성 있는 그래프 일 때는 위상정렬!! 을 다시 한번 기억해야겠습니다. 해결방법 큐를 구현하긴 귀찮고 removeFirst도 사용하기 싫어서 큐 인덱스를 가리키는 변수를 하나 만들어서 FIFO를 구현해봤습니다 :) protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()!..
-
백준 13904 과제Algorithm/BOJ 2021. 1. 27. 13:56
출처: https://www.acmicpc.net/problem/13904 분류: 그리디 접근방식 그리디하게 점수가 높은 과제부터 배정해주는 방식으로 해결했습니다. 점수가 높은 과제를 마감일에 처리해주되 해당 날이 이미 배정되어 있다면 비어 있는 날을 찾아 그 전날에 배정해주는 방식으로 해결했습니다. 만약 1 30 2 40 2 50 주어졌다면, 점수가 가장 높은 2 50을 먼저 배정해주고 그 다음 높은 2 40을 배정해주려 하는데, 2일차는 이미 차서 그 전날인 1일차에 배정해주는 방식입니다. 이미 점수가 높은 순서대로 배정시키기 때문에 다 차있어서 배정할 수 없다면 그게 최선일거라고 판단했습니다. 해결방법 protocol Readable { func readSingleValue() -> String f..
-
백준 1300 K번째 수Algorithm/BOJ 2021. 1. 26. 14:53
출처: https://www.acmicpc.net/problem/1300 분류: 이분탐색 접근방식 풀이 자체는 그냥 이진탐색을 이용하면 돼서 그렇게 어렵지 않지만, 이진탐색으로 접근하기가 어려웠던 문제였습니다. 가장 첫 번쨰 접근은 오름차순으로 정렬했을 때 k번째 수라는 건, B[k] 의 원소보다 작거나 같은 수가 k-1개만큼은 있다는 의미가 됩니다. 그럼 B[k]의 원소가 될 어떤 수를 정하고 이 어떤 수보다 작은 수가 k-1개가 있는지 확인하면 됩니다. 문제는 어떤 수보다 작은 수가 몇 개인지 확인하는 방법입니다. 이 방법만 찾으면 이진탐색으로 어떤 수보다 작은 수의 개수가 k보다 작은지 비교해가며 찾아줄 수 있습니다. 어떤 수를 m이라고 했을 때 이 m보다 작은 수가 몇 개가 있는지는 어떻게 확인할..
-
백준 1339 단어 수학Algorithm/BOJ 2021. 1. 22. 14:43
출처: https://www.acmicpc.net/problem/1339 분류: 그리디 접근방식 기본적으로 글자를 체크하고 수를 만드는 방식은 글자를 키로하고 글자의 자리 수 배열(해당 문제에서 최대 8자리)을 만들어서 이 글자가 해당 자리수에 몇 번이 사용되었는지 체크했습니다. 그리고 이걸 가지고 수를 만드는 방식으로 접근했습니다. 이제 문제는 어떤 글자에 어떤 숫자를 할당할지 결정해야 합니다. 아마도 가장 일반적인 생각이자 실수하기 딱 좋은 가정은 가장 큰 자리 수의 숫자가 많은 글자에 가장 큰 수를 매칭시키는 것으로 생각할 수 있습니다. 아래 예를 생각해볼까요? AA BC " 가장 큰 자리에 A 와 B가 1개씩 있어서 동률이고, 그 다음에 A가 한 번 더 있으니 A에 가장 큰 수인 9를 할당하면 되..