Swift224 [Swift][브루트포스] 백준 2143번 (두 배열의 합) 요구능력 해시, 브루트포스 문제풀이 부분합 문제는 연속되서 브루트포스를 하게되면 n^2의 시간복잡도를 가지게되고, 연속되지않게 부분수열과 같은 문제가나오면 2^n의 시간복잡도를 가지게 된다. 이 문제는 연속되기 때문에 편하게 푸려면 브루트포스를 생각해봐야한다. n과 m이 1000이하이므로 n^2을 시도해봐도 괜찮을 것같다. 부분합을 구해주면서 dictionary에 해당 부분합이 나오는 개수를 저장을 해준다. 반으로 쪼개지는 않았지만, 이것도 중간에서 만나기 개념이 살짝 사용되는거같은데..?(아닌가) 그리고 나머지부분합을 구하면서 해시를 이용하여 목표값을 달성하는 개수를 result에 누적해준다. 후기 이전 문제랑 비슷하게 풀리는데.. 이건 연속된 배열이고, 이전 문제는 연속되지 않기때문에 2^n 코드 l.. 2022. 5. 10. [Swift][이분 탐색][중간에서 만나기] 백준 1208번 (부분수열의 합 2) 요구능력 해시와 이분탐색 문제풀이 일반적인 부분수열의 합으로 풀기에는 시간복잡도가 2^40까지 나와서 시간초과가 나오게된다. 2^40이 나오는 이유는 이 문제는 더하기, 더하지않기라는 경우의 수밖에 없기때문이다. 그렇다면 어떻게 풀어야할까? 나는 여기서 중간에서 만나기라는 개념을 처음 접했는데, 대충 이런개념인것같다. 반을 쪼개서 해시로 dictionary에 값들을 저장해주고, 나머지 반에서 값들을 구하면서 (목표값 - 구한값)을 해시에 저장된 값에서 가져오면 중간에서 만나는(?) 개념이 성립되는것 같다. 그리고 문제에서는 크기가 양수인 부분수열이라고 했는데, 아래와 같이 재귀로 sum을 계속 들어가면 하나도 더하지않는 경우(공집합)가 생기므로 s가 0인경우에는 공집합이 생기는 경우를 제거해야한다. 후기.. 2022. 5. 10. [Swift][Two-Pointer] 백준 1644번 (소수의 연속합) 요구능력 투포인터, 에라토스테네스의 체 문제풀이 우선, 에라토스테네스의 체를 이용해서 소수를 판별해주었다. 에라토스테네스의 체를 이용해서 소수를 판별할 때 주의할 점이 있는데, 나는 처음에 에라토스테네스의 체의 배열 개수를 n + 1로 두었다가 97%에서 런타임에러가 나서 최대인 4000001로 설정했다. 그리고 투포인터를 이용해서 end를 증가시키면서 end가 소수인경우 더해줬다. 이렇게 하면 연속적으로 소수만 부분합을 구하게된다. 가장 중요한점은 start가 소수여야된다는 것이다. 자기자신이 소수가아니라면 continue로 넘겨주었다. 후기 투포인터를 살짝 꼬아낸거같다. 코드 import Foundation let n = Int(String(readLine()!))! var arr = Array(re.. 2022. 5. 9. [Swift][Two-Pointer] 백준 1806번 (부분합) 요구능력 투포인터 문제풀이 연속된 수들의 부분합이라는 부분에서 투포인터가 생각났다. 이 문제에서 핵심이라고 느껴지는 부분은 투포인터를 이용해서 부분적인 합을 구했을 때 그 합이 s를 넘어가게 되는 그 시점이 최소길이라는 것이다. 그 이상으로 넘어가버린다면, 최솟값이 될 수 없다. 예를 들어서 1 2 3 2 5라는 수가 있는데, s가 3이다. 그렇다면 start index가 0에있고, end index가 1에 있다면, 우선은 그 때가 최소인 부분이다. 만약 더 탐색하게되서 1 2 3까지 탐색하면 문제의 조건인 s이상은 만족을 하지만, 최소길이는 될 수 없다. 그래서 합이 s보다 작을 때까지만 while문을 돌려준 것이다. 후기 투포인터의 개념을 알고있다면 풀만한 문제인것같다. 코드 import Founda.. 2022. 5. 9. 이전 1 ··· 3 4 5 6 7 8 9 ··· 56 다음