Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- Oracle
- Spring Security
- 프로그래머스
- python
- 파이썬
- 스프링 부트 쇼핑몰 프로젝트 with JPA
- JPA
- DB
- springboot
- 데이터
- 시큐리티
- 스프링
- Java
- spring
- 스프링부트
- 리눅스
- backjoon
- 네트워크
- CS지식
- baekjoon
- 백준
- 데이터베이스
- 자바스크립트
- programmers
- postgresql
- 자료구조
- CS
- 플러터
- 자바
- Flutter
Archives
- Today
- Total
Jin's Dev Story
[실버 5] 24313번 알고리즘 수업 - 점근적 표기 1 본문
문제 링크 : https://www.acmicpc.net/problem/24313
문제
오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.
함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.
입력
첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)
다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)
다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)
출력
f(n), c, n0가 O(n) 정의를 만족하면 1, 아니면 0을 출력한다.
입력 1
7 7
8
1
출력 1 : 0
f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다.
입력 2
7 7
8
10
출력 2 : 1
f(n) = 7n + 7, g(n) = n, c = 8, n0 = 10이다. 모든 n ≥ 10에 대하여 7n + 7 ≤ 8n 이므로 O(n) 정의를 만족한다.
코드
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int a1 = scan.nextInt();
int a2 = scan.nextInt();
int c = scan.nextInt();
int n = scan.nextInt();
System.out.println(a1 * n + a2 <= c * n && a1 <= c? 1 : 0);
}
}
'Coding Test > 백준[JAVA]' 카테고리의 다른 글
[실버 5] 11651번 좌표 정렬하기 2 (0) | 2023.09.05 |
---|---|
[실버 5] 11650번 좌표 정렬하기 (0) | 2023.09.05 |
[브론즈 2] 24267번 알고리즘 수업 - 알고리즘의 수행 시간 6 (0) | 2023.08.29 |
[브론즈 3] 24266번 알고리즘 수업 - 알고리즘의 수행 시간 5 (0) | 2023.08.29 |
[브론즈 3] 24265번 알고리즘 수업 - 알고리즘의 수행 시간 4 (0) | 2023.08.29 |