Swift
-
백준 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 ..
-
#selector 에 parameter 전달하기iOS 2020. 6. 4. 15:01
addTarget, UIGestureRecognizer 등을 사용할 때 action을 주기 위해 #selector를 사용합니다. 하지만 #selector를 사용할 때는 임의로 파라미터를 전달할 수가 없고 오직 sender 로 버튼이나 제스쳐 같은 대상만을 파라미터로 받을 수가 있습니다. 오늘 알아볼 방법은 원하는 파라미터를 전달할 수 없으니 대신 파라미터가 되는 대상을 원하는 아이로 바꾸는 방법입니다. 바로 예시를 살펴보겠습니다. \ swipe를 할 때 원하는 정보를 함께 전달하고 싶어요 \ 보통 일반적인 스와이프 제스쳐는 이렇게 생성합니다. override func viewDidLoad() { super.viewDidLoad() let swipeGesture = UISwipeGestureRecogniz..
-
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) 의 시간이 소요됩니다..
-
1217. Play with ChipsAlgorithm/LeetCode 2020. 5. 28. 13:40
출처: leetcode.com/problems/play-with-chips/ 분류: Greedy, Easy 접근방식 문제 자체를 이해하기가 어려웠던 문제였습니다. 간단히 요약하면, chips 에는 chip이 있는 index 가 적혀있습니다. 즉, chips = [2,2,2,3,3] 이렇게 주어져 있다면, 아래와 같은 모습으로 생각할 수 있습니다. 칩이 있는 인덱스 1 2 3 칩의 개수 0 3 2 이 칩들은 좌우로 2칸을 움직일 때는 비용이 없고 1칸을 움직일 때는 1의 비용이 듭니다. 여기서 이 칩을 한 곳으로 모으는 방법은 2가지 방법이 있습니다. 2에 있는 칩3개를 3으로 옮기는 방법 --> 비용 2 3에 있는 칩 2개를 2로 옮기는 방법 --> 비용 3 당연히 3을 2로 옮기는게 좋겠죠?? 다음으로..
-
1221. Split a String in Balanced StringsAlgorithm/LeetCode 2020. 5. 23. 21:34
출처: https://leetcode.com/problems/split-a-string-in-balanced-strings/ Split a String in Balanced Strings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 분류: Greedy, Easy 접근방식 "L", "R"로 이루어진 문자열에서 짝이 맞는 문자열의 개수가 얼마나 되는지 찾는 문제입니다. 저는 처음에 L 과 R 의 개수를 저장하는 변수를 만들고 카운트 해주면서 둘이 같아지면 ba..