알고리즘
-
[level2]튜플 - swift 풀이알고리즘/프로그래머스 2021. 4. 29. 17:42
문제 https://programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 19년도 카카오 겨울 인턴십에 나온 문제다. 문제 자체는 크게 어렵지 않은 문자열 다루는 문제인데, 처음에는 배열로 풀고, 배열 부분을 Set으로 바꾸니 해결 시간이 크게 줄어서 기록해본다. 위 사진처럼 Set을 이용했을 때의 시간이 훨씬 작은 것을 볼 수 있다. 나의 풀이 중점적으로 Set을 활용한 부분..
-
유클리드 알고리즘, 확장 유클리드 알고리즘알고리즘/이론 2021. 4. 20. 20:07
유클리드 알고리즘을 이용한 여러 코드를 짜 봅시다! 유클리드 알고리즘으로 GCD 구하기 GCD 즉, 두 수의 최대 공약수를 구하기 위해서 유클리드 알고리즘을 사용할 수 있습니다 두 수 a, b (a>b) 가 있을 때 a를 b로 나눈 나머지가 0이면 b는 a, b의 GCD이다 라는 알고리즘이 유클리드 알고리즘인데요. 이 때 나머지가 0이 아니면 0이 될 때까지 b와 a%b의 수로 위 과정을 반복해 줍니다. swift 코드로 알아볼게요 func gcd(_ a: Int, _ b: Int) -> Int{ var a = a, b = b if a < b { swap(&a, &b) } if a == b { return a } else if b == 0 { return a } else { return gcd(b, a ..
-
[level2]조이스틱 - swift 풀이알고리즘/프로그래머스 2021. 4. 20. 03:16
문제 https://programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 이 문제는 역시나 안일하게 생각했다가 큰 코 다친 문제였다. 예시로 나와있지 않은 테스트케이스 찾는게 아직도 어렵다.. 처음에 단순하게 앞에서부터 순서대로 보면서 다음 타겟을 찾고, 거기서 위/아래냐 좌/우냐만 검사해서 풀었더니 이런 결과가 나왔다 🥲 XAAAAAAAYZ 와 같은 경우나 BAAAAIAAAAAAE 의 경우에는 탐색 방향이 ..
-
최단 경로 (다익스트라, 플로이드 워셜 알고리즘)알고리즘/이론 2021. 3. 14. 20:53
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 최단 경로 가장 짧은 경로를 찾는 알고리즘. '길 찾기' 문제 라고도 불린다. 상황에 맞는 효율적 알고리즘이 정해져 있다! 예 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 보통 그래프를 이용하여 표현되고, 각 지점은 노드로, 지점 간 연결된 도로는 간선으로 표현된다. 보통은 최단 거리를 출력하는 문제가 많다. 대표적 알고리즘 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘이 가..
-
부품 탐색 문제를 여러 알고리즘으로 풀어보기 with 시간 복잡도알고리즘/이론 2021. 3. 6. 21:42
문제 N개의 부품 배열에서 M개의 문의 부품이 있는지 확인하여 "yes", "no"를 출력한다. 1 ≤ N ≤ 1,000,000 (100만) 1≤ M ≤ 100,000 (10만) → 최댓값 100만 이진 탐색 이용 let n = Int(readLine()!)! var inputs = readLine()!.split(separator: " ").map { return Int($0)!} print(n) print(inputs) let m = Int(readLine()!)! let targets = readLine()!.split(separator: " ").map { return Int($0)! } inputs.sort() for t in targets { binarySearch(inputs, t) } fu..
-
이진 탐색알고리즘/이론 2021. 2. 24. 21:22
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례로 확인하는 방법. 데이터의 정렬 여부와 상관없이 앞에 있는 원소부터 하나씩 확인한다. 시간복잡도는 O(N) func sequentialSearch(n: Int, target: String, array: [String]) -> Int { for i in 0.. Int? { if start > end { return nil } let mid = (start + end) / 2 if array[mid] == target { return mid } else ..
-
정렬알고리즘/이론 2021. 2. 11. 17:22
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 퀵 정렬(quick sort) 가장 많이 사용되는 알고리즘 데이터의 특성을 파악하기 어렵다면 퀵 정렬이 유리 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식 피벗 사용 : 교환하기 위한 기준 평균 시간 복잡도 $O(NlogN)$ 그러나 최악의 경우 (데이터가 이미 정렬이 되어 있을 경우) O(N^2)이다 일반적 퀵 정렬 코드 var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] func quick_sort(array: inout [Int], start: Int, end: Int) { ..