Algorithm
-
프림 알고리즘Algorithm/Theory 2020. 3. 6. 17:13
- MST(Minimum Spanning Tree)를 만드는 방법 중 하나입니다. - 현재 트리를 기준으로 가장 최소인 점을 찾아나가는 방식입니다. - 사이클을 확인할 필요가 없습니다. (현재트리를 기준으로 하기 때문에 사이클이 생기지 않습니다.) 프림 알고리즘은 현재까지 생성된 트리를 기준으로 가장 최소 비용의 간선을 선택해서 트리를 확장시켜 나갑니다. 현재 트리를 기준으로 한다는 말 속에는 이미 방문한 점은 방문하지 않는다는 말이 포함되어 있습니다. 때문에 자연스럽게 사이클이 생기지 않습니다 :) 과정은 간단합니다. 1. 현재 트리를 기준으로 최소 비용으로 방문 가능한 점을 방문합니다. 2. 새로운 점을 기준으로 최소 간선의 목록을 업데이트 합니다. 직접 문제를 하나 풀어보면 쉽게 이해하실 수 있으실..
-
Programmers) Lv2 조이스틱Algorithm/Programmers 2020. 1. 29. 16:50
출처: https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 | 프로그래머스 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다. - 첫 번째 위 programmers.co.kr 분류: Lv2, Greedy 너무너무 어려웠던 문제... 하 어렵네..
-
Swift) GenomicRangeQuery in CodilityAlgorithm/Codility 2020. 1. 3. 18:06
https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ GenomicRangeQuery coding task - Learn to Code - Codility Find the minimal nucleotide from a range of sequence DNA. app.codility.com 출처: Codility 분류: Lesson5 Prefix Sums 개인적으로 매우 매우 고통 받았던 문제입니다.. "푸는 것" 자체는 어렵지 않게 할 수 있으나 시간 복잡도를 통과하기가 굉장히 어려웠습니다.. Hㅏ.... 문제를 간단히 요약하면 ACGT 로 이루어진 유전자 배열 S와 유전자의 부분의 인덱스가 들어있는 P, Q가 주어..
-
Lv2 위장Algorithm/Programmers 2019. 12. 30. 16:58
출처: https://programmers.co.kr/learn/courses/30/lessons/42578 코딩테스트 연습 - 위장 | 프로그래머스 programmers.co.kr 분류: Lv2 해시 처음엔 쉬워보였지만 개인적으로 꽤 어려웠던 문제였습니다... "중복된 이름은 없으니 분류별로 개수만 카운팅하면 되겠다" 라고 생각하며 접근했지만 그 이후 경우의 수를 어떻게 계산해야 할 지가 문제였습니다. 단순히 종류별 개수로 곱하면 경우를 다 포함하지 못하고.. 종류별로 1개를 뽑는 경우, 2개를 뽑는 경우 ... 로 나눠보자니 종류별로 개수가 다르고.. 결국 다른 분들의 풀이를 찾아보았습니다. 이 문제의 가장 큰 포인트는 의상을 최소 1개만 선택하면 더 이상을 뽑지 않아도 된다는 것입니다. 1개만 뽑으..
-
Lv2 쇠막대기Algorithm/Programmers 2019. 12. 24. 15:46
출처: https://programmers.co.kr/learn/courses/30/lessons/42585 코딩테스트 연습 - 쇠막대기 | 프로그래머스 여러 개의 쇠막대기를 레이저로 절단하려고 합니다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자릅니다. 쇠막대기와 레이저의 배치는 다음 조건을 만족합니다. - 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다. - 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다. - 레이저는 어 programmers.co.kr 분류: Lv2 스택/큐 닫히는 ")"를 만났을 때 이게 레이저인지 ..
-
다리를 지나는 트럭 Lv2Algorithm/Programmers 2019. 12. 23. 21:55
출처: https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서 programmers.co.kr 분류: Lv2, 스택/큐 순서대로 서있는 트럭들이 다리를..
-
Algorithm) 숫자 하나씩 확인하기Algorithm 2019. 7. 3. 14:49
17037300 와 같이 큰 수를 한 글자씩 확인해야 할 경우가 있습니다. 예를들어 다음과 같은 문제를 풀 경우가 되겠네요. 어려운 문제는 아니지만 꽤나 자주 등장하기 때문에 한번 짚고 넘어가고 싶어 포스팅을 하게 되었습니다 :D 1. 문자열로 바꿔서 하나씩 탐색 제 경우에 가장먼저 떠오른 생각은 문자열로 바꿔서 하나씩 탐색 하기였습니다. 이러한 방식으로 위 문제를 풀면 let numString = String(a*b*c) var numbers = [Int](repeating: 0, count: 10) for s in numString { if let n = Int(String(s)) { numbers[n] += 1 } } 다음과 같이 풀 수 있겠네요. 이러한 방식은 Swift와 같이 형변환이 까다로운 ..
-
Algorithm) BOJ) 백준 1744 - 수묶기Algorithm/BOJ 2019. 6. 26. 23:18
Algorithm) BOJ) 백준 1744 - 수묶기 문제보러가기 1. 초기접근 문제 조건 해석 두 개의 수를 묶어서 곱해서 더해나가 가장 큰 수가 되게 묶는 문제다. 문제를 보고 가장 먼저 떠올린 생각은 큰 수끼리 곱하면 큰 수가 된다는 것. 따라서 정렬해서 묶어 나가면 되겠다. 음수는? 어쩔 수 없으니다 더하자. 라고 생각 하셨다면.. 저와 같이 좀 더 힘내자구요 우리..ㅠㅠ 음수와 음수를 곱하면 양수가 된다. 여기서 끝이 아니고 몇 가지 경우를 더 생각해야 한다. 1은 곱하는 것보다 더하는 것이 더 크다. 음수가 하나 남았고 0도 남아있다면 둘을 곱해서 없애버리는게 더 크다. 이렇게 3가지를 기억하면 이 문제를 풀 수 있다. 알고리즘 양수, 음수와 0 으로 나눠서 배열을 만든다. 양수는 오름차순, ..