Java/코딩테스트

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

다아빈 2025. 4. 22. 21:58
728x90
반응형

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

문제 접근

저는 바보라 처음에 문제를 이해하는 것이 어렵더라구요..?

문제에 나와 있는 MenOfPassion 함수를 작성해야하는지 헷갈렸습니다.

 

알고보니 입력값을 MenOfPassion에 넣는다 생각하고 알고리즘의 수행 횟수와 시간복잡도(빅오표기법)의 최고차항 차수를 구하면 되는 것이었습니다. 

따라서 이 문제를 풀기 위해서는 빅오 표기법에 대해서 알아야 합니다!

 

먼저, 빅오 표기법(Big-O Notation)이란 알고리즘의 시간 복잡도나 공간 복잡도를 표현할 때 사용되는 수학적 표기입니다. 즉, 입력 크기(n)가 커질 때 알고리즘의 실행 시간이나 메모리 사용량이 얼마나 증가하는지를 표현하는 방법입니다. 알고리즘의 정확한 실행 시간은 컴퓨터의 성능이나 언어에 따라서 달라지는데, 이러한 성능을 상대적으로 비교하기 위해 빅오 표기법을 사용합니다.

 

주요 빅오 표기법의 종류는 다음과 같습니다.

  • O(1), 상수 시간
    입력 데이터의 크기와 상관없이 항상 일정한 시간을 갖으며, 대표적인 예시로는 변수 접근, 배열 인덱싱이 있습니다.
  • O(log n), 로그 시간
    입력 데이터의 크기가 커질수록 처리 시간이 줄어들며, 대표적인 예시로는 이진 탐색이 있습니다.
  • O(n), 선형 시간
    입력 데이터의 크기에 비례해 처리 시간이 증가하며, 대표적인 예시로는 for문 순회, 선형 검색이 있습니다.
  • O(n log n), 선형 로그 시간
    선형 + 로그 단계가 섞인 구조로, 입력 데이터의 크기가 커질수록 처리 시간이 로그의 배만큼 증가합니다. 대표적인 예시로는 병합 정렬, 퀵정렬 평균이 있습니다.
  • O(n²), 이차 시간
    입력 데이터의 크기가 커질수록 처리 시간이 입력의 제곱만큼 증가하며, 대표적인 예시로 버블정렬, 선택정렬, 이중 for문이 있습니다.
  • O(2ⁿ), 지수 시간
    입력이 늘어날 때마다 처리 시간이 2배씩 증가하며, 대표적인 예시로 재귀적 조합이 있습니다.
시간 복잡도의 성능을 비교하면 다음과 같습니다.
O(1) < O(log n) < O(n log n) < O(n²) < O(2ⁿ)
즉, 오른쪽으로 갈수록 효율성이 떨어집니다!

 

빅오 표기법에서 가장 영향을 미치는 것은 n의 단위입니다. 

식 빅오 표기법
2 O(1)
2n + 20 O(n)
5n² O(n²)

위의 표와 같이 계수와 뒤에 연산은 무시되며, n만 생각합니다.

 

이제 MesOfPassion 알고리즘을 살펴보겠습니다.

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

배열과 n이 주어지면 i를 구한 후, A[i]를 반환하는 코드입니다. 이 문제는 반복문이 없으며 단순히 입력값을 받으면 배열의 값을 찾아오는 것이 끝입니다. 따라서 입력값이 아무리 커져도 코드를 1번만 수행한다는 뜻이죠!

예를 들어, n의 값이 1이어도 1번만 실행되고, n의 값이 100이어도 1번만 실행됩니다. 이를 빅오 표기법으로 표현하면 O(1)으로 표현할 수 있는 것이죠!

 

따라서 실행 횟수를 출력하는 첫 번째 줄은 1이 됩니다.

두 번째 줄에는 n의 차수를 구해야 하는데 상수(O(1))는 n이 없으니 0을 출력합니다.

전체 코드

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

        String input = br.readLine();

        bw.write("1\n0");

        bw.close();
    }
}

 

저는 위와 같이 코드를 짰지만, 입력값에 아무리 커져도 무조건 동일한 출력값을 갖기 때문에, 입력받는 부분은 없어도 된다고 하네요!! 

 

읽어주셔서 감사합니다!

728x90
반응형