Algorithm
-
합병정렬 Merge sortAlgorithm/Theory 2020. 5. 14. 20:04
목표 합병 정렬을 이해한다. 합병 정렬을 Swift로 구현한다. 합병 정렬의 시간 복잡도를 이해한다. ( O(nlogN) ) 총 재귀 호출 횟수는 2n-1 합병 정렬 ? 합병 정렬은 분할정복 알고리즘의 하나입니다. 합병 정렬의 아이디어는 이미 정렬된 두 배열이 있다면 각 배열의 첫번째 원소끼리 비교해 정렬된 새로운 배열을 만들 수 있다. 에서 시작합니다. 이 정렬된 두 배열을 얻기 위해 일단 최대한 작게 쪼개고 다 쪼갰다면, 위의 아이디어를 이용해 정렬된 새로운 배열을 만들어 나가는 것이죠. 구체적으로 아래와 같은 과정을 거치게 됩니다. 1. 길이가 1 이하인 리스트는 정렬된 것으로 본다. 2. 분할(divide): 길이가 2이상이면 리스트는 반으로 쪼갠다. 3. 정복(conquer): 분할된 각 부분의..
-
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% ... 👀 문제의 핵심은 기둥과 보를 설치하고 삭제할 때 조건을 명확하게 이해하고 구현할 수 있느냐에 있습니다. 생각보다 여러가지 상황이 있기 때문에 각 케이스 별로 잘 분류해서 명확하게 풀어야겠어요. 저는 설치 / 삭제 기둥 / 보 상황별 이런식으로 쪼개서 케이스를 최대한 나눠서 풀어보았습니다. 해결방법 먼저 설치부터 확인해보죠. 설치는 기둥 설치, 보 설치 상황이..
-
Programmers) Lv3 [2020카카오공채] 자물쇠와 열쇠Algorithm/Programmers 2020. 4. 3. 21:13
출처: https://programmers.co.kr/learn/courses/30/lessons/60059#qna 분류: Lv3, 2020 카카오 공채 접근방식 배열의 크기가 3~20 으로 범위가 크지 않기 때문에 각각의 케이스를 맞춰가면서 됩니다. 핵심 포인트는 3가지 입니다. 1. lock 과 key 를 맞춰서 열 수 있는지 확인할 수 있어야 합니다. 2. 주어진 범위 안에서 key를 이동시킬 수 있어야 합니다. 3. key 를 회전시킬 수 있어야 합니다. 주의할 점은 범위를 설정할 때, key의 끝 부분이 lock의 시작 점에 오는 점부터 key의 시작 부분이 lock의 끝 점에 오는 점까지 를 확인해야 합니다. 문제의 예처럼 key와 lock이 둘 다 (3,3) 인 배열이라면, key의 끝 부분..
-
Programmers) Lv2 [2020카카오공채] 괄호 변환Algorithm/Programmers 2020. 3. 25. 15:04
출처: https://programmers.co.kr/learn/courses/30/lessons/60058 분류: Lv2 접근방식 문제에서 알고리즘 방법을 단계별로 잘 나눠서 알려주고 있습니다. 잘 읽고 "그대로" 구현만 잘 하면 되는 문제 입니다. (그치만 그게 어렵네요 😭) 포인트라면 반복적인 재귀형태가 들어가기 때문에 기능별로 함수를 쪼개서 구현하는 능력이 필요할 것 같네요. 출제의도 역시 다음과 같습니다. 주어진 로직을 그대로 구현할 수 있는지 파악 재귀함수를 이해하고 작성할 수 있는지 파악 해결방법 저는 주요 기능 (함수)을 크게 4가지로 나눠봤습니다. 1. 문자열을 쪼개는 1 ~ 4 번을 수행하는 함수 (trimming) func trimming(_ p: String) -> String { ..
-
Programmers) Lv2 [2020카카오공채] 문자열 압축Algorithm/Programmers 2020. 3. 16. 15:24
출처: https://programmers.co.kr/learn/courses/30/lessons/60057 분류: Lv2 문자열 접근방식 문자열의 길이 N의 절반 이상으로 자르면 압축할 수가 없습니다. 주의 할 개념은 이정도 나머지는 구현이 핵심입니다. 카카오 테스트 해설의 출제의도는 다음과 같습니다. 문자열을 다룰 수 있고, 아래 예시와 같이 문자열과 관련된 다양한 작업을 할 수 있는지 파악 문자열 자르기 부분 문자열 얻기 문자열 비교하기 문자열 길이 얻기 Swift 는 문자열 다루기가 상대적으로 까다로운데 자유자재로 사용하려면 역시 많은 연습이 필요하겠습니다 😥 해결방법 1 ~ N/2 까지 잘라가며 압축 문자열의 길이가 가장 작은 값을 찾아냅니다. 앞에서부터 압축 문자열의 길이로 잘라내면서 중복을 ..
-
Programmers) Lv2 스킬트리Algorithm/Programmers 2020. 3. 15. 16:40
출처: https://programmers.co.kr/learn/courses/30/lessons/49993 분류: Lv2 접근방식 선행 스킬에 없는 스킬은 무시하면 되고 선행 스킬의 스킬을 순서대로 배우는지 확인하면 되는 문제입니다. 해당 키값(스킬)에 빠르게 접근할 수 있는 자료구조가 필요하다고 생각했고 해시를 떠올렸습니다. 해결방법 따라서 가장 먼저 배워야 하는 선행 스킬만 true 나머지는 false로 해서 Dictionary로 만들었습니다. 그 후 true인 스킬을 확인하고 나면 그 다음 선행 스킬을 true로 만들어줍니다. 선행 스킬이 모두 true가 되면 그 스킬 트리는 배울 수 있으므로 카운팅해주고 넘어갑니다. 당연히 선행 스킬에 없는 스킬은 nil 값이므로 넘어가면됩니다. func sol..
-
Programmers) Lv3 섬 연결하기Algorithm/Programmers 2020. 3. 6. 19:39
출처: https://programmers.co.kr/learn/courses/30/lessons/42861 분류: Lv3 , Greedy MST의 대표적인 문제입니다!!! Prim 알고리즘으로 해결해봤는데요. 자세한 설명은 이론 설명 그 자체일 듯 합니당 다음글을 참고해주세용 :) /** * 현재 노드에 연결되어 있는 노드만 확인할 것이기 때문에 * 간단하게 목적지와 비용만 저장하는 Edge 를 정의합니다. */ struct Edge { var destination: Int var cost: Int } func updateDist(_ tree: [Edge], dist: inout [Int?]) -> [Edge] { for edge in tree { if let d = dist[edge.destinati..