Tips.
- 정수형 범위를 의식해서 Long Type을 고려하자.
- Buffer
- 장점: 많은 데이터를 빠르 속도에 출력 가능. 따라서 시간이 민감하 문제에서 사용하면 좋다.
- 단점: 중간에 버퍼가 가득 차게 되면 부분 출력을 시도하므로, 중간 계산에 따라서 결과 형식이 달라져야 하는 경우 실패할 가능성이 있음
s[i] = s[i] + a[i], 연속되는 특정 Index 까지의 합을 구할 때
q11660번: 구간 합 구하기2
q10986번: 나머지 합 구하기
2개의 변수 startIndex, endIndex를 조건에 따라 증가시키며 특정 구간의 합을 계산할 때,
조건: 배열의 연속되는 수는 **정렬되어 있어야 함** (시간 복잡도 주의)
투 포인트와 유사한 기법으로 특징은 고정된 구간에서 계산을 하는 것이 특징.
슬라이드 윈도우를 이용해 정렬 구현하기 (Deque)
탐색 범위르 1/2로 줄여나가면서 원하는 요소를 찾는 방법. nlong
조건: 정렬이 되어 있어야 함
dfs: 깊이 우선 탐색
스택, 혹은 재귀를 이용하여 구현
bfs: 너비 우서 탐색
큐를 이용하여 구현
주의:
무한 반복으로 하지 않도로 방문한 노드를 체크해야함
필요한 계산만 빠르게 하는 기법
사이클이 없는 그래프에서 순서를 찾는 방법
- 항상 유일한 값으로 정렬되지 않음, 순서는 여러개일 수 있다는 뜻
- 진입 차수라는 개념이 등장
특정 그래프에서 최단 거리를 구하는 방법
특징
- 방문한 노드를 체크해야함
- 우선순위가 들어가므로 `Priorty Queue` 적용
나머지 성질: (A+B+C)%M = (A%M + B%M + C%M) % M
nC2 (조합, n개 중 2개를 뽑는 경우의 수): (n) * (n - 1) / 2