f(n) = a1 * n + a0 g(n) = n 모든 n >= n0에 대해 f(n) = n0에 대해 f(n) 7 ≤ n 일 때 모든 10 < n 이 성립한다. 2번 조건에서 n이 7보다 크거나 같으면 f(n)

백트레킹 진행 과정에서 답이 아닌 분기를 만나면 탐색을 진행하지 않고 돌아가 다른 분기로 감으로써 가지치기를 한다는 차이가 있다. 조건에 맞지 않는 분기에서 가지 치기를 하고, 부모 노드로 돌아가 다른 자식을 검색한다 First In Last Out을 하는 Stack과 재귀를 사용해서 구현할 수 있다. 모든 요소를 포함하고 있는 그래프에서 조건에 맞게 분기를 할지 말지 결정하는 것이 아니라 그래프(혹은 배열)에 바로바로 추가할지 말지를 결정해야 하는 문제이다. 또한 조건을 만족하는 답을 찾아서 끝내는 것이 아니라 재사용을 위해서 마지막 요소를 popLast() 하고 부모 노드로 돌아가서 재귀를 이용해야 한다. [popLast()와 removeLast()] - 둘 다 배열의 마지막 요소를 제거하지만 pop..

스위프트의 경우 pascal(n: n-1, k: k-1) + pascal(n: n-1, k: k)를 DP를 이용해서 풀면 시간초과의 문제가 생긴다. -> 시간초과를 해결하기 위해서는 2차원 배열에 값들을 저장해서 c[n-1][k-1] + c[n-1][k]를 계산해서 문제를 풀 수 있다. 1. 먼저 이항계수의 성질은 nCk = n-1Ck-1 + n-1Ck 2. nC0 = 1, nCn = 1 을 사용해서 문제를 풀 수 있다. 위의 2가지를 사용한다면 풀 수 있는 문제이지만, 한 번에 풀지 못해 다른 블로그를 참고했을 때 이해 되지 않던 점을 정리해보았다. 1. 범위를 k가 n을 초과할 수 없는 이유 - 이항계수 값을 저장할 배열은 [N+1][N+1]개의 사각형 형태의 이차원 배열로 저장했지만 당연히 이항계수..

주어진 수의 최대공약수의 약수를 구하는 문제이다. - 주어진 수의 규칙을 찾아내는 것이 중요하다. - 나머지(r)가 모두 같게 되는 M을 구하는 문제 1. 모든 수에서 r을 빼면 M으로 나눠진다. 2. 가장 큰 M을 구하고(최대공약수), M의 약수를 구하면 된다. - 사실 이 문제를 풀면서 런타임 에러가 많이 발생했는데 이유를 찾을 수 있었다. - 차(gap: input[1] - input [0])를 새로운 정렬에 저장해서 gcf를 구했는데, 이때 변수의 범위를 잘 못 지정해서 런타임 에러가 발생했다. for i in 1..

최대공약수와 최소공배수를 구하는 문제에서는 최대공약수만 안다면 최소공배수는 쉽게 구할 수 있다. 1. 최대 공약수를 부르트포스 처럼 모든 수로 나누는 방법을 생각했지만 유클리드 호제법이라는 알고리즘이 있었다. 유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 ..

방정식도 없이 경로를 구하라고? - 그렇다. 내 맘대로 하면 되는 문제지만 사실 경로가 필요 없는 문제다. - 주어진 입력을 좌표상에 그려보고 규칙을 찾을 수 있었다. - 1. 출발과 도착지점이 원의 안에 있는지 밖에 있는지가 이 문제를 해결하는 방법이다. 1 - 1. 출발과 도착지점이 원의 안에 있다면 원의 경계를 지나지 않고는 이동할 수 없기 때문에 카운트 +1 (= 보라색 점) 1 - 2. 출발과 도착지점이 원의 밖에 있다면 해당 원은 무시해도 된다. (= 초록색 해당 없음) - 2. 여기서 주의할 점은 주황색 원이다. 2 - 1. 출발과 도착지점 둘 다 주황색 원 안에 위치해 있다. 2 - 2. 이 경우는 주황색 원을 지날 필요가 없기 때문에 카운트하지 않고 무시한다. (= 주황색 해당 없음) -..

