algorithm
-
Programmers Lv2) [2021 카카오블라인드] 신규 아이디 추천Algorithm/Programmers 2021. 2. 22. 13:38
출처: programmers.co.kr/learn/courses/30/lessons/72410 분류: 문자열 접근방식 친절하게 단계별로 요구사항을 제시해주고 있기 때문에 주어진 대로 열심히 구현하면 되는 문제였습니다! 문자열을 다루는 문제이니 만큼 굉장히 다양한 풀이들이 있더라구요. 문자열을 연습하기 아주 좋은 문제였던 것 같아요. 각 단계별로 가능한 다양한 풀이를 생각해보면서 정리해보고자 합니다. 우선 다른 분들의 풀이를 보면 그냥 solution 함수에 다 때려박아(?)서 구현하신 분도 있고 함수를 나누신 분도 계시고 extension 으로 처리해서 더 깔끔하게 푸신 분들도 계시던 것 같아요. 편한대로 풀면 되겠지만 실전이라면 여기서 너무 시간을 오래 끌지 않도록 익숙하고 빠르게 풀 수 있는 방법으로..
-
백준 1149 RGB 거리Algorithm/BOJ 2021. 2. 19. 15:32
출처: https://www.acmicpc.net/problem/1149 분류: DP 접근방식 dp 문제임은 알았지만 결국 풀지 못하고 다른 분들의 풀이를 참고했습니다 ㅠㅠ 처음에는 r, g, b에서 시작한 dp 3개를 다 채우면 되지않을까 생각을 했는데 이렇게 하면 두 색의 비용이 같거나 하는 등의 여러 예외들을 처리해줄 수가 없게됩니다 ㅠㅠ 기존에서 사고를 좀 더 열어 생각해보면 각 집이 모두 r, g, b로 칠해질 수 있는 경우를 생각해보면 쉽게 접근할 수 있습니다 :) 일반적인 1차원 배열이 아니라 [집의 개수][3] 크기의 2차원 배열을 채워나가는 방식으로 접근하면 쉽게 해결할 수 있었습니다. 해결방법 let numberOfHouse = Int(readLine()!)! var colorSet =..
-
백준 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 = "..