[백준] 24262

문제

 

 

분석

시간복잡도에 대해서는 아래와같이 알고 있었다.

빅-오메가 : 최적의(Best Case) 인 경우의 연산 횟수를 나타낸 표기법

빅-세타 : 보통일때(Average Case) 인 경우의 연산 횟수를 나타낸 표기법

빅-오 : 최악일때(Worst Case) 인 경우의 연산 횟수를 나타낸 표기법

 

일반적으로 알고리즘 문제풀이는 빅오계산법을 사용한다고 알고있다.

다만.....

해당 문제를 여러번 읽어봐도 어떻게 풀어야하는지 감이 오지 않았다...

 

독해력 부족으로 검색을 해보니 문제의 알고리즘에서 걸리는 시간복잡도의 차수 O(n) 에 들어가는 "n" 을 구하는 문제였다.

 

 

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

해당 알고리즘에서는 반복을 진행하지 않고, 바로 결과를 전달해주기때문에 실행 횟수는 1번이고,

시간 복잡도는 0이다.

 

해당 알고리즘을 반복하더라도, 시간 복잡도는 "상수" 이기 때문에 변하지 않는다...

(추가 설명은 refs 란으로..)

 

 

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        sc.close();

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

    }
}

 

 

 

느낀점

평소에 시간 복잡도를 읽으면서 어떻게 계산해야하는지를 명확하게 인지하고있지 못하였었다.

해당 문제를 접하면서 이해해나가며 코드를 작성하니까 조금은 더 깊게 알아가는 것 같다.

 

 

 

 

refs

https://kevinitcoding.tistory.com/entry/%EB%B0%B1%EC%A4%80Python-24262%EB%B2%88-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%98-%EC%88%98%ED%96%89-%EC%8B%9C%EA%B0%84-1-%EB%AC%B8%EC%A0%9C

[백준/Python] 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 문제

 

빅오 표기법

https://blog.chulgil.me/algorithm/

알고리즘의 시간 복잡도와 Big-O 쉽게 이해하기