[BAEKJOON]24266 알고리즘 수업 - 알고리즘의 수행 시간 5

문제 요약

• 알고리즘 분류: 구현, 큰 정수 다루기
• 난이도: Bronze3
• 문제내용:
  • 수행 횟수와 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력 해라
• 사이트 주소: https://www.acmicpc.net/problem/24266

문제풀이

이 문제는 단순한 시간 복잡도 분석 문제입다.

1. 시간 복잡도 분석

문제에서 요구하는 것은 다음과 같다.:

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

즉, O(n^a)에서 a가 몇인지만 알면 풀 수 있다.

알고리즘을 분석해보면:

• 3중 for문이 각각 n번씩 반복
• 시간 복잡도: O(n³)
• 최고차항의 차수: 3

2. 핵심 문제점

문제의 핵심은 첫째 줄 출력입니다. n의 범위가 1 ≤ n ≤ 500,000이므로, n³은 매우 큰 수가 될 수 있습니다. 따라서 Java, JavaScript 같은 언어에서 기본 정수 타입으로는 표현할 수 없다.

구현 포인트

주의사항

• n의 범위가 1 ≤ n ≤ 500,000이므로, n³은 매우 큰 수가 될 수 있습니다.
• 500,000³ = 125,000,000,000,000,000,000 (약 1.25 × 10¹⁷)
• 따라서 일반적인 int나 long 타입으로는 표현할 수 없어 BigInteger나 BigInt를 사용해야 한다.

 

Code

Python

 파이썬은 데이터 범위에 대한 제약이 크게 없어서 그냥 작성 하면 된다.

n = int(input())
print(n ** 3)
print(3)

 

Java

자바는  long으로 해결이 안되서 BigInteger class를 사용 해야 한다.

BigInteger에는 pow() 사용하면 제곱을 사용 할수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;


public class Main {


	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
		BigInteger n = new BigInteger(br.readLine());
		System.out.println(n.pow(3));
		System.out.println(3);

	}
}

Javascript

자바스크립트는 일반 정수 타입으로는 범위가 초과 되서 BigInt를 사용 해야한다. 주위 점은 연산은 그대로 해도 되지만 연산 할 숫자 뒤에 n을 붙어야 한다. ex) 3 -> 3n

var input = require('fs').readFileSync("/dev/stdin", "utf-8").trim().split("\n");

const n = BigInt(input[0]);

console.log(n ** 3n + "\n3");

마무리

알고리즘의 효율성을 분석하는 것은 프로그래밍에서 매우 중요한 기술이다. 특히 입력 크기가 커질수록 시간 복잡도의 차이가 실행 시간에 미치는 영향이 크기 때문에, 이런 분석 능력을 기르는 것이 중요하다.