[ 알고리즘 ] 문제풀이 방법
@ 무엇인가?
수업을 듣던중 내용 정리
알고리즘은 문제 해결을 위한 절차
1. 문제를 정확히 이해해야 한다. ( 예제를 통해서 이해하려고 하지 말고 문제를 천천히 읽는 습관!! )
2. 문제를 해결하는 알고리즘을 개발한다. - 알고리즘 설계
> 모든 경우 생각
> 어떻게 줄일수 있지? 꼭 전부 고려해야 하나?
3. 알고리즘이 문제를 해결한다는 것을 증명한다. ( 수학적으로 -> 뭐 이렇게 하면 되지 않나요? 이렇게 말하면 안된다. )
4. 알고리즘이 제한시간 내에 동작한다는 것을 보인다. ( 시간 복잡도를 물어본다. )
5. 알고리즘을 코드로 작성한다.
6. 제출 후 만점을 받고 매우 기뻐한다.
코딩 도중에 다시 풀어보고 왔다 갔다 한다면 3,4 번이 문제가 되서 그렇다.
@ 연속 부분 최대합
연속된 부분을 선택하여, 그 합이 최대가 되게 하라.
> 문제 해결 철차를 통해서 풀기
1. 문제 이해
1, 2, -4, 5, 3, -2, 9, 10 ( 단, 1<= n <= 100 )
2. 탐색 공간 파악하는 것이 가장 먼저 !!!! > 모든 범위 생각!!!!!
> 문제 해결을 위해 고려해야 하는 모든 경우 ( 가장 기본 )
> 면접에서 탐색 공간이 이정도라고 꼭 이야기 해야 한다. ( 모든 경우가 얼만큼 되는가? )
- 우리가 고려해야 하는 경우의 개수는? 연속한 부분을 다 고려했을때 문제가 해결된다.
숫자 1개 고려 (0,0),(1,1) ... (7,7) :8개
숫자 2개 고려 (0,1),(1,2)... (5,7) :7개
...
숫자 7개 (0,7) :1개
우리가 고려 해야 할것 28개 !!!
> (면접) 왜 그러냐: 연속으로 선택하는게 있는데 1개 2개 선택하는 경우가 8개 7개,,, 1개니까 총 합이 28이 된다.
> N(N+1) / 2
> O(N^2) 이 된다.
탐색 공간 파악 완료 > 그럼 모든 경우를 다 고려해 보자!!!!! 그럼 무조건 답이 나온다.
> 가능한 모든 경우를 다 해보고 그 중 최대가 되는 것을 고르자 !
해결: 모든 구간을 다 더해보자
## 우리의 솔류션
## 정확성
3. 우리 알고리즘이 잘 돌아가는지 수학적으로 증명해야 한다.
가능한 모든 경우를 고려했으므로 정답을 찾을 수 있음
> 빈틈 없다.
방법:
start 연속부분 시작부분
end 연속부분 끝부분
for start = 0 to n > O(n)
for end = start to n > O(n)
start ~ end 합 > O(n)
최대값 판단 > O(1)
총: O(n^3) 이 된다.
@ 구현
4. 수도코드를 먼저 작성 해라
for start = 0 to n
for end = start to n
mySum = getSum(data, start, end)
if( mySum > myMax
myMax = mySum;public class SumFindMax {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] data = new int[n];
for(int i=0;i<n;i++) {
data[i]=scanner.nextInt();
}
int myMax = -9127320;
for(int start =0;start<n;start++) {
for(int end =start;end<n;end++) {
int mySum =0;
for(int k=start;k<=end;k++) {
mySum += data[k];
}
if(mySum > myMax) {
myMax = mySum;
}
}
}
System.out.println(myMax);
}
}## 시간 복잡도 줄이기
> 우선 모든 경우 다 생각!!
> 대부분의 문제들이 모든 경우를 고려하는 문제는 아니다. 어떻게든 줄여야 한다.
> 이것이 최선인가?
합을 미리 구하면 Sum 구하는 O(N) 이 O(1) 이 된다.
public class SumFindMax2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] data = new int[n];
int[] sum = new int[n];
for(int i=0;i<n;i++) {
data[i]=scanner.nextInt();
}
sum[0] = data[0];
for(int i=1;i<n ;i++) {
sum[i]= sum[i-1]+data[i];
}
int myMax = -9127320;
for(int start =0;start<n;start++) {
for(int end =start;end<n;end++) {
int mySum =0;
if(start ==0 ) mySum = sum[end];
else mySum = sum[end] - sum[start-1];
if(mySum > myMax) {
myMax = mySum;
}
}
}
System.out.println(myMax);
}
}@ 정리
모든 경우를 고려함으로써 문제를 해결하자
> 완전 탐색 ( Brute-Force Search )
장점: 확실하며, 알고리즘이 비교적 단순하다. 비교적 풀이를 떠올리기가 쉽다.
단점: 느리다.
> 조금 씩 개선 하면서 문제를 해결
> 탐색 공간을 파악하는 것이 문제 해결에서 가장 중요함
> 모든 경우를 고려해서 시간 내에 해결이 된다면 OK
> 시간 내에 해결이 되지 않으면 경우의 수를 줄이는 시도를 함
> 완탐 실패시
분할 : 나누고 합치기
동적: 작은거 해결하고 서서히 큰 문제 해결하기
탐욕적 기법: 좋아 보이는 몇개만 보고 나머지는 볼 필요 없다.
그래프 알고리즘: 최단 거리 찾기
