분류 전체보기266 [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. [Swift][프로그래머스][BFS] 거리두기 확인하기 요구능력 BFS 문제풀이 문제에서 대놓고 BFS를 쓰라고 하고있다. 행렬로 이루어져있고 응시자와 응시자의 맨하탄거리가 2이하로 이루어져있고 중간에 파티션이 없다면 거리두기를 지키지 않은것으로 간주된다. 1) 맨하탄거리 구하는 함수 func manhatan(_ r1: Int, _ c1: Int, _ r2: Int, _ c2: Int) -> Bool{ if abs(r1 - r2) + abs(c1 - c2) Bool{ var queue = [(Int, Int)]()//좌표, 거리 var visited = Array(repeating: Array(repeating: false, count: 5), count: 5) queue.append((x, y)) visited[x][y] = true while !queue.. 2022. 5. 4. 이전 1 ··· 8 9 10 11 12 13 14 ··· 67 다음
