1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 👾접근 주어지는 수의 범위가 절댓값이 1,000,000,000 이하인 정수인 점 과 정수 중복도 가능하다는 점을 알고 있어야 한다..(이거 고려못하고 중복없는 양의 정수로 풀어서 헤맸다) 즉, 체크되는 수를 제외한 두 수의 합이 체크되는 수와 같기만 하면 된다. 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn) 이 되어야 함 => 정렬과 투포인터 사용해보기 리스트를 정렬한 후 좋은 수 여부를 체크할 위치를 지정하고 해당 인덱스를 제외하고 양쪽 끝 인덱스로 s 와 ..
🏷️CS/Algorithm
1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 🐱🏍접근 입력받은 자연수 리스트를 오름차순으로 정렬한 후 양끝에서부터 포인터를 지정하여 두 수의 합을 구하는 방식으로 구현 시작 인덱스(s)는 리스트의 0번 인덱스에서부터 종료 인덱스(e)는 리스트의 마지막 (N-1)번 인덱스에서부터 시작 투 포인터 이동원칙 - lst[s] + lst[e] > M : e -= 1 - lst[s] + lst[e] < M : s += 1 - lst[s] + lst[e] == M : cnt +=1;..
투포인터 2개의 포인터로 알고리즘의 시간 복잡도를 최적화할 수 있음 2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 🐬접근 N의 최댓값이 10,000,000 이므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한시간 2초를 초과함. 따라서 O(n)의 시간 복잡도 알고리즘을 써야함. 연속된 자연수이므로 투포인터를 활용해 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현할 수 있음 시작 인덱스(s)를 1씩 증가시킨다(오른쪽으로 1칸 움직인다) = 연속된 자연수에서 왼쪽 ..
구간합 다른 문제 구간합1 구간합2 10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 🐲접근 (A+B) % C = ((A%C)+(B%C))%C 해당 구간 합의 나머지 연산 값 = 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값 합 배열 S 가 있다고 할 때, S[i] % M == S[j]%M 이면 (S[i] + S[j])%M == 0 : 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[i] 와 S[j] 가 같은 (i,j) 쌍을 찾으..
구간 합 첫 게시글로 이동하기 11660 👻접근 질의 개수 (M) 이 최대 100,000 이기 때문에 질의마다 합을 구하면 시간 복잡도가 올라가므로 구간 합 배열을 이용해야함. 2차원 구간 합 배열 D[X][Y] 정의 D[X][Y] = 원본 배열의 (0,0) 부터 (X,Y) 까지의 사각형 영역 안에 있는 수의 합 풀이 질의 X1,Y1, X2,Y2 에 대한 답을 구간 합으로 구하는 방법 D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1-1][Y1-1] 코드 import sys input = sys.stdin.readline N,M = map(int,input().split()) A = [[0] * (N+1)] # 2차원 원본 배열 D = [[0] * (N+1) for _ in..
