분류 전체보기
-
Permutation 순열Algorithm/Theory 2020. 6. 11. 12:48
안녕하세요. 문제를 풀다가 순열 관련 부분에서 머리가 터져버려(?) 순열에 대해 공부해보고자 합니다. 순열은 순서가 있는 열, 순서를 가지고 줄세우는 경우의 수 라고 생각하시면 됩니다. 1번과 2번의 사람이 있다면 이 둘을 줄세우는 경우의 수는 1, 2 2, 1 이렇게 2가지 경우가 있겠죠. 1, 2, 3 세 명의 사람이라면 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 이렇게 총 6가지 경우가 있습니다. 맨 앞 자리에 올 수 있는 사람의 수는 3 맨 앞자리가 정해졌다면 그 다음에 올 수 있는 사람의 수는 2 그 다음은 1 즉 순열의 경우의 수는 n! 이 됩니다. 여기까지는 많이들 알고계셨던 내용이겠죠? 이제 이를 코드로 구현하려면 어떻게 해야하는지 살펴보겠습니다...
-
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 }..
-
iOS) 실 기기인지 simulator인지 확인하기 in SwiftiOS 2020. 6. 10. 14:40
simulator에서 많은 부분을 테스트해볼 수 있지만, 꼭 실제 기기에서만 할 수 있는 기능들이 있죠. remote 노티라던지 위치라던지요? 이렇듯 시뮬레이터와 실제 기기를 구분해야 할 경우들이 있습니다. 이럴 땐 간단하게 이렇게 구분할 수 있습니다. #if targetEnvironment(simulator) // Simulator #else // Device #endif 혹은 if TARGET_IPHONE_SIMULATOR == 1 { // Simulator } else { // Device } 감사합니다 :)
-
백준 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 ..