[Swift][BruteForce] 백준 1182번 (부분수열의 합)
요구능력 : 백트래킹 코드설명 : 이 문제에서 생각해봐야할건 "어떻게해야 모든 부분수열을 구할 수 있을까?" 이다. -7, -3, -2, 5, 8 이 있을 때 {-7} {-7, -3} {-7, -3, -2} {-7, -3, -2, 5} {-7, -3, -2, 5, 8} {-7, -2} ... 그리고 -3부터 시작해서 위처럼 쭉 나열하고 -2부터, 5부터, 8부터... 이렇게 구하면 모든 부분수열을 구할 수 있다. 부분수열을 구하는건 그럼 백트래킹으로 해야겠다. 백트래킹으로 모든 경우의수를 다 검사해보는것이다. 백트래킹을 하면서 우리가 구해야하는건 부분수열의 합이다. 그래서 sum에 입력받은 연속된수열의 합을 백트래킹하면서 구했고, 그 합이 구하고자하는 값인 s와 같아졌을 때 그리고 문제에서 크기가 양수인..
2022. 1. 11.
[Swift][DP] 백준 15989번 (1, 2, 3 더하기 4)
요구능력 : DP점화식 코드설명 : 기존의 1,2,3더하기와 비슷한데 "합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다."라는 조건이 붙었다. 1,2,3더하기 문제는 특징이 있는데 1과 2와 3을 기준점으로 세우고 해당하는 수가나오도록 더하는것이다. 예를들어서 4가있으면 3 + 1 2 + 2 1 + 3 이런식으로 기준을 1,2,3으로 두고 문제를 풀면된다. 중복된 수의 순서가 안나오려면 1,2,3을 기준으로 두고 뒤에 나오는수가 작거나같으면된다. 예를들어 4가있으면 1뒤에는 1보다 작거나 같은 수가 나와야한다. 1 + 1 + 1 + 1 2뒤에는 2보다 작거나 같은 수가 나와야한다. 2 + 2, 2 + 1 + 1 3뒤에는 3보다 작거나 같은 수가 나와야한다. 3 + 1 이렇게 4가지 나오게된다...
2021. 12. 18.