큰 사각형 - 작은 사각형의 문제다. 문제점은 작은 사각형을 어떻게 구하는지 - 작은 사각형의 변은 큰 사각형의 변과 인접하지 않는다. - 큰 사각형의 가로 변(160)에 인접한 변은 세로변들(30, 50) 세로 변(50)에 인접한 변은 가로변들(160, 100) - 세로변들 차의 절대값(30 - 50)은 작은 사각형의 세로 변 길이(20) - 가로변들 차의 절대값(160, 100)은 작은 사각형의 가로 변 길이(60) - 작은 사각형변 길이(20) X 세로 사각형 변 길이(60) = 작은 사각형 넓이(1200) //코드 import Foundation let num = Int(readLine()!)! var LV = 0; var LH = 0 var VIdx = 0; var HIdx = 0 var inp..

산술평균, 중앙값, 범위를 구하는 것은 모두에게 문제가 없을 것이라고 생각한다. 그래서 최빈값에 대해서만 적어보겠다. 처음엔 계수 정렬을 사용해서 최빈값을 따로 계산하려고 했는데 -> 음수를 고려해서 배열의 인덱스를 다시 설정해야 하는 번거로움이 있었다. 그래서 서치 결과 딕서너리의 활용법을 통해 문제를 풀 수 있었다. 1. 숫자를 입력받을 때 dictionary의 key값에 숫자를 value에 += 1을 해주는 방식으로 dictionary를 세팅한다. let input = Int(readLine()!)! var arr = [Int](repeating: 0, count: input) var dict = [Int: Int]() for i in 0.. 1{ print(mode[1]) }else{ print(..

팩토리얼 함수는 모든 양의 정수와 0에 대해 정의됩니다. 0! 의 값은 무엇이어야 할까요 ? 이는 1보다 크거나 같고 0보다 작거나 같은 모든 정수들의 곱입니다. 그렇지만 그런 정수는 존재하지 않습니다. 그러므로 0! 은 곱셈의 항등원인 1과 같다고 정의합니다. 에 주의해서 문제를 풀어야 합니다. 팩토리얼의 끝이 1이라고 생각해서 문제를 풀었더니 메모리 초과로 문제를 풀지 못했습니다. 0과 1의 메모리에서 어떤 차이가 있는지는 더 찾아봐야 겠습니다. //코드 import Foundation let input = Int(readLine()!)! func factorial(num: Int) -> Int{ if num == 0{ return 1 }else{ return num * factorial(num: n..

중학교 수학을 코드로 푸는 느낌이다. //코드 import Foundation var time = Int(readLine()!)! for i in 0.. r1 + r2{ print("0") }else if (r1 > r2 && d + r2 r1 && d + r1 < r2){ print("0") } else if d == r1 + r2 || (d + r1 == r2) || (d + r2 == r1){ print("1") }else{ print("2") } }

출력 형식의 문제인가 싶었는데 원주율의 문제였습니다. 원주율 -> 3.141592653 로 표현하지 말고 원주율 -> Double.pi 사용하기 //코드 import Foundation let r = Float64(readLine()!)! var u = Double.pi * r * r var t = r * r * 2 print(u) print(t)

재귀함수로 문제를 풀었다. 1. 분홍색 = 주황색1 + 주황색 2 + 파랑색 2. 주황색1 + 주황색 2. 초록색 3. 분홍색 = 초록색 + 파랑색 f(f, r) = f(f, r - 1) + f(f - 1, r) 4. 재귀함수의 endpoint는 (0층 r호) or (f층 1호) (0층 r호)는 r의 값을 가지고 (f층 1호)는 1의 값을 가진다. 코드 let input = Int(readLine()!)! for i in 0.. Int { if r == 1{ return 1 } if f == 0 { return r } return howmany(f: f - 1, r: r) + howmany(f: f, r: r - 1) } 박박대가리가 된 나를 실감 중... 넘 충격이어서 포스팅합니다.. 백준 잡아먹자구,..