[Java] 백준 24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1

문제 url:
알고리즘 수업 - 알고리즘의 수행 시간 1

문제:

풀이하기 앞서, 시간 복잡도를 잘 모른다면 아래 링크를 통해 이해하면 좀 낫다.
[알고리즘] 시간 복잡도? 그게 무엇인지 알아보자

🤔 문제 알아보기

문제에서 MenOfPassion 알고리즘에 대해 설명하는 것이 보인다.
분명 n과 A배열을 넣으면 i 에는 n/2의 몫에 해당하는 배열 인덱스 값을 초기화,
A배열을 리턴한다.. 등등으로 적혀 있는데

여기서 중요한 건, n에 무슨 값을 넣어도 해당 값은 단 한 단계만 처리할 것이다.
n이 2든 3이든 하나의 값만 출력할 것인데,
이는 곧 O(1)의 시간 복잡도를 가진다.

코드로 짜지말고 해당 MenOfPassion을 머리로 풀어보면 이해가 될 것이다.

필자는 해당 문제를 이해하기 전에 풀다가 시간 복잡도를 공부한 다음 다시 문제를 풀어 이해가 조금 된 상태였다. 하지만 처음엔 이해가 어려웠는데 이를 먼저 설명하면

• 첫쨰 줄에 코드 1의 수행 횟수를 출력한다.
  • 수행 횟수에서 힌트를 얻을 수 있다. 위의 링크 글을 읽으면 시간 복잡도는 연산횟수와 관련이 있는 것을 알 수 있는데,
  • 이 말은 즉, 시간 복잡도를 구해라 라고 이해할 수 있다.

• 둘째 줄에 코드1의 수행 횟수를 .. 최고차항의 차수를 출력한다. 단 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력
  • 처음에 이 말을 듣고, if문을 쓰고 막 그랬다. 그리고 나중에 이해한 바
  • 빅오 표기법은 계수와 최고차항을 제외한 나머지 항은 무시하는 특징이 존재
    즉 O(N), O(N ^ m)인지를 묻는 질문이라 이해했다.

🐱‍👤 실제 코드

import java.io.*;

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

        int n = Integer.parseInt(br.readLine()); // 굳이 변수에 넣지 않아도 풀린다.

        System.out.println(1);
        System.out.println(0);


    }

}