Algorithm/Programmers
-
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]가 포함되어 있으므로 최소성..
-
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가 추가됩니다. 저는 처음에 시간 복잡도를 생각해서 링크드 리스트와 딕셔너리를 섞어서 굉장히..
-
Programmers Lv3) 방문 길이Algorithm/Programmers 2020. 7. 10. 13:54
출처: programmers.co.kr/learn/courses/30/lessons/49994 분류: Lv3 접근방식 -5 ~ 5 까지의 정사각형에서 U, D, R, L 중 하나로 이동 방향들이 주어질 때, 처음 이동한 길의 개수를 세는 문제입니다. 저는 처음에 Set 로 이루어진 11x11 맵을 만들고 각 칸에 이동한 위치를 넣는 엄청나게 무식한 방법을 사용했는데, 단순히 새로운 길의 개수만 알면 되기 때문에 이럴 필요 없이 그냥 좌표만 가지고도 해결할 수 있는 문제입니다. 갈 수 있는 길이라면 그 길을 그냥 Set 에 String 으로 때려박으면 매우 간단해집니다. 주의할 점은 (0, 0) -> (0, 1) 로 이동했다면 반대로 오는 (0, 1) -> (0, 0) 도 같은 길로 체크해야 합니다. 해결..
-
Programmers) Lv2 가장 큰 수Algorithm/Programmers 2020. 5. 1. 11:06
출처: https://programmers.co.kr/learn/courses/30/lessons/42746 분류: Lv2, 정렬 접근방식 주어진 수로 만들 수 있는 가장 큰 수를 구하는 문제입니다. 처음엔 첫 자리부터 비교하려고 했었는데요, 이렇게 하면 매우 복잡해집니다. 우선 앞 자리부터 비교하기가 어렵습니다. 길이를 알면 자리수로 나눠볼텐데 그것도 안되고 뒤집자니 뒤가 0이라면 날라갈테고 문자열로 바꿔서 한 자리씩 비교하더라도 각각의 길이가 다르기 때문에 어렵습니다. 무작정 길이가 짧다고 앞에 둘 수가 없습니다. 가령, [5, 559] 가 있다면 5559 < 5595 가 되어버립니다. 중간에 0이 껴있는 경우는 어떻게 처리 할 것이며... 네 첫 단추를 잘못 끼웠습니다... 결국 다른 분들의 풀이를..
-
Programmers) Lv3 [2020카카오공채] 기둥과 보 설치Algorithm/Programmers 2020. 4. 14. 14:28
출처: https://programmers.co.kr/learn/courses/30/lessons/60061 분류: Lv3 접근방식 문제에 제시된 조건대로 잘 구현할 수 있는지 구현 능력을 파악하는 문제입니다. 특별한 기술이나 이론이 필요한 문제는 아닙니다. 조건에 맞게 잘 구현하면 됩니다... 잘 잘.. 잘.... 네... 정답률 1.9% ... 👀 문제의 핵심은 기둥과 보를 설치하고 삭제할 때 조건을 명확하게 이해하고 구현할 수 있느냐에 있습니다. 생각보다 여러가지 상황이 있기 때문에 각 케이스 별로 잘 분류해서 명확하게 풀어야겠어요. 저는 설치 / 삭제 기둥 / 보 상황별 이런식으로 쪼개서 케이스를 최대한 나눠서 풀어보았습니다. 해결방법 먼저 설치부터 확인해보죠. 설치는 기둥 설치, 보 설치 상황이..