알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자
세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다.
내용이 이상하다면 지적해주시면 감사하겠습니다. 👍
안녕하세요 이 포스팅은 알고리즘 2일차로 시간복잡도 응용편입니다.
시간복잡도 줄이는 방법들
문제 풀이와 함께 아래와 같은 기법들을 배웠습니다.
어디선가 한번쯤 사용해보았지만 ‘의식'하고 풀지는 않았던거 같습니다.
문제를 푸는데 많은 도움이 되는 기법들이니 꼭 숙지하고 가야합니다.
투 포인터 기법
투 포인터 기법이란 ?
투 포인터는 연속되고 가변적인 부분 배열을 이용하여 특정 조건을 일치시키는 알고리즘 입니다.
즉, 정렬되어 있을 때 사용할 수 있습니다.
투 포인터 언제 사용하는데?
2-포인터 기법은 보통 두 데이터를 비교하여 될 때 많이 사용됩니다.
예를 들면 병합 정렬에서 분해 후에 다시 합체할 때 2-포인터 기법을 이용하여 두 숫자를 비교하게 됩니다.
두 포인터는 보통 다음과 같은 변수를 선언해서 사용하게 됩니다.
변수명은 원하시는데로 하시면 되지만 대게 left, right, start ,end, p1, p2, … 이런 식으로 이용합니다.
int left, right;
int start, end;
int p1, p2;
선언된 두 변수는 배열의 특정한 인덱스를 가리키게 됩니다.
int[] A = new int[5];
int left = 0;
int right = A.length() - 1;
위와 같이 A의 첫번째 인덱스와 끝 인덱스를 넣어주는 식으로 사용하게 됩니다.
물론, 문제가 원하는 조건 마다 다를 수 있습니다.
두 배열을 비교하는 경우도 존재합니다.
int[] A = new int[5];
int[] B = new int[5];
int p1 = 0;
int p2 = 0;
int tenCount = 0;
while (true) {
// ...
if (A[p1] + B[p2] == 10) {
tenCount++;
}
// ...
}
추천 문제
투 포인터와 관련된 백준 문제입니다.
2003번: 수들의 합 2
첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.
www.acmicpc.net
슬라이딩 윈도우
슬라이딩 윈도우와 투 포인터의 차이
슬라이딩 윈도우는 투-포인터 기법과 비슷하지만 분명한 차이점이 있습니다.
슬라이딩 윈도우는 부분적인 배열이 고정적입니다.
슬라이딩 윈도우 장점
덕분에 투-포인터와 다르게 두 개의 변수를 선언하여 인덱스를 둘 다 신경쓰면서 움직이지 않아도 되어 간단합니다.
때문에 마치 창문을 미는 것과 같은 느낌이기에 “슬라이딩 윈도우"라고 불리는 기법입니다.
슬라이딩 윈도우 코드 느낌
- 자신 + 3까지의 범위 슬라이딩
int[] arr = new int[10000000];
int myRange = 3;
int myLoc = 0;
int sum = 0;
for (int i = 0; i <= myRange; i++) {
sum += arr[i];
}
while (myLoc + myRange < 10000000) {
sum -= arr[myLoc];
sum += arr[++myLoc + myRange];
}
추천 문제
밑에는 슬라이딩 윈도우 응용 문제입니다.
10025번: 게으른 백곰
첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다.
www.acmicpc.net
파라메트릭 서치
파라메트릭 서치란 ?
이분 탐색으로 특정한 숫자를 찾는 방법과 동일하며 결정 문제입니다.
코드를 보는게 더 이해하기 쉬울 수 있을거 같습니다.
다음과 같이 구현하고 문제에 맞는 조건들을 더 추가해주는 식으로 풀이하게 됩니다.
이분 탐색과 같이 밑 코드 만으로는 $O(logN)$이므로 매우 효율적인 방법 중 하나 입니다.
int start = 0; int end = arr.length();
while (true) {
int mid = (strat + end) / 2;
if () {
} else if () {
// start = mid + 1;
} else {
// end = mid - 1;
}
}
위 코드를 보면 여러 조건들이 나오게 됨을 알 수 있습니다.
일반적으로
SUM > TARGET : start = mid +1
SUM == TARGET : 종료
SUM < TARGET : start = mid - 1;
start > end : 종료
start == end : 조건에 맞게 구현
이런 조건들이 나오게 됩니다.
무조건 적으로 위와 같이 나오는 것을 표현한 것이 아닌 단지 예제일 뿐입니다.
단지 이러한 조건들이 나올 수 있고 mid값을 포함해줄지 말지, 범위 설정, 탈출 조건도 잘 설정해주어야 합니다.
아래는 이와 관련된 문제입니다.
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
부분배열
시간복잡도를 어떤 식으로 줄일 수 있을지 생각하게 해주는 문제를 접했습니다.
2143번: 두 배열의 합
첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그
www.acmicpc.net
크게 어려운 문제는 아니지만 어떤 식으로 반복문을 줄일 수 있을지 고민 할 수 있고 또한 조건들이 있어 구현력을 키우는데 큰 도움이 됐습니다.
알고리즘 2일차 [시간복잡도] 배운 것 정리
1) int형, long형
long형으로 사용하는 편이 좋습니다.
long형이 int보다 범위가 넓어 비효율적일 것 같지만 프로그램을 돌리면서 큰 문제는 되지 않습니다.
대부분 문제는 잘 구현 했는데 변수 타입 때문에 틀린적이 많아 이번 기회에 확실히 알게 되었습니다.
2) 투-포인터, 슬라이딩 윈도우, 파라메틱 서치
배열 등 어떠한 데이터를 순차적으로 비교해야 할 때 위와 같은 3가지 방법들을 잘 사용해야 합니다.
비효율적인 문제를 어떤 ‘기법'으로 풀지 판단해야 합니다.
또한 그와 관련된 조건들을 잘 구현하는 연습을 해야합니다.
그리고 범위 조건과 탈출 조건을 별개로 선언해서 가독성을 늘려야 합니다.
3) List<Object>와 Object[]
어떠한 조건에 만족하는지 데이터 더미를 뒤져야할 때 어떤 방식으로 하는게 더 좋을 지 생각해보아야 합니다.
저같은 경우 List 타입으로 선언하여 forEach로 돌리지만
배열로 선언하여 해당 인덱스를 찾아서 “한 번"에 확인 할 수 있는 방법도 있음에 유의해야 합니다.
댓글