algorithm
-
Recursion 재귀Algorithm/Theory 2020. 6. 11. 12:21
많은 일들은 대개 작은 조각들로 나누어 볼 수 있습니다. 그리고 한 조각이 작으면 작을수록 일은 단순해지고 반복되는 형태를 띄는 경우가 많습니다. 완전히 같은 코드를 반복적으로 하는 작업이 있다면 이때 재귀 함수(recursion fnction), recursion(재귀 호출)이 유용하게 사용될 수 있습니다. 1~100까지의 합을 구하는 경우를 재귀적으로 생각해봅시다. 1~100까지의 합은 100 + 1~99까지의 합으로 나눠서 생각할 수 있습니다. 마찬가지로 1~99까지의 합은 99 + 1~98까지의 합으로 볼 수 있겠죠. "n + 1~n-1까지의 합" 이라는 과정은 완벽하게 동일합니다. 이를 코드로 구현해보면, func sum(_ n: Int) -> Int { if n == 1 { return 1 }..
-
백준 1049 기타줄Algorithm/BOJ 2020. 6. 8. 16:18
출처: www.acmicpc.net/problem/1049 분류: 그리디 접근방식 패키지와 낱개의 가격이 주어지고 고장난 기타줄 이상을 살 수 있는 최소가격을 구하는 문제입니다. 최소 가격을 구하는 문제이므로 패키지와 낱개 각각의 최소값에만 신경쓰면 됩니다. 동전나누기와 비슷하죠? 낱개 6개 가격이 패키지 가격보다 싸지만 않다면 패키지만큼 다 나눠주고 나머지랑 패키지랑 비교해서 풀면 됩니다. 해결방법 let n = readLine()!.split(separator: " ").map{Int($0)!} var minPackage = Int.max var minPiece = Int.max for _ in 0.. minPiece * 6 { print(n[0] * minPiece) } else { var tota..
-
백준 1946 신입 사원Algorithm/BOJ 2020. 6. 8. 15:54
출처: www.acmicpc.net/problem/1946 분류: 그리디 접근방식 다른 사람보다 서류와 면접 점수가 모두 낮은 경우엔 탈락, 합격한 사람의 수를 구하는 문제입니다. 서류 1등은 무조건 합격입니다. 1등보다 면접 등수마저 낮다면 그 사람은 탈락이 되겠죠. 이때 1등의 면접 등수가 서류 2등 ~ 나머지 사람의 합격을 가르는 기준점이 됩니다. 1등의 면접 점수보다 낮은 사람을 모두 거르고 나면 남아있는 사람 중 서류 1등이 다시 합격의 기준점이 되죠. 이를 반복해주면 합격자의 수를 구할 수 있습니다. 하지만 이렇게 해주면 시간 초과가 납니다. (Swift 기준) 매번 나머지를 다시 도는건 너무 비효율적인 방법이죠. 보다 효율적으로 해결할 수 있는 방법이 있습니다. 서류 1등의 면접 등수를 기준..
-
백준 1120 문자열Algorithm/BOJ 2020. 6. 8. 14:58
출처: www.acmicpc.net/problem/1120 분류: Greedy 접근방식 앞뒤로 아무 문자나 붙여서 길이를 같이 만들 때 차이가 가장 적은 경우를 찾는 문제입니다. 앞뒤로 아무 문자나 붙일 수 있으므로 현재 문자열과 비교할 문자열만 가지고 비교하면 나머지는 길이를 맞춰버릴 수 있습니다. 예제 케이스처럼 adaabc aababbc 를 보면, 0번 인덱스부터 adaabc와 adaabc의 길이만큼인 aababb 와 비교해보면 다른 개수는 3개입니다. 나머지는 adaabc 뒤에 c를 붙여버리면 길이를 똑같이 만들 수 있겠죠 1번 인덱스부터 adaabc와 adaabc의 길이만큼인 ababbc 와 비교해보면 다른 개수는 2개입니다. 마찬가지로 앞에 a를 붙여서 길이를 똑같이 만들 수 있겠죠 해결방법 ..
-
백준 1541 잃어버린 괄호Algorithm/BOJ 2020. 6. 7. 15:18
출처: www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 분류: Greedy +와 -만으로 이루어진 연산이 들어올 때 괄호를 묶어서 최소인 수를 만드는 문제입니다. + 연산부터 해주고 - 연산을 해주면 최소의 값을 구할 수 있습니다. - 로 우선 다 잘라준 다음에 각각을 다 더해주고 마지막에 빼주는 방식으로 해결했습니다. import Foundation var str = readLine()! var plusOpers = str.components(sepa..
-
위상정렬 Topological SortAlgorithm/Theory 2020. 6. 7. 13:21
목표 - 위상정렬 (Topological Sort)를 이해하고 설명할 수 있다. - 위상정렬의 조건을 알고 언제 어떻게 사용하는지 이해한다. 위상정렬? \ 특정한 순서를 가진 조건에서 사용한다. DAG(방향성 비순환 그래프) 에서만 사용할 수 있다. \ "위상" 이라는 사전적 정의에서 알 수 있듯이, 위상정렬이란 어떤 순서를 가지고 있는 경우에 사용할 수 있는 정렬 방법입니다. 게임을 하는데 어떤 스킬을 익히기 위해 반드시 먼저 배워야 하는 사전스킬이 있죠? 이런 식으로 어떤 순서를 가지고 있을 때 사용합니다. 이 말인즉 위상정렬은 방향성을 가지고 있어야 합니다. 그리고 이 의미를 잘 생각해보면 사이클이 생기면 안된다는 것을 알 수 있습니다. A -> B -> C 순서를 가지고 있어야 하는데 여기서 C ..
-
1029. Two City SchedulingAlgorithm/LeetCode 2020. 6. 4. 13:17
출처: leetcode.com/problems/two-city-scheduling/ 분류: Greedy, Easy 접근방식 각 cost에는 A와 B에 보낼 수 있는 비용이 들어있습니다. 2N개의 비용이 적힌 costs에서 각각 N개씩 공평하게 A와 B에 나눌 때 최소비용을 찾는 문제입니다. costs가 [[10,20],[30,200],[400,50],[30,20]] 이렇게 주어져 있다면, A에 2개 B에 2개를 [ 10, 30, 50, 20 ]로 뽑아줄 때 가장 최소비용이 됩니다. 하지만 무작정 둘 중 최소를 찾아서 분배한다고 해서 최소비용을 보장할 수가 없습니다. costs 중에서 어떤 cost를 우선적으로 분배해줘야 할까요? 바로 둘의 차이가 큰 cost를 먼저 분배해줘야 나중에 더 작은 비용을 분배..
-
1046. Last Stone WeightAlgorithm/LeetCode 2020. 5. 31. 11:15
출처: leetcode.com/problems/last-stone-weight/ 분류: Greedy, Easy 접근방식 무게가 가장 큰 돌과 그 다음으로 큰 돌을 부시면서 1개의 돌이 남을 때까지 반복하는 문제 입니다. 두 돌의 무게가 같다면 그대로 없어지고 한쪽이 더 크다면 그 나머지가 다시 남은 돌이 됩니다. 문제는 두 돌을 골라서 부실 때마다 돌의 우선순위가 바뀐다는 점입니다. 즉, 매 스탭마다 가장 큰 돌이 바뀔 수 있다는 점이죠. 이 점을 잘 체크하면 되는 문제입니다. 해결방법 단순하게 매 스탭마다 max를 2번 뽑아서 제거해주는 방법을 사용할 수도 있겠으나, swift 기준으로 max의 시간복잡도가 O(n) 이고 max의 인덱스를 찾는데 O(n), 이를 제거하는데 O(n) 의 시간이 소요됩니다..