[개념 학습 및 정리] 문제 해결

1. 문제 해결 절차

• 문제 이해
• 문제를 해결하는 알고리즘 개발
• 알고리즘이 문제를 해결함을 증명
• 알고리즘이 제한시간(시간복잡도) 내에 동작함을 확인
• 알고리즘을 코드로 작성
• 한번에 통과

 

 

 

2. 연속 부분 최대합

연속된 부분을 선택하여 그 합이 최대가 되게 하는 방법

1

2

-4

5

3

-2

9

10

 

문제 이해) 문제 해결을 위해 고려해야 하는 모든 경우를 파악 (탐색 공간)

• 연속된 구간이 1개씩, 2개씩 3개씩 ... 7개씩 전부 28개의 경우가 된다.
• n개가 있을 경우, n(n+1)/2
• O(n^2)

 

알고리즘 개발) 가능한 모든 경우를 다 해보고 그 중 최대가 되는 것을 선택

• start와 end로 구간 지정
• 코드 레벨로 구현

 

for(int start = 0; start < n; start++) -- O(n)
  for(int end = start; end < n; end++) -- O(n)
    (start + end의 합)                  -- O(n)
    (최댓값 판단)                         -- O(1)

알고리즘 증명) 가능한 모든 경우를 고려했기에 문제 해결

알고리즘 시간복잡도) 효율성 확인

• O(n^3)의 시간 복잡도가 성립하는 경우
• O(n^3)의 시간 복잡도가 성립하지 못하는 경우

 

시간복잡도가 성립할 경우)

코드 작성)

package org.example;

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] data = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0;
        int end = 0;

        int max = 0;
        for(start = 0; start < n; start++) {
            for(end = start; end < n; end++) {
                int sum = 0;

                for(int k = start; k <= end; k++) {
                    sum += data[k];
                }

                if(max < sum) max = sum;
            }
        }

        bw.write(max + "");

        bw.flush();
        bw.close();
        br.close();
    }

}
/*
예제 입력
10
2 3 -7 5 8 -3 5 7 -10 8

예제 출력
22
 */

시간복잡도가 성립하지 못할 경우)

• 시간복잡도를 줄일 수 있는 방안 모색 (start부터 end까지의 합을 구하는 코드)
• sum의 배열에 첫 번째 수부터 x번째 수까지 더한 값을 저장

 

for(int start = 0; start < n; start++) -- O(n)
  for(int end = start; end < n; end++) -- O(n)
    (start + end의 합)                  -- O(n) -- 수정 필요
    (최댓값 판단)                         -- O(1)

start 부터 end 꺄지의 합을 구하는 방법

최종적으로, 구간의 합은 O(1)의 시간이 걸림을 확인할 수 있다. 따라서 O(n^3)이 O(n^2)으로 줄일 수 있다.

코드 작성)

package org.example;

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] data = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            data[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0;
        int end = 0;

        int[] sum = new int[n];
        sum[0] = data[0];
        for(int i= 1; i < n; i++) {
            sum[i] = sum[i-1] + data[i];
        }

        int max = 0;
        for(start = 0; start < n; start++) {
            for(end = start; end < n; end++) {

                int temp = 0;
                if(start == 0) temp = sum[end];
                else temp = sum[end] - sum[start-1];

                if(max < temp) max = temp;
            }
        }

        bw.write(max + "");

        bw.flush();
        bw.close();
        br.close();
    }

}
/*
예제 입력
10
2 3 -7 5 8 -3 5 7 -10 8

예제 출력
22
 */

 

 

 

3. 문제 해결 접근법

• 완전 탐색법 (Brute-Force) : 모든 경우의 수를 확인하는 방법
• 분할 정복법 (Divide & Conquer) : 합병 정렬 처럼 각각의 작은 문제로 나눠 해결하고 합치는 방법
• 동적 계획법 (Dynamic Programming) : 작은 문제를 모두 해결하는 것으로 전체 문제를 해결하는 방법
• 탐욕적 기법 (Greedy Approach) : 전체의 경우를 고려하지 않아도 된다는 증명을 하면 일부 경우의 수만 사용하여 해결하는 방법
• 그래프 알고리즘 (Graph Algorithm) : 최단거리 찾기