[백준] 24265 - 알고리즘 수업 - 알고리즘의 수행시간

| 문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

| 입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

| 출력
첫째 줄에 코드1 의 수행 횟수를 출력한다.
둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

| 예제 입력1
7

| 예제 출력1
21
2

---

| 문제 해석
주어진 MenOfPassion() 알고리즘을 먼저 해석해보자.

1. 입력한 값이 7일 경우,

• 첫번째 for문이 1일때,
  두번째 for문은 (i+1)~n까지 이므로 2~7

• 첫번째 for문이 2일때,
  두번째 for문은 3~7

• 첫번째 for문이 3일때,
  두번째 for문은 4~7 ... 증가하여 마지막으로

• 첫번째 for문이 6일때
  두번째 for문은 7이 된다.

//i=1일때, 
MenOfPassion(A[], n) {
    sum=0;
    for (1 to 6) //
        for (2 to 7) // (j=i+1)
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

2. 그럼 위 코드는 수행 시 아래와 같은 규칙성을 띈다.
   A[1](A[2]+A[3]+...+A[7]) // i=1일때, (n-1)번 수행
   A[2](A[3]+A[4]+...+A[7]) // i=2일때, (n-2)번 수행
   A[3](A[4]+A[5]...+A[7]) // i=2일때, (n-3)번 수행
   ...
   A[6]*A[7] //i=6일때, 1번 수행

sum=(n-1)+(n-2)+(n-3)+...+1
=> 1~(n-1)까지의 합

---

가우스 합의공식

🪄Tip
가우스 합의 공식

• 1~n까지의 합 구하는 공식
  • 1+2+3+...+n = n(n+1)/2

---

3. 문제는 1~(n-1)까지의 합을 구하는 것이므로 합의 공식 n자리에 n-1을 대입하면,
   n*(n-1)/2 식으로 바뀐다.

   해당 식에 입력 7을 하면 수행횟수 21이 나온다.

4. 최고차항의 차수는 for문을 기준으로 정해진다. 문제 MenOfPassion()알고리즘은 이중for문을 사용했으므로 최고차항 차수는 2이다.
   따라서, 2를 그냥 출력해주었다.

package baekjoon_CodingStudy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//시간복잡도
public class A24265 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));

		// 입력 크기
		// int(4byte)는 약 -21억~21억 
		// long(8byte)은 int 보다 무수히 많은 수를 나타내며,
		// 해당 문제에서 input_n의 범위가 1<=input_n<=500,000
		// 제일 큰 데이터 크기를 for문 최고 차수로 계산했을 때 500,000*500,000=25,000,000,000,000
		// int의 범위를 넘어가므로 long형 사용
		long input_n=Integer.parseInt(bf.readLine());
		
		//1~(n-1)까지의 합
		// 가우스 합의 공식 (1~n까지의 합)=n(n+1)/2
		System.out.println(input_n*(input_n-1)/2);
		System.out.println(2); // 최고차항 차수
	}
	

}

| 느낀점
고등학생 때 배웠던 수학 공식들을 다 까먹어서 풀기 너무 까다롭게 느껴졌다..ㅠ 진짜 다시 수학 공부를 해야하나 싶다.
그리고 문제를 풀기전 시간복잡도에 대한 강의를 어느정도 학습하고 풀었더니 전체적으로 내가 변수라던가, 제한 시간을 보면서 어떤 느낌으로 접근해야할지 어느정도 이해가 가서 좋았다.

1. 1초 = 약 1억번의 연산을 한다는 점을 생각하면서 접근하자!

2. 시간 복잡도는 최대 데이터 크기를 기준으로 생각한다!

3. int자료형(4byte,32bit)을 -21억~21억까지만 표현 가능하다. long은 8byte로 그 이상의 갯수(진짜 엄청 많이 표현됨)를 나타낼 수 있으니 코테에선 맘 편하게 long을 쓰도록 하자!
   그래도 문제를 보면서 int가 되고 안되는 이유를 문제마다 알 수 있는 능력은 있는게 좋을 듯 싶다.