정신차려 하프물범 정신차려 하프물범

누적합 (1) (A+B) % M : 구간의 합이 mod인 경우 모듈러 연산 사용 -> 나머지 배열 만들기 예시문제 1. 백준: 10986 "나머지 합" (2) (A+B) = T : 구간의 합이 T인 경우 이중포인터 사용(범위 늘리기용) O(N) 예시문제 1. 백준 1806 부분합 2. 백준 2143 두 배열의 합 # 범위가 큰 경우 O(nlogn) 을 위한 "이분탐색" 사용. bisect 그래프이론 (1) BFS + 3차원배열/큐: 이동할 때마다 현재 상태에 따라 조건이 바뀌는 경우 (이동 좌표 & 현재 상태)를 큐에 같이 저장한다. 예시문제 백준: 2206 "벽 부수고 이동하기" 백준: 1600 말이 되고픈 원숭이 백준: 7569 토마토 트리 - 공통은 재귀함수를 사용하는 것 (1) 입력값으로 트리를 ..

문제 링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 풀이 설명 분류: 누적합 모듈러 합의 개념을 알아야 함. (A + B) % M = ((A % M) + (B % M)) % M 덧셈 뿐 아니라 뺄셈, 곱셈 다 해당됨 구간의 합은 누적합 배열에서의 차와 같다. ex. i~j 까지의 부분합 = sum[j] - sum[i-1] 그러므로, 구간의 합 % M = 0 -> (sum[j] - su..

1. 문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 2. 풀이 분류: 누적합, 투포인터 (10 ≤ N < 10만 )과 S (0 < S ≤ 1억) 이므로 O(n)으로 풀어야지, 이중 반복문으론 아무리 break를 걸어도 시간초과 남. while 문 1개로 돌리기.. 누적합 배열 만들어서도 해봤는데 왜 시간초과 나거나 틀렸다고 하는지 모르겠움🤦‍♀️(아직 풀이중) import sys input = sys.stdin.rea..

1. 문제 링크 https://www.acmicpc.net/problem/1182 2. 풀이 n, s = map(int, input().split()) array = list(map(int, input().split())) cnt = 0 def dfs(idx, sub_sum): global cnt if idx >= n: return sub_sum += array[idx] if sub_sum == s: cnt += 1 dfs(idx + 1, sub_sum) dfs(idx + 1, sub_sum - array[idx]) return dfs(0, 0) print(cnt) 3. 후기 백트래킹 문제 유형은 index의 값을 어떻게 넘기는지에 따라 조합, 순열 등 결과에 영향을 많이 받습니다. 대체로 문제에서 시키..

1. 문제 링크 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 2. 풀이 1) 문제 풀이 각 50만개씩인 명단 2개 in으로 판별(시간 초과, n^2 = 2500억개) -> 이진탐색(풀림, 시간 복잡도 50만 * logN = 50만 * 11 정도) -> set활용(풀림, 제일 간단, O(len(s) + len(t)) = 2 * 50만) 두 집합의 교집합, 합집합, 차집합은 2 * O(n)이 2000만을 넘지 않는다면 set 쓰자. 2) 풀이..

1. 문제 링크 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 2. 풀이 1) 풀이 설명 - 빠른 도착지의 짐 부터 싣는데 최적해라는 것 - 도착지를 기준으로 s-r 까지 가장 많이 실을 수 있는 짐의 양을 재는 것이다. 도착지를 기준으로 오름차순으로 정렬한다. 시작부터 도착지 범위에서 min(남은 트럭 용량(capa), 박스 크기(box)) 을 골라서 가장 작은 값을 넣는 것이다. 이때 박스 크기는 달라지지 않지만, 범위..

1. 문제 링크 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 2. 풀이 1) 풀이 설명 분류: 그리디, 스위핑 스위핑은 정렬 후 다음 데이터만 생각하기 때문에 그리디랑 같이 엮인다. => 이럴 경우 heapq 사용하기 heapq(room 배열)에 끝나는 시간을 담아서, 다음 시작 시간이 heapq에 담긴 0번째(가장 빨리 끝나는 시간)보다 클 경우, 배열에 끝나는 시간을 추가한다. 그렇지 않으면 빼고 추가 2) 풀이 코드 import..