알고리즘
-
백준 18808 스티커 붙이기Algorithm/BOJ 2021. 3. 7. 18:48
출처: www.acmicpc.net/problem/18808 분류: 시뮬레이션 접근방식 주어진 요구사항대로 잘 구현하면 되는 문제였습니다! 각 부분을 함수로 잘 쪼개면 어렵지 않게 해결할 수 있을 것 같네요 :) 저는 isPaste, paste, rotate 등을 함수로 분리해서 해결했습니다. rotate 하는 부분이 좀 헷갈렸는데, 기억해두면 나중에도 유용하게 사용할 수 있을 것 같아요! 90도 회전 func rotate(_ sticker: [[Int]]) -> [[Int]] { let rowSize = sticker.count let colSize = sticker[0].count var rotated = [[Int]](repeating: [Int](repeating: 0, count: rowSize..
-
백준 2143 두 배열의 합Algorithm/BOJ 2021. 3. 5. 13:44
출처: www.acmicpc.net/problem/2143 분류: 이분 탐색, 투 포인터 접근방식 합이 0인 네 정수 문제와 비슷했던 문제였습니다. 주어진 각 배열에서 나올 수 있는 부분합을 모두 구해준 뒤 정렬해서 투 포인터로 해결했습니다. 마찬가지로 T인 케이스를 찾았을 때 중복인 수의 개수를 세서 쌍을 찾아줘야 합니다 :) 해결방법 let t = Int(readLine()!)! let n = Int(readLine()!)! let a = readLine()!.split(separator: " ").map { Int(String($0))! } let m = Int(readLine()!)! let b = readLine()!.split(separator: " ").map { Int(String($0))..
-
백준 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..
-
백준 1806 부분합Algorithm/BOJ 2021. 1. 22. 11:43
출처: https://www.acmicpc.net/problem/1806 분류: 투포인터 접근방식 앞선 투포인터 문제와 거의 비슷했습니다. 이 문제도 전형적인 투포인터 방식으로 풀었습니다 :) 해결방법 protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func readSingleValue() -> String { return readLine()! } func readSingleValue() -> Int { return Int(readLine()!)! } func readArray(with separator: Character..
-
백준 11725 트리의 부모 찾기Algorithm/BOJ 2021. 1. 14. 16:44
출처: https://www.acmicpc.net/problem/11725 분류: 트리, 그래프 탐색 접근방식 우선 주어진 대로 트리를 모두 연결하고 루트 노드부터 부모를 연결해나가면 되는 문제입니다! 연결된 노드를 우선 connects에 담아두고 부모가 결정되면 connects에서는 지워주는 방식으로 구현했어요! 처음엔 연결 할 때마다 체크하려고 했는데 다 연결하고 수정해나가는 건 쉬운데, 이건 만만치 않더라구요.. 해결방법 import Foundation protocol Readable { func readSingleValue() -> String func readArray(with separator: Character) -> [String] } extension Readable { func read..
-
선택문제 Quick SelectAlgorithm/Theory 2021. 1. 7. 15:44
- 선택문제: n개의 값 중에서 k번째로 크거나 작은 수를 찾는 문제 - Quick Select: pivot과 작은 값, 같은 값, 큰 값으로 나누어서 찾고자 하는 수가 어디에 속해있는지 찾아나가는 방법 1. pivot 고르기 2. 3부분으로 나누기 ( n-1번 수행 ) S = { P보다 작은 값 } L = { P보다 큰 값 } M = { P와 같은 값 } 3. k가 어디에 속해 있는지 찾기 |S| : 배열 S의 개수, (S에 속함) if |S| >= k { return 재귀(S, k) } (L에 속함) else if |S| + |M| < k { return 재귀(L, k - |S| - |M| } (M에 속함) else { return P } - 시간복잡도 최선의 경우 O(n), 최악의 경우 O(n^2)..