2021. 1. 8. 22:20ㆍ알고리즘/알고리즘 문제 [medium]
-jlis 문제를 푸는 과정에서의 나의 잘못된 접근방법
1. LISLongest Increasing Sequence
jlis 문제를 풀기전에 알고리즘 문제해결전략 책에 나와있는 LIS의 더 빠른 알고리즘을 구현하였다.
(동적계획법을 사용한 O(n^2)알고리즘과 다르게 O(nlgn)만에 수행된다.)
이 알고리즘은 배열의 각 원소들을 앞에서 부터 탐색해나가며
다음과 같은 배열에 원소들을 집어넣는다.
C[i] = 지금 까지 만든 부분 배열이 갖는 길이 i인 증가 부분 수열 중 최소의 마지막값
C[i]에 원소들을 집어 넣을 때 push()함수가 쓰이는데
이 함수는 삽입정렬과 비슷하며 다음과 같이 작동한다.
C[i] 배열에 x라는 원소를 삽입하고자할 때 이 함수는 i에서 시작하여 1까지 탐색하여
lo < x && x <= hi && (lo + 1 == hi)
lo 와 hi를 구하여 hi에 원소를 삽입한다.
이는 lo길이를 가지는 수열에 x를 덧붙여 hi 길이인 수열을 만드는것이다.
이 때 C[] 배열은 항상 오름차순으로 정렬되며
이는 이진 탐색을 사용할 수 있음을 의미한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
int C[501];
void push(int x, int lo, int hi, int& maxlen)
{
int mid = (lo + hi)/2;
if (C[maxlen - 1] < x)
C[maxlen++] = x;
else if(lo + 1 == hi)
C[hi] = x;
else if (C[mid] >= x)
return push(x, lo, mid, maxlen);
else
return push(x, mid, hi, maxlen);
}
void lis(vector<int> alist, int ai, int& maxlen)
{
if(ai == an) return;
int a = alist[ai];
push(a, 0, maxlen, maxlen);
return lis(alist, ai+1, maxlen);
}
|
cs |
2.JLIS (합친 LIS) 잘못된 풀이.
처음 jlis라는 문제를 봤을때 1lis와 마찬가지로
C[i]같은 배열을 만들자고 생각하였다.
이 C[i]는 lis때 와 마찬가지로 증가 수열 길이 와 마지막 원소값의 정보를 가지고 있고
a와 b의 배열을 합친 lis이다.
하지만 작성한 코드는 시간초과가 되었고, 나는
int cache[ai][bi] 를 생성하여
ai 와 bi 의 단계에서 한번 계산이 수행되었으면 return 하는
동적계획법을 사용한 함수를 다시 구현하였다.
하지만 이 코드는 원활하게 돌아가지 않았고, 문제점이 많았다.
그 문제는 정보가 하나 더 필요했던 것이다.
그 정보는 바로 ai bi 즉
a 배열의 남은 갯수, b 배열의 남은 갯수와 더불어
이 남은 것들을 조합하여 최장이 되었을 떄의 맨 앞의 원소의 정보가
더 필요로 하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
void jlis(int ai, int bi)
{
int &ret = cache[ai][bi];
if(ret != -1) return;
if(ai == an && bi == bn) return;
int a = alist[ai];
int b = blist[bi];
ret = 1;
if(ai != an)
{
jpush(a, 0, jsize);
jlis(ai+1, bi);
}
if(bi != bn)
{
jpush(b, 0, jsize);
jlis(ai, bi + 1);
}
}
|
cs |
이는 a와 b를 각 배열 안의 원소들의 순서는 지키되
a와 b를 섞어 넣은 모든 배열을 생성한뒤
lis를 생성한 모든 배열에 실행하여
가장 긴 것을 찾는것과 동일한 코드일 것이다.
이 코드의 잘못된 수행은 다음과 같다.
j1: a0 a1 a2 b0
b1 b2
j2: a0 a1 b0 a2
b1 b2
코드 순서에 따라 j1 이 만들어 진 다음 j2 배열이 만들어진다
이 때 a2 == b1 이라고 하고 b0 < a2라 하자
j1의 배열은
최대 5의 길이를 가지는 lis를 생성할 수 있다
만약 이 경우
a2까지 쓰였고, b0 이 쓰인 다음 즉 cache[2][0]에 2가 들어가게 된다.
j2가 생성될때
a2가 추가된 이후 cache[2][0] != -1 이 므로 2 + 1 이 되어
결국
a0 a1 b0 a2 b1 b2 라는 증가함수 즉 최대 길이가 6인 수열이 생기게 된다.
하지만 a2 == b1이므로 이것은 거짓된 값이 된다.
그러므로 여기서 이 코드가 문제가 생김을 알 수 가 있었고
이는 원소의 정보가 하나 더 필요함을 의미 한다.
원소의 정보를 하나 더 추가한다는것은
간결한 코드가 되지않고 복잡한 코드가 된다는 것이다.
따라서 이런 접근 방식은 잘못된 접근이라고 생각한다.
복습할 때 이 풀이는 다시 생각해봐야 겠다.
'알고리즘 > 알고리즘 문제 [medium]' 카테고리의 다른 글
[동적 계획법] POLY 폴리오미노 (0) | 2021.01.11 |
---|---|
[동적 계획법] ASYMTILING 비대칭 타일링 (0) | 2021.01.10 |
[동적 계획법, 그래프] JUMPGAME 외발 뛰기 (0) | 2021.01.06 |
[분할 정복] FANMEETING 팬미팅 (0) | 2021.01.05 |
[분할 정복, 스위핑, 스택, 상호 배타적 집합] FENCE 울타리 잘라내기 (0) | 2021.01.04 |