어 그냥 이 파트의 컨셉 자체를 모르겠어서 되게 당황스러움
시간복잡도라는 개념 자체를 알아야 하는 건가?
24262
내 생각에는 시간복잡도 개념을 알고 => 문제에서 제시된 알고리즘이 O(1)인 알고리즘을 알아채느냐가 중요한 것 같음
내 풀이 (근데 이 문제는 풀이가 중요한 건 아닌 듯)
input() #입력 받음
print(1) #무조건 한 번
print(0) #상수 알고리즘이라 무조건 0정리
설계
출력 조건
1. 첫째 줄에 코드1 의 수행 횟수를 출력한다.
=> 여기에선 단순하게 알고리즘을 읽고 수행 횟수가 무조건 1임만 알 수 있으면 되는 것 같음
- 둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.
=> 수행 횟수를 다항식으로 나타내서 최고차항의 차수를 출력
=> 이 문장 자체가 시간 복잡도를 의미하는 거라고 유추하는 게 의도인 듯?
나의 생각(?)
코드 자체에서 무엇을 얻어갈 수 있는 문제는 아닌 듯
1. 시간 복잡도 개념 정리
- 입력 크기 N과 관계없이 항상 같은 횟수 연산 => O(1)
- 다항식 f(N) = 1 * N^0 => 최고 차항 차수 0
- 알고리즘을 보고 시간 복잡도를 평가해 보는 경험
- 코드의 구조(반복문, 재귀, 호출 등)을 보고
- 얼마나 많은 연산이 실행되는지
- 입력 크기에 어떻게 비례하는지
파악하는 훈련
몰랐거나 틀린 포인트 정리 "시간 복잡도"
시간 복잡도
- 시간 복잡도를 고려한다
=> 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가? - 효율적인 알고리즘 구현
=> 입력밧이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 - 주로 시간 복잡도는 빅-오 표기법 사용
Big-O 표기법
- 상한 접근
- 최악의 경우 고려 => 프로그램 실행할 때 소요되는 최악의 시간 고려
Big-O 표기법 종류
=> 대충 그래프 떠올리면 다 이해됨
1.O(1)
O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가해도 시간이 늘어나지 않음
입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있음
2.O(n)
O(n)는 선형 복잡도(linear complexity)라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가
3.O(logn)
O(logn)는 로그 복잡도(logarithmic complexity)라고 하며, Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도
- BST(Binary Search Tree)가 여기에 해당
4.O(n^2)
O(n^2)는 2차 복잡도(quadratic complexity)라고 하며, 입력값이 증가함에 따라 시간이 n의 제곱수 비율로 증가하는 것을 의미
5.O(2^n)
O(2^n)은 기하급수적 복잡도(constant complexity)라고 하며, Big-O 표기법 중 가장 느린 시간 복잡도
- 재귀로 구현하는 피보나치 수열이 대표적인 O(2^n) 시간 복잡도 알고리즘
def fibonacci(n): if n <= 1: return 1 return fibonacci(n-1) + fibonnacci(n-2)만약에 내가 피보나치가 저 시간 복잡도인 걸 모른다고 하면 어떻게 추측할까?
- 재귀 형식의 알고리즘을 만났다
- 그 함수가 자기 자신을 어떻게 호출하는지 보고
- 그것을 기반으로 재귀식을 세우는 것
재귀식 세우는 원칙
1. 호출 횟수: 함수 F(n) 안에서 몇 번 호출하는가?
2. 서브 문제 크기: 호출할 떄 넘겨 주는 인자의 크기는 어떻게 변하는가?
3. 추가 오버헤드: 그 호출 외에 내부에서 하는 반복문/연산량은?
=> **T(n) = (호출 횟수) X T(서브 크기) + O(오버헤드)
예시
| 알고리즘 | 재귀 호출 구조 | 재귀식 | 해(시간 복잡도) |
|---|---|---|---|
팩토리얼 (fact(n)) | 1번 호출, 크기 n-1 | T(n) = T(n-1) + O(1) | O(n) |
이분 탐색 (binary_search) | 1번 호출, 크기 n/2 | T(n) = T(n/2) + O(1) | O(log n) |
| 퀵정렬 (평균) | 2번 호출, 크기 약 n/2 | T(n) = 2 T(n/2) + O(n) | O(n log n) |
피보나치 재귀 (fib(n)) | 2번 호출, 크기 n-1와 n-2 | T(n) = T(n-1) + T(n-2) + O(1) | O(φ^n) |
24263
내 풀이
n = int(input())
print(n)
print(1)24264
내 풀이
n = int(input())
print(n*n)
print(2)24265
내 풀이
n = int(input())
print(n*(n-1)//2)
print(2)
정리
- 손으로 풀자
- 등차 수열 공식
- 제1항부터 제n항까지의 합 S
- 첫째항 a, 마지막항 l
- S = n(a + l) / 2
24266
내 풀이
n = int(input())
print(n**3)
print(3)
정리
몰랐거나 틀린 포인트 정리
파이썬에서 제곱근 표시
n**n = n * n * n 24267 (보류)
내 풀이
정리
설계
- 삼중루프문을 분리해서 각각 몇 번 반복하는지 구하기
- i 구간 : (n-2)번 반복
- j 구간 : (n - i - 1)번 반복
- k 반복 : (n - j)번 반복
- 근데 이걸 가지고 수행 횟수를 어떻게 구해야 하는 건지 모르겠음
- 어차피 차수는 n만 따지면 되니까 3일 것임
=> 조합이라고 설명하는데 조합으로 넘어가는 부분이 이해가 안 됨
몰랐거나 틀린 포인트 정리
24313
내 풀이
a1, a0 = map(int, input().split())
c = int(input())
n0 = int(input())
def f(n) :
return a1*n + a0
def g(n) :
return c*n
flag = 1
for i in range(n0, 100):
if f(i) > g(i):
flag = 0
break
print(flag)정리
설계
-a₁, a₀, c, n₀ 값을 입력받는다.
-f(n) = a₁·n + a₀로 정의
-g(n)은 문제에서 O(n)이라고 했으니 g(n) = c·n이라고 설정
-f(n) ≤ g(n)을 만족하는지 검사
-모든 n ≥ n₀에 대해 만족해야 하므로, 특정 범위 (n0 ~ n0+100)까지 검사하고 조건을 만족하면 1, 아니면 0 출력몰랐거나 틀린 포인트 정리
1. def로 f(n), g(n) 정의
- 처음에 그냥 f(n) = a1 * n + a0이라고 작성
2. g(n) = c * n으로 정의한 이유
- 문제에서 O(n)에 부합하는지를 묻고 있으므로
- 만약 문제에서 O(n^2)를 물었으면 g(n) = c*n^2로 정의했을 것
- 빅오 표기법에서 상수항은 무시할 수 있어서 그냥 c*n 해도 ㄱㅊ
3. 모든 n >= n0에 대해 성립하는지
- 모든 n에 대한 검사는 불가능
=> ** 귀납적으로 n0부터 약 100개의 값만 테스트 **
4. flag 변수 사용
- flag = 1를 놓고, 틀리면 flag = 0으로 바꿈
- 조건을 만족하는지 검사하고 빠르게 탈출할 때 자주 쓰이는 패턴임