백준 24264 알고리즘 수업 - 알고리즘 수행 시간3 [JAVA]

문제 해석

• 전 포스트와 전전 포스트의 연장선으로 이번에도 수행 횟수와 수행 시간을 출력하는 문제이다.

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

• 위의 코드를 봐보자.
• for문 안에 for문이 있는 것을 확인할 수 있다. (i와 j)
• 이중 반복문인데, 이 반복문이 돌아가는 과정은 i가 1일때 j가 n만큼 반복이 돌고, 다시 i가 2일때 n만큼 반복이 돈다.
• 위의 방식으로 i가 1부터 n만큼 반복한다.
  => 즉, 수행 횟수는 n*n = n^2 이고, 수행 시간은 n의 차수인 2가 된다.
  => 시간 복잡도 : O(n^2)

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어지는데
        //이거의 n*n을 했을때 int로는 overflow가 발생할 수 있다.
        long n = Long.parseLong(br.readLine()); //입력 크기 입력받음 => 이것이 수행 홧수
        br.close();
        System.out.println(n*n);
        System.out.println(2);
    }
}

결과

느낀점

• 자료형 범위부분에 대해 실수해서 한번 틀렸습니다를 받았다.
• 아직 범위값을 구분하는게 미숙한 것 같다. (자료형 실수했다ㅠ)