알고리즘/백준

공부 209일차: 백준 24262번 알고리즘 수업 - 알고리즘의 수행 시간 1 자바 java

김발자~ 2023. 2. 24. 21:38
반응형

24262 알고리즘 수업 - 알고리즘의 수행 시간 1

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

 

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1

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

www.acmicpc.net

 

 

 

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

문제

 

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 3439 2711 2501 79.904%

문제

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

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

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

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

입력

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

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

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

예제 입력 1

1

예제 출력 1

1
0

코드1 이 1회 수행되고 알고리즘은 상수 시간이 소요된다.

 

 

 

과정 생각해보기

 

https://gimbalja.tistory.com/371

이 포스팅에 차례차례 정리하는 시간 복잡도에 관한 시리즈이다

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

MenOfPassion은 n이 어떤 숫자냐에 관계없이

i를 한 번만 구한 뒤 배열의 i번째 값을 반환한다

 

1번만 수행하는 메서드인 것이다

 

따라서 무조건 수행 횟수는 1로 고정되며,

수행 횟수를 다항식으로 표현하면 0이 된다

 

빅오 표기법으로 보면 O(1)의 시간 복잡도를 가지는 코드이다

 

 

 

 

정답 인정 코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.io.*;
 
public class Main {
    
    public static void main(String[] args) throws IOException{
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(1+"\n");
        bw.write(0+"");
        bw.flush();
        bw.close();
    }
}
 
 cs

 

 

 

단계별로 풀어보기에 시간 복잡도 탭이 생겼길래.. 나한테 많이 부족한 부분이라 여길 해보려고 한다

첫 시작은 가볍게~

반응형