백준177 Swift) 백준 11726번 (2 x n타일링) 요구능력 : 규칙을 통해 DP를 사용해야할지를 아느냐 코드설명 : 2 x 2 ~ 2 x 4까지 그림을 그려보자. 규칙을 찾아보면 아래와 같다. 보다시피 위의 세로막대기가 왼쪽에 1개 있는건 n-1개가 나온다. 아래의 가로막대기가 왼쪽에 2개 있는건 n-2개가 나온다. 여기서 DP를 해야겠다는 생각이 어떻게 나오냐? 1. 문제가 연속적이다. 2. 중복되는 부분문제가 있다. ( f(5)를 구하려면 f(4)와 f(3)을 구해야하는데 f(4)를 구하려면 f(3)을 또 구해야하는 것을 말한다.) 후기 : 규칙을 찾고 DP개념만 알고있으면 풀 수 있는 문제 let n = Int(readLine()!)! var dp = Array(repeating: 0, count: 1001) dp[1] = 1 dp[2] = 2 f.. 2021. 8. 28. Swift) 백준 1463번 (1로 만들기) 요구능력 : dp의 개념을 알고있느냐 코드설명 : 다이나믹 프로그래밍의 바텀업 방식은 작은문제부터 차근차근 답을 도출해 나아가는 방식이다. 그리고 배열에 저장하는 이유는 다이나믹프로그래밍의 기본 원리중 하나인 중복되는 부분문제를 해결하기 위함이다. 2~n 까지의 모든 경우를 배열에 저장해놓고 사용함으로써 중복되는 부분문제를 해결하고 실행시간을 어마어마하게 줄일 수 있다. 만약, 10까지가는 최단경로를 구하고자 하면 2~10까지의 최단경로를 모두 구하는것이다. 1. DP방식중 Bottom-up방식으로 접근하기 위해 우선 배열을 선언하였다. 2. 3가지의 조건 중 -1을 하는 조건에는 특정조건이 없으므로 우선적으로 처리해준다. 3. 현재의 수 i가 2 or 3으로 나누어 떨어지면 2 or 3으로 나눠주는데,.. 2021. 8. 28. Swift) 백준 1476번 (날짜 계산) 요구능력 : 전체경우의 수를 따질수 있느냐 코드설명 : 전체적인 연수를 세기위한 변수 i 각각 E, S, M 변수 지구, 태양, 달의 조건을 넣어서 만족하면 1을 넣어준다. 입력받은것과 E, S, M 이 같으면 반복문을 중단한다. 후기 : 문제에 나와있는 조건만 충족하면 평이한 문제 let arr = readLine()!.split(separator: " ").map{Int($0)!} var i = 1 var E = 1 var S = 1 var M = 1 while true { if E > 15 { E = 1 } if S > 28 { S = 1 } if M > 19 { M = 1 } if E == arr[0] && S == arr[1] && M == arr[2] { break } i += 1 E += 1.. 2021. 8. 26. Swift) 백준 2309번 (일곱 난쟁이) 요구능력 : 브루트포스 알고리즘을 알고있느냐 코드설명 : result배열을 만들어서 랜덤으로 선택한 값을 가지고 있지 않으면 result배열에 저장해주고 sum에 더해준다. 그렇게 7번 더해주고 while문을 빠져나왔을 때 sum이 100이면 바깥의 while문을 탈출해준다. 왜 랜덤으로 풀었냐고 물으면 키가 모두 다르고 정답이 여러가지인 경우에는 아무거나 출력가능했기 때문이다. 후기 : 랜덤으로 풀어버렸다. var result: [Int] = [] var arr: [Int] = [] for _ in 1...9 { arr.append(Int(readLine()!)!) } while true{ var sum = 0 var j = 0 result = Array(repeating: 0, count: 7) wh.. 2021. 8. 26. 이전 1 ··· 31 32 33 34 35 36 37 ··· 45 다음
