백준 [단계별로 풀어보기]: (11단계) "시간 복잡도", python

백준 [단계별로 풀어보기]: (11단계) "시간 복잡도", python

 

1. 문제번호 및 정답비율

11단계 시간복잡도 : 문제번호 및 정답 비율

2. 문제별 필요 지식 및 풀이 포인트

O(1) - 상수 시간(Constant Time):
입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우입니다.
예: 배열의 특정 인덱스에 접근하는 경우.

O(log n) - 로그 시간(Logarithmic Time):
입력 크기가 증가함에 따라 실행 시간이 로그 함수처럼 증가하는 경우입니다.
예: 이진 탐색(Binary Search).

O(n) - 선형 시간(Linear Time):
입력 크기에 비례하여 실행 시간이 증가하는 경우입니다.
예: 배열의 모든 요소를 한 번씩 순회하는 경우.

O(n log n) - 선형 로그 시간(Linearithmic Time):
입력 크기에 로그를 곱한 만큼 실행 시간이 증가하는 경우입니다.
예: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort).

O(n^2) - 이차 시간(Quadratic Time):
입력 크기의 제곱에 비례하여 실행 시간이 증가하는 경우입니다.
예: 이중 루프를 사용하는 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort).

O(2^n) - 지수 시간(Exponential Time):
입력 크기에 대해 지수적으로 실행 시간이 증가하는 경우입니다.
예: 피보나치 수열을 재귀적으로 계산하는 경우(단순 재귀).

O(n!) - 계승 시간(Factorial Time):
입력 크기에 대해 계승적으로 실행 시간이 증가하는 경우입니다.
예: 외판원 문제(Traveling Salesman Problem)의 브루트 포스 알고리즘.

3. 문제별 풀이 코드

#알고리즘 수업 - 알고리즘의 수행 시간 1 24262
'''무슨 말이지'''
n = int(input())
count = 1
degree = 0
print(count)
print(degree)


#알고리즘 수업 - 알고리즘의 수행 시간 2 24263
'''for문 1번 = 선형(n)시간복잡도'''
n = int(input())
print(n)
print(1) #n은 1차


#알고리즘 수업 - 알고리즘의 수행 시간 3 24264
'''2중for문 = 이차(n^2)시간복잡도'''
n = int(input())
print(n**2)
print(2)


#알고리즘 수업 - 알고리즘의 수행 시간 4 24265
'''등차수열의 합에 관한 식
    i : i ~ n-1 
    j : i+1 ~ n
n=7, i=1, j=2~7 sum=iXj
    i=2, j=3~7
    i=3, j=4~7
    i=4, j=5~7
    i=5, j=6~7
    i=6, j=7
    i=7, j=8 (x)
n*(n-1) - (1+n-1)*(n-1)/2
'''
n = int(input())
print(int(n*(n-1) - (1+n-1)*(n-1)/2))
print(2)


#알고리즘 수업 - 알고리즘의 수행 시간 5 24266
'''3중for문 = 삼차(n^3)시간복잡도'''
n = int(input())
print(n**3)
print(3)


#알고리즘 수업 - 알고리즘의 수행 시간 6 24267
'''
n=7, i=1,2,3,4,5
     j=2,3,4,5,6
     k=3,4,5,6,7
     즉, 1~n까지 중복 없이 3개 뽑는 것 : nC3 = n!/(n-3)!3!
'''
n = int(input())
print(int((n-2)*(n-1)*n/6))
print(3)


#알고리즘 수업 - 점근적 표기 1 24313
a1, a0 = map(int, input().split())
c = int(input())
n = int(input())

if a1*n + a0 <= c*n and a1 <= c: #a1<=c를 안 해주면, 오류 발생
                                #a1, n, a0, c모두 양수이므로 a1<=c의 관계를 추가해 주면 된다.
    print(1)
else:
    print(0)