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

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

 

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

차근차근 풀어봅시다.

 

알고리즘

---

백준 BAEKJOON 24262

 

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

 

24262번: 알고리즘 수업 - 알고리즘의 수행 시간 1

 

문제 해석

 

수행 시간에 대한 지식이 없다면 처음 문제를 읽어보았을 때 아리송한 부분이 존재했을 겁니다.

코드의 수행 시간과 알고리즘의 수행 시간은 다른 개념입니다.

코드의 수행 시간은 코드가 정말로 몇번 실행되는가를 의미하고

알고리즘의 수행 시간은 주어지는 수를 n이라고 했을 때 n에 비례하는가를 살펴봐야합니다.

예를 들어

for i in range(n):
    print(i)

이러한 알고리즘이 존재한다면 알고리즘의 수행시간은 n입니다. n에 비례하여 수행되기때문입니다. 

for i in range(n):
    for j in range(n):
        print(list[i][j])

그렇다면 위와 같은 알고리즘의 수행시간은 얼마일까요?

n * n 크기의 리스트를 출력하기 때문에 n^2가 되겠습니다.

문제에서 원하는 수행 횟수를 다항식으로 나타냈을 때 최고차항의 차수는 2가 되겠습니다.

이제 문제를 풀어보시죠

 

풀이 

 

print(1)
print(0)

 

풀이 해석 및 팁

 

어떤 수가 주어지든 코드의 수행 횟수는 1회이고 다항식으로 나타내도 1이므로 최고차항은 0이 됩니다.

---

백준 BAEKJOON 24263

 

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

 

24263번: 알고리즘 수업 - 알고리즘의 수행 시간 2

 

문제 해석

 

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

위 알고리즘의 코드 수행 횟수와 시간 복잡도를 구해야한다.

풀이 

 

print(input())
print(1)

 

풀이 해석 및 팁

 

주어지는 숫자 n에 따라 코드 수행 횟수가 정해지고 시간복잡도는 n에 비례하므로

빅O 표기법으로 나타내면 O(n)라고 할 수 있다.

---

백준 BAEKJOON 24264

 

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

 

24264번: 알고리즘 수업 - 알고리즘의 수행 시간 3

 

문제 해석

 

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

위 알고리즘의 코드 수행 시간과 시간 복잡도를 생각해봅시다.

for 반복문의 중첩을 유심히 보시기바랍니다.

 

풀이

 

print(int(input()) ** 2)
print(2)

 

풀이 해석 및 팁

 

for 문이 중첩되어 있으므로 주어진 숫자 n의 제곱번 만큼 코드가 수행됩니다.

시간 복잡는 O(n^2)가 되므로 최고차항은 2가 되겠습니다.

---

백준 BAEKJOON 24265

 

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

 

24265번: 알고리즘 수업 - 알고리즘의 수행 시간 4

 

문제 해석

 

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

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

 

풀이 

 

n = int(input())
print(int(n*(n-1)/2))
print(2)

 

풀이 해석 및 팁

 

코드 실행 횟수는 직접 간단한 수를 넣어보면서 생각해보면 코드와 같은 수식을 구할 수 있을 겁니다.

다항식으로 표현해 보았을 때 최고 차항이 2이므로 2를 출력해주면 되겠습니다.

---

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

 

다음 2탄에서 나머지 문제들에 대한 풀이도 다루도록 하겠습니다.

 

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

 

감사합니다.