본문 바로가기
728x90

시간복잡도

[백준][파이썬] 26313 알고리즘 수업 - 점근적 표기 1
백준 문제풀이 2023. 2. 24. [백준][파이썬] 26313 알고리즘 수업 - 점근적 표기 1 1.문제 분석 알고리즘의 시간복잡도를 점근적 표기를 이용해 알아본다. 첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100) 다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100) 다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100) 2. 기본 아이디어 일차함수의 성질을 이용하여 두 일차함수를 비교한다. 3.문제 풀이 주어진 O-표기법(빅-오)는 아래와 같다. O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다} 이때, 함수 f(n) = a1n + a0, g(n) = n이다. 문제의 조건을 보면 함수 g(n)은 늘 우상향하는 일차함수다. (n >= n0 범위이며, n0는 양수..
[백준][파이썬] 24267 알고리즘 수업 - 알고리즘의 수행 시간 6
백준 문제풀이 2023. 2. 24. [백준][파이썬] 24267 알고리즘 수업 - 알고리즘의 수행 시간 6 1.문제 분석 알고리즘의 수행횟수와, 이것을 다항식으로 나타냈을 때의 최고차항의 차수 출력 2. 기본 아이디어 코드1의 수행 시간은 n세제곱에 비례한다. 3.문제 풀이 주어진 알고리즘 MenOfPassion(A[], n) { sum
백준 문제풀이 2023. 2. 24. [백준][파이썬] 24266 알고리즘 수업 - 알고리즘의 수행 시간 5 1.문제 분석 알고리즘의 수행횟수와, 이것을 다항식으로 나타냈을 때의 최고차항의 차수 출력 2. 기본 아이디어 코드1의 수행시간은 n세제곱에 비례한다. 3.문제 풀이 주어진 알고리즘 MenOfPassion(A[], n) { sum
[백준][파이썬] 24265 알고리즘 수업 - 알고리즘의 수행 시간 4
백준 문제풀이 2023. 2. 24. [백준][파이썬] 24265 알고리즘 수업 - 알고리즘의 수행 시간 4 1.문제 분석 알고리즘의 수행횟수와, 이것을 다항식으로 나타냈을 때의 최고차항의 차수 출력 2. 기본 아이디어 코드1의 수행 시간은 n제곱에 비례한다. 3.문제 풀이 주어진 알고리즘 MenOfPassion(A[], n) { sum
백준 문제풀이 2022. 8. 25. [백준][파이썬] 1920 수 찾기 1.문제 분석 주어진 수가 배열에 있는지 확인하는 문제 시간초과에 주의해야 한다. 2. 기본 아이디어 시간 초과를 방지하기 위해 sys를 import한다. 3.문제 풀이 처음 문제를 풀었을 때에는 lst의 자료형을 list로 만들었다. 하지만 시간초과가 났다. 검색을 통해 알아본 결과 if in을 사용할 시 set 자료형의 시간복잡도는 O(1)이고 list 자료형의 시간복잡도는 O(N)인 것을 알게 되었다. 따라서 set 자료형을 사용해서 문제를 풀었다. import sys n = int(sys.stdin.readline()) lst = set(sys.stdin.readline().split()) m = int(sys.stdin.readline()) is_in = sys.stdin.readline().s..
728x90

티스토리툴바