[백준] 시간복잡도

서론

---

이번에는 시간복잡도를 풀어보았다.

카테고리만 보고 제한시간안에 문제를 풀어야 하나 라고 생각했는데 그건 아니었다.

시간복잡도에 대해 고민해보는 문제이지만, 구현 문제는 아니었던 것 같다

---

24262 : 알고리즘 수업 - 알고리즘의 수행 시간 1

---

문제

---

https://www.acmicpc.net/problem/24262

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1

---

해설

---

import java.io.*;

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());

        StringBuilder sb = new StringBuilder();
        sb.append(1).append("\n").append(0);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

의사코드를 보면, n에 상관없이 수행 횟수는 1번으로 상수항만 존재하므로, 최고차항의 수는 0이다. O(1)

---

24263 : 알고리즘 수업 - 알고리즘의 수행 시간 2

---

문제

---

https://www.acmicpc.net/problem/24263 

24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2

---

해설

---

import java.io.*;

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());

        StringBuilder sb = new StringBuilder();

        sb.append(n).append("\n").append(1);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

의사 코드의 반복문만을 구현해보자면 아래와 같다.

for(int i = 1; i <= n; i++){
	sum += A[i];
}

해당 반복문은 입력받은 n번만큼 수행하게 된다. 

따라서 최고차항의 수는 1이다. O(n)

---

24264 : 알고리즘 수업 - 알고리즘의 수행 시간 3

---

문제

---

https://www.acmicpc.net/problem/24264 

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3

---

해설

---

import java.io.*;

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());

        StringBuilder sb = new StringBuilder();

        sb.append((long) Math.pow(n, 2)).append("\n").append(2);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

의사코드

for (int i = 1; i <= n; i++){
	for (int j = 1; j <= n; j++){
 		sum += A[i] * A[j];   
    }
}

의사코드를 보면 n * n번 수행하게 된다. 따라서 최고차항의 차수는 2이다. O(n^2)

---

24265 : 알고리즘 수업 - 알고리즘의 수행 시간 4

---

문제

---

https://www.acmicpc.net/problem/24265 

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

---

해설

---

import java.io.*;

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));

        long n = Long.parseLong(br.readLine());

        StringBuilder sb = new StringBuilder();

        sb.append((n * (n-1)) / 2).append("\n").append(2);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

의사코드

for (int i = 1; i <= n-1; i++){
	for (int j = i + 1; j <= n; j++){
 		sum += A[i] * A[j];   
    }
}

해당 코드의 수행 횟수를 확인해보면 아래와 같다.

i = 1	i = 2	i = 3	i = 4	i = 5	i = 6
j = 2~7 (6)	j = 3~7 (5)	j = 4~7 (4)	j = 5~7 (3)	j = 6~7 (2)	j = 7 (1)

위의 표를 보면 n-1부터 1까지의 합만큼의 수행횟수를 가지는 것을 볼 수 있으며,

이를 수식으로 나타내면 오른쪽과 같다는 것을 확인할 수 있다. (n^2-n)
따라서 최고차항의 차수는 2이다, O(n^2)

---

24266 : 알고리즘 수업 - 알고리즘의 수행 시간 5

---

문제

---

https://www.acmicpc.net/problem/24266 

24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5

---

해설

---

import java.io.*;

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));

        long n = Long.parseLong(br.readLine());

        StringBuilder sb = new StringBuilder();

        //sb.append((long) Math.pow(n,3)).append("\n").append(3);
        sb.append(n*n*n).append("\n").append(3);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

의사코드

for (int i = 1; i <= n; i++){
	for (int j = 1; j <= n; j++){
		for (int k = 1 k <= n; k++){
        		sum += A[i] * A[j] * A[k];   
    	}
    }
}

n * n * n의 수행 횟수를 가지는 것을 볼 수 있으며, 최고차항의 차수는 3이다.

하지만, Math.pow(n, 3)을 사용하려 했지만, Double형을 사용하기 때문에 부동소수점 오차가 생겨서 오답이 나오는 경우를 확인할 수 있었다.

그래서 해당 부분을 주석처리하고 그냥 n*n*n을 하였따.

---

24267 : 알고리즘 수업 - 알고리즘의 수행 시간 6

---

문제

---

https://www.acmicpc.net/problem/24267 

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

---

해설

---

import java.io.*;

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));

        long n = Long.parseLong(br.readLine());

        StringBuilder sb = new StringBuilder();

        sb.append(n*(n-1)*(n-2) / 6).append("\n").append(3);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

의사코드

for (int i=1; i <= n-2; i++){
	for (int j = i+1; j <= n-1; j++){
		for (int k = j+1; k <= n; k++){
        		sum += A[i] * A[j] * A[k];   
    	}
    }
}

이 문제도 표를 통해 횟수를 나타내보면 아래와 같다.

i=1	i=2	i=3	i=4	i=5
j=2~6 (5)	j=3~6 (4)	j=4~6 (3)	j=5~6 (2)	j=6 (1)
j = 2, k = 3~7 (5)	j = 3, k = 4~7 (4)	j = 4, k = 5~7 (3)	j = 5, k = 6~7 (2)	j = 6, k = 7 (1)
j = 3, k = 4~7 (4)	j = 4, k = 5~7 (3)	j = 5, k = 6~7 (2)	j = 6, k = 7 (1)
j = 4, k = 5~7 (3)	j = 5, k = 6~7 (2)	j = 6, k = 7 (1)
j = 5, k = 6~7 (2)	j = 6, k = 7 (1)
j = 6, k = 7 (1)
5+4+3+2+1	4+3+2+1	3+2+1	2+1	1

위와 같은 수행 횟수를 확인할 수 있으며, 이는 아래와 같은 수식으로 만들어볼 수 있다.

 

2중 시그마를 통해 해당 공식을 풀어볼 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

즉, 수행 횟수의 공식은 바로 위의 공식이며, 최고 차항의 차수는 3임을 알 수 있다.

---

24313 : 알고리즘 수업 - 점근적 표기 1

---

문제

---

https://www.acmicpc.net/problem/24313 

24313번: 알고리즘 수업 - 점근적 표기 1

---

해설

---

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a[] = new int[2];
        a[0] = Integer.parseInt(st.nextToken());
        a[1] = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        boolean check = (a[0] * n + a[1]) <= c * n;
        if(check && c >= a[0]){
            bw.write(String.valueOf(1));
        }
        else {
            bw.write(String.valueOf(0));
        }
        bw.flush();
        bw.close();
    }
}

간단하게 생각해서, 공식에 입력받은 수들을 대입하여 만족하면 1, 아니면 0을 출력하도록 하였다.

하지만 처음에 제출하였을 때는 틀렸다는 결과를 받았다.

a[0] = 7

a[1] = -1

c = 6

1

이러한 경우 7 * 1 - 1 <= 6*1 이므로 수식을 만족하지만, n이 계속해서 증가하더라도 이를 만족할 수 있어야 한다.

하지만 n=2일 경우, 7 * 2 - 1 <=  6 * 2의 수식은 성립하지 않음을 알 수 있다.

따라서 이를 확인해주는 코드를 추가하여야 했다.

---

결론

---

오랜만에 수학 공식을 생각하고, 24267번 문제 해설 처럼 시그마를 풀어보며, 정답을 맞췄을 때 너무 재미있었다.

수학문제가 역시 집중하기에는 너무 좋은 것 같다~

---