전체 글
-
백준 2961 도영이가 만든 맛있는 음식Algorithm/BOJ 2021. 2. 19. 14:04
출처: https://www.acmicpc.net/problem/2961 분류: 재귀 접근방식 N이 1 ~ 10 으로 아주 작아서 백트래킹으로 모든 조합을 다 계산해서 풀 수 있었습니다. 처음에는 뭐에 홀렸는지 단순히 이중 포문으로 모든 경우를 다 체크할 수 있지 않나? 라고 생각했었네요... 단순히 이렇게 하면 중간을 건너뛴 1, 3 같은 조합은 체크할 수가 없겠죠 ㅠㅠ s는 곱이고 b는 합이기 때문에 초기값으로 1, 0을 넣고 시작해줬습니다. 처음을 안 넣었을 경우는 계산하면 안 되기 때문에 각 케이스에서 재료를 넣어서 새롭게 만든 조합의 차만 생각을 해줬습니다. 해결방법 let n = Int(readLine()!)! var flavors = [[Int]]() for _ in 0.. abs(newS-..
-
백준 1074 ZAlgorithm/BOJ 2021. 2. 18. 12:28
출처: https://www.acmicpc.net/problem/1074 분류: 재귀 접근방식 백준 1992 쿼드트리 와 비슷한 문제였습니다. 대신 쿼드트리처럼 전부 방문하면 시간 제한에 걸리게 되기 때문에 어느 사분면에 포함되는지 체크해서 해당 분면만 재귀적으로 호출해줘야 합니다. 방문의 순서는 알고 있기 때문에 해당 사분면에 가능한 방문의 범위도 알 수가 있습니다. 4x4 배열이라면 각각 0~3, 4~7, 8~11, 12~15 사이의 값이 오겠죠? 이를 이용해서 방문 가능한 카운트 범위도 같이 넘겨주면서 해결했습니다. 해결방법 import Foundation extension Int { func pow(_ n: Int) -> Int { var powered = 1 (0..
-
백준 1992 쿼드트리Algorithm/BOJ 2021. 2. 18. 11:20
출처: https://www.acmicpc.net/problem/1992 분류: 재귀 접근방식 사각형의 영역을 1, 2, 3, 4분면씩 쪼개서 재귀로 풀 수 있는 문제였습니다. 고민하다가 잘 모르겠어서 다른 분들 풀이를 참고해서 풀었네요 ㅠ-ㅠ 처음엔 포문을 먼저 돌려서 모두 1인지 0인지 체크하는 방식으로 풀었는데, 다른 분들의 풀이를 보니 어차피 재귀로 돌릴거라면 먼저 체크하지 않아도 결과를 가지고 확인해서 풀 수도 있네요! 해결방법 처음 풀이 포문으로 전부 0인지 1인지 체크, 아니라면 compression func compress(size: Int, at point: Point) -> String { guard size != 1 else { return String(map[point.r][poin..
-
백준 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 = "..
-
CALayer 그리고 View와의 관계iOS 2021. 1. 31. 17:58
개인적으로 공부하며 정리하는 블로그 입니다. 오류나 부족한 부분이 있을 수 있으니 감안하여 봐주시고 아낌없는 조언 감사드립니다 :D CA, Core Animation CALayer의 CA는 Core Animation의 prefix입니다. CALayer를 알기 전에 먼저 Core Animation에 대해 알아보겠습니다. Core Animation Programming Guide를 보면 Core Animation의 역할과 목적에 대해 나와있습니다. Core Animation provides a general purpose system for animating views and other visual elements of your app. Core Animation is not a replacement for..
-
백준 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..