Algorithm
-
백준 3190 뱀Algorithm/BOJ 2021. 1. 9. 13:10
출처: https://www.acmicpc.net/problem/3190 분류: 자료구조 접근방식 특별한 알고리즘이나 수학적 개념보다 주어진 상황에 충실히 구현하면 되는 문제였습니다. 2차원 배열 맵을 만들어두고 체크해도 되겠으나(많이들 그런 식으로 푸신 것 같더라구요) 저는 굳이 배열을 따로 만들진 않고 범위만 체크했습니다. 해결방법 뱀을 링크드리스트 형태로 구현해줬고 body set을 정의해서 자기 자신으로 가려고 하는지 확인했습니다. enum, class 등등으로 정의해서 좀 느리고 길게 풀어진 것 같긴 하지만 그래도 나름 swift스럽게(?) 푼 것 같기는 합니다. 사과를 찾았으면 해당 사과를 지워줘야 하는데 이걸 빼먹어서 시간을 좀 잡아먹었네요 ;; 혹시나 저처럼 실수하시는 분들이 없기를 ㅠㅠ ..
-
선택문제 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)..
-
Programmers Lv4) [2020 카카오블라인드] 가사검색Algorithm/Programmers 2020. 8. 30. 11:57
출처: programmers.co.kr/learn/courses/30/lessons/60060 분류: Kakao Blind 2020, Lv4, Trie 접근방식 효율성 문제였습니다. 대부분 정확성까지는 어렵지 않게 푸셨을 것 같은데요, 효율성에서 상당히 애를 먹었습니다 ㅠㅠ 문자열을 얼마나 효율적으로 관리하고 탐색할 수 있을지가 키포인트였던 것 같습니다 :) 카카오 단골이죠 문자열 ... 😇 문제설명 가사검색은 주어진 words가 있을 때 query에 만족하는 단어가 몇 개인지 찾는 문제였습니다. 쿼리는 ?를 포함하고 있는데요, ?는 한 글자를 의미하며 어떤 글자가 와도 괜찮습니다. 예를 들어 다음과 같다면, words = ["frodo", "front", "frost", "frozen", "frame"..
-
Programmers Lv2) [3차] n진수 게임Algorithm/Programmers 2020. 8. 28. 17:34
출처: programmers.co.kr/learn/courses/30/lessons/17687 분류: 카카오 블라인드 2018 3차, Lv2 접근방식 주어진 진법의 수를 한 글자씩 끊어서 말하는 게임입니다. 모든 멤버 * turn 이 총 말해야 할 문자열의 길이가 됩니다. 0부터 시작해서 총 문자열의 길이가 멤버 * turn 가 될 때가지 문자열을 만들어 주고 여기서 튜브가 차례의 문자들 (p-1 + m * turn) 을 찾아주는 방식으로 해결했습니다. (p가 1부터 시작하기 때문에 -1을 해줬습니다.) 해결방법 func solution(_ n:Int, _ t:Int, _ m:Int, _ p:Int) -> String { let string = radixString(radix: n, turn: t, me..
-
Programmers Lv2) 파일명 정렬Algorithm/Programmers 2020. 8. 28. 15:42
출처: programmers.co.kr/learn/courses/30/lessons/17686 분류: Lv2, 카카오 블라인드 2018 3차 접근방식 주어진 조건으로 파일을 정렬하는 문제입니다. 문제에서 head, number, tail 3부분으로 나눠서 정렬하라고 하고 있는데요, 하라는 대로 분류해서 head, number, tail 을 프로퍼티로 갖는 File 이라는 struct를 만들고 정렬했습니다. 저는 File을 만들 때 Init 에서 바로 분류 해줬는데요, 분류할 때는 정규표현식을 쓸 수도 있을 것 같은데 중간에 숫자있는 부분만 number로 만들어주면 되어서 current 변수를 하나 두고 처음부터 읽어가면서 분류해줬습니다. mutating func parseFile(_ file: Strin..
-
Programmers Lv2) 압축Algorithm/Programmers 2020. 8. 28. 14:50
출처: programmers.co.kr/learn/courses/30/lessons/17684# 분류: 카카오 블라인드 2018 3차, Lv2 접근방식 LZW(Lempel–Ziv–Welch) 압축 알고리즘을 구현해서 풀어보는 문제였습니다. 조금 헷갈리긴 했는데, 문제의 의사코드를 따라서 잘 구현해주면 해결할 수 있었습니다. 해결방법 func solution(_ msg:String) -> [Int] { var wordTable = makeTable() let msg = Array(msg).map { String($0) } var printIndices = [Int]() var offset = 0 while offset < msg.count { var w = msg[offset] var idx = wordT..
-
Programmers Lv2) 방금그곡Algorithm/Programmers 2020. 8. 28. 13:42
출처: programmers.co.kr/learn/courses/30/lessons/17683#qna 분류: 카카오 블라인드 2018 접근방식 musicinfos를 이용해 정보를 가공하고 주어진 music이 포함되는지 확인하는 문제입니다. 주의할 점은 # 이 포함되어 있는 음을 처리해주는 일인데요, 단순히 "ABC" 가 포함되어 있는지 확인한다면 "ABC#" 인 경우를 걸러주지 못합니다. 이를 체크하기 위해서는 대표적으로 두 가지 방법이 있습니다. 토큰화 "ABC#" 를 ["A", "B", "C#"] 와 같이 의미있는 단위로 쪼개서 비교하는 방법입니다. 치환 이 문제에서 의미있는 음표는 12개 뿐입니다. 따라서 "A#" 과 같은 음을 "a" 와 같이 의미없는 문자로 치환시켜서 해결해줍니다. 저는 토근화를..
-
Programmers Lv2) 후보키Algorithm/Programmers 2020. 8. 25. 17:06
출처: programmers.co.kr/learn/courses/30/lessons/42890 분류: 카카오 블라인드 2019 접근방식 유일성과 최소성을 만족하는 후보키를 찾는 문제입니다. 각 row를 유일하게 식별할 수 있다면 유일성을 만족합니다. 이미 후보키가 포함되어 있다면 최소성을 만족하지 못합니다. 유일성 확인 ["a","1","4"] ["2","1","5"] ["a","2","4"] 테이블이 다음과 같이 주어졌고 각 column을 0, 1, 2 라고 할 때, [0], [1], [2], [1,3] 는 모두 중복을 포함하고 있으므로 유일성을 만족하지 못해 후보키가 될 수 없고, [0, 1], [1, 2] 는 후보키가 될 수 있습니다. [1, 2, 3]은 이미 [1, 2]가 포함되어 있으므로 최소성..