Swift
-
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가 추가됩니다. 저는 처음에 시간 복잡도를 생각해서 링크드 리스트와 딕셔너리를 섞어서 굉장히..
-
DispatchQueueiOS 2020. 8. 11. 23:22
iOS의 쓰레드 스케줄링을 처리해줄 DispatchQueue 대해 공부해보겠습니다 :) DispatchQueue 공식 문서의 설명을 간단하게 살펴볼까요? An object that manages the execution of tasks serially or concurrently on your app's main thread or on a background thread. 앱의 메인쓰레드 또는 백그라운드 쓰레드에서 작업의 순차적(serially) 혹은 병렬적(concurrently) 처리를 관리하는 Object 네 설명 끝입니다. 역시 공식문서 답게 완벽한 요약이네요 👏 하지만 이대로 끝낼 순 없으니 이제 이 말 뜻을 조금 더 풀어서 알아보겠습니다 :) 다시한번 DispatchQueue란 iOS의 thr..
-
순수함수 Pure functionSwift 2020. 8. 4. 21:42
순수 함수란 수학에서 사용하는 함수를 떠올리시면 좋습니다. f(x) -> y 위 함수의 의미는 아시겠죠? x를 넣으면 y가 나온다. 네 프로그래밍에서 말하는 순수 함수도 정말 순수하게 '수학에서 사용하는 함수처럼' 동작하는 함수에 가깝게 만들자 라는 취지에서 출발했다고 합니다. 프로그래밍에서 순수 함수는 다음 정의를 따릅니다. 동일한 입력에는 항상 같은 값을 반환해야 한다. 함수의 실행은 프로그램의 실행에 영향을 미치지 않아야 한다. (Side effect 가 없어야 한다) 예를 들어, 함수 내부에서 인자의 값을 변경하거나 프로그램 상태를 변경하는 것 수학에서의 함수처럼 동일한 입력에는 항상 같은 값을 반환해야 합니다. 그리고 함수의 결과가 외부에 영향을 주지도, 받지도 않는 함수를 순수함수 라고 합니다..
-
ReduceSwift 2020. 8. 4. 15:22
Reduce에 대해 알아보겠습니다! Reduce 정의부터 살펴볼까요?? 직역해보면 연속된 원소들을 클로저를 이용해 결합시키고 그 결과를 리턴한다. 정도로 이해할 수 있을 것 같아요. reduce는 2개의 파라미터 initialResult, nextPartialResult 와 1개의 Result 를 return 합니다. 공통점이 보이시나요? 네 파라미터와 결과가 모두 어떤 Result 들을 리턴하고 있습니다. reduce를 사용하는 목적을 생각해볼까요? 위 정의의 Return Value 를 보면 the final accumulated value, 최종적으로 계산된 값을 리턴한다고 나와있습니다. 단계 단계가 다 결과이니 만약 시퀀스의 원소가 없다면, 즉 nextPartialResult가 없으면, 초기값(초기..