algorithm
-
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]가 포함되어 있으므로 최소성..
-
Combination 조합Algorithm/Theory 2020. 8. 25. 14:26
- n개의 원소에서 r 개의 원소를 순서에 상관없이 뽑는 경우의 수 - nCr = n! / (n-r)! * r! - nCr = n-1Cr-1 + n-1Cr 조합? 조합은 n 개의 원소 중에서 순서를 고려하지 않고 원하는 개수만큼 뽑는 경우의 수를 말합니다. 순서를 고려해서 뽑는 순열에서 중복을 제거해준 형태로 볼 수 있죠. 따라서 순열에서 r! 만큼 더 나눠준 형태를 띕니다. nCr = nPr / r! = n! / (n-r)! * r! 조합에는 기억해야 할 중요한 성질이 있습니다. 결론부터 보면, nCr = n-1Cr-1 + n-1Cr 의 공식인데요, 이 의미를 살펴보면, 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우를 나타냅니다. 예를 들어, [1, 2, 3] 에서 2개를 뽑는 경우의..
-
Programmers Lv2) 캐시Algorithm/Programmers 2020. 8. 24. 19:57
출처: programmers.co.kr/learn/courses/30/lessons/17680 분류: Lv2 접근방식 LRU(Least Recently Used)의 개념을 알면 쉽게 풀 수 있는 문제입니다. LRU란 캐시를 관리하는 방법인데요, 캐시를 비울 때 가장 오래 사용되지 않은 녀석을 지우는 방식입니다. 만약 캐시의 크기가 4이고, [1, 2, 3, 4] 가 들어있을 때, 2가 추가로 들어온다면 2가 가장 최신에 사용된 것이 되므로 캐시는 [1, 3, 4, 2]로 변하게 됩니다. 만약 도시가 이미 캐시에 들어있다면 cache hit 이 되어 시간 1이 추가되고, 캐시에 없다면 chache miss가 되어 5가 추가됩니다. 저는 처음에 시간 복잡도를 생각해서 링크드 리스트와 딕셔너리를 섞어서 굉장히..
-
백준 13460 구슬 탈출 2Algorithm/BOJ 2020. 7. 24. 13:32
출처: www.acmicpc.net/problem/13460 분류: 완전 탐색 접근방식 상하좌우로 회전시킬 수 있는 보드판 위에 빨강, 파랑 구슬, 빠져나갈 구멍이 있을 때 움직여서 빨간 구슬만 구멍에 넣어야 할 때 최소 횟수를 찾는 문제입니다. 단, 횟수가 10번을 초과하면 안됩니다. 판의 크기가 3 ~ 10 까지로 매우 작고 10번이라는 제한이 있기 때문에 모든 경우를 다 탐색해서 말그대로 완전 탐색으로 해결할 수 있습니다. 개인적으로 구현이 꽤나 까다로웠던 문제였습니다. 상하좌우로 다 해본다는 게 말은 쉽지만 생각보다 까다로웠습니다. 두 구슬은 겹칠 수 없기 때문에 다른 구슬이 앞에 있다면 그 구슬 뒤까지 움직여야 하고 말이죠... 구현 아이디어는 다음과 같습니다. 빨간 구슬과 파란 구슬은 계속 굴..