누적합4 [Swift] 백준 16139 : 인간-컴퓨터 상호작용 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 풀이 과정 누저합 원리만 알고 있다면 크게 어려움이 없는 문제이다. 단, 1) 질문의 수가 최대 200,000번이기 때문에 매번 반복되지 않도록 한번 누적합을 구한 알파벳의 누적합은 저장해놓고 사용하도록 하고 2) 물어보지 않을 특정 문자가 있을 수 있기 때문에 특정 문자가 등장하는지에 대한 누적합을 처음 물어볼 때에만 누적합을 구하도록 한다. 먼.. 2023. 12. 18. [Swift] 백준 3020 : 개똥벌레 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 방식 나는 처음에는 1...n 구간마다 장애물로 막혀 있는 곳의 위치들을 높이별로 빈도수 배열을 구한 뒤 배열 전체를 검색하면서 최솟값과 그 개수를 구하는 방식으로 구현했었다. // 완전 탐색으로 구현할 경우 O(n^2) 복잡도 for i in 0.. 2023. 12. 14. [Swift] 백준 10986 : 나머지 합 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 단순히 누적합 알고리즘으로 접근할 경우에 아래와 같이 시작점과 끝점의 모든 경우의 수를 확인해야 하므로 시간 복잡도가 O(n^2) for i in 0...n-1 { for j in i+1...n { count += ( psum[j]-psum[i] ) % 1 == 0 ? 1 : 0 { { 하지만 여기서 누적합 psum[0]...psum[n] 중 나머지.. 2023. 12. 13. [Swift] 백준 2559 : 수열 # 풀이 전형적인 누적합 문제. 아래와 같이 psum[0] = 0 부터 시작하는 prefix sum을 먼저 구한 뒤 var psum = [Int](repeating: 0, count: n + 1) for i in 1...n { psum[i] = psum[i-1] + inputArr[i-1] } psum[m] - psum[0] 부터 psum[n] - psum[n-m] 중 가장 작은 값을 찾는다. var max = Int.min; for i in m...n { if( max < psum[i] - psum[i-m] ) { max = psum[i] - psum[i-m] } } 소스코드 import Foundation let input = readLine()!.split(separator: " ").map{Int.. 2023. 12. 7. 이전 1 다음
