LV3
-
Programmers Lv3) [2020 카카오 인턴십] 경주로 건설Algorithm/Programmers 2021. 4. 21. 17:16
출처: programmers.co.kr/learn/courses/30/lessons/67259 분류: Lv3, BFS 접근방식 BFS 방식으로 해결했습니다. 조금 확장된 개념이 들어가는데, 단순히 방문 체크에 더해서 비용과 방향까지 기록해주면서 탐색해나가면 됩니다. 방향까지 체크해주는 이유는 같은 가격이여도 어떤 방향에서 오는지에 따라 달라질 수 있기 때문입니다. 현제 체크되어 있는 방향의 비용보다 더 작다면 다시 방문해주는 방식이 되겠습니다. 저는 enum으로 방향을 정의해주고 (그냥 Int나 bool 변수 등으로 정의해도 상관없을 것 같습니다.) Point 를 하나 정의해서 가지고 있도록 해줬습니다. enum Direction: Int { case horizontal = 0, vertical } ty..
-
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) 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) 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..