[algorithm] 백준 단계별 문제 풀이 (시간복잡도 2탄)

[algorithm] 백준 단계별 문제 풀이 (시간복잡도 2탄)

 

안녕하세요. 심심한 코딩쟁이입니다.
 
오늘도 저번 시간에 이어 시간복잡도에 대한 문제들로 구성해 보았습니다.
 
파이썬3 를 사용해 문제 풀이를 진행하겠습니다.
 
문제마다 링크를 걸어두었으니 문제를 살펴보시고 문제를 푼 다음에 저와
 
풀이를 비교해 보시는 걸 추천드립니다.

차근차근 풀어봅시다.

 

알고리즘

---

백준 BAEKJOON 24266

 

https://www.acmicpc.net/problem/24266

 

24266번: 알고리즘 수업 - 알고리즘의 수행 시간 5

 

문제 해석

 

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

위 알고리즘의 코드 실행 횟수와 시간복잡도를 구하시오.

 

풀이

 

print(int(input()) ** 3)
print(3)

 

풀이 해석 및 팁

 

코드가 실행되는 횟수는 총 n의 3제곱 번 만큼 실행되므로 주어지는 수에 3제곱을 출력해줍니다.

알고리즘의 시간복잡도는 O(n^3)으로 표기 가능하므로 두 번째 줄에는 3을 출력해줍니다.

---

백준 BAEKJOON 24267

 

https://www.acmicpc.net/problem/24267

 

24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6

 

문제 해석

 

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

위 알고리즘의 코드 실행 횟수와 시간복잡도를 구하는 문제입니다.

 

풀이

 

n = int(input())

print(n * (n-1) * (n-2) // 6)
print(3)

 

풀이 해석 및 팁

 

숫자가 3이 주어질 땐 코드가 1번 수행되고 4가 주어질 땐 4번 수행됩니다.

이처럼 간단한 수를 넣어보면서 수식을 유추해 보면 첫 번째 출력물의 답을 알 수 있게됩니다.

두 번째 출력은 최고차항의 차수는 3이므로 3을 출력합니다.

---

백준 BAEKJOON 24313

 

https://www.acmicpc.net/problem/24313

24313번: 알고리즘 수업 - 점근적 표기 1

 

문제 해석

 

문제에서 주어진 조건들을 그대로 코드로 옮겨서 정의를 만족하는지 판별하는 문제

 

풀이

 

a1, a0 = map(int,input().split())
c = int(input())
n0 = int(input())

print(1 if a1 * n0 + a0 <= c * n0 and a1 <= c else 0)

 

 

풀이 해석 및 팁

 

print 문에서 if else 삼항연산자를 사용합니다.

문제에서 주어진 조건을 만족하는지 판단하기 위해 조건을 if와 else 사이에 작성하고

if 왼쪽에는 조건을 만족할 때의 원하는 출력 값을 적고

else 오른쪽에는 조건을 만족하지 못 할 때 출력할 값을 적으면 됩니다.

---

여기까지 백준 단계별 문제 풀이 시간복잡도 2탄의 풀이였습니다.

 

궁금하신 점이나 도움이 필요하신 부분이 있다면 댓글로 남겨주세요.

 

감사합니다.