[알고리즘/Python] 시간복잡도와 Big-O, Brute Force 문제

 
 
적기라 판단하여 알고리즘 스터디를 해보려한다.
 
인공지능 공부를 하고 있고 진로를 빅데이터쪽으로 잡았지만
기초 언어 공부와 자료구조를 C++로 하여 언어 선택에 고민이 많이 될 수 밖에 없었다...
 
 
 
 
이론은 cpp로 공부하되, 코딩은 python으로 하기로 했다.
 
 
 
 
 
시간복잡도와 Big-O에 관한 문제풀이 영상이다. 헷갈리는 부분들을 짚어주어 좋은것 같다.
 
*강의영상*: https://www.youtube.com/watch?v=QBZnX_P_dj4

 
 
 
 
 
 
영상에 나오는 코드들을 몇개만 다뤄보자. 영상에선 cpp로 설명한다.
 
 

int sqrt(int n) {
    for (int g = 1; g * g <= n; g++) {
        if (g * g == n) return g;
    }
    return -1;
}

 
 
이 코드에서 반복문은 g * g가 n과 같아질 때까지 실행된다. g * g가 n과 같아지려면, g는 최대 n의 제곱근까지 커질 수 있다.
이렇게 g가 최대 n의 제곱근까지 가는 동안 반복문이 실행되므로, 반복 횟수는 n의 제곱근에 비례하게 된기 때문에 이 함수의 시간복잡도는 O(sqrt(n))이다.
 
 
 
 

int sumDigits(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

 
이 코드에서는 함수의 반복문은 n이 0이 될 때까지 실행된다. 숫자 n이 10진수로 몇 자리인지를 고려하면, 이 함수의 실행 횟수는 n의 자릿수에 비례한다. 예를 들어, n이 1234라면, 4자리 수이므로 반복문은 4번 실행된다. 숫자 n의 자릿수는 log10(n)에 비례하기 때문에
이 함수의 시간복잡도는 O(log n)이다.
 
binary search, 이진 검색 알고리즘과 유사한 형태를 띄고 있는게 특징인듯 하다.
 
 
 
 

int intersection(int[] a, int[] b) {
    mergesort(b);
    int intersect = 0;
    for (int x : a) {
        if (binarySearch(b, x) >= 0) {
            intersect++;
        }
    }
    return intersect;
}

 
이 코드에서 함수는 두 배열 a와 b의 교집합의 크기를 계산하는 함수이다. 
 
 
 
이 코드의 시간복잡도를 해결하기 위해서 먼저 알아야 할 상식으론,
mergesort는 O(n log n) 시간복잡도를 가지고 있고, binarySearch는 O(log n) 시간복잡도를 가지고 있다는 것이다. 알고리즘을 공부하기전에 약간 외워야 할 상식인 것 같다. 아래 표를 통해 알아보자.
 

 
 

 
다른 자료구조의 시간복잡도, 공간복잡도를 알고 싶다면 다른 자료가 많기 때문에 찾아 보는것도 좋은 생각인듯 하다.
 
 
 
 
돌아와서,
먼저 배열 b를 mergesort를 사용해 정렬한다. mergesort의 시간복잡도는 O(m log m)이다. 여기서 m은 배열 b의 크기이다. 다음으로, 배열 a의 각 요소 x에 대해, 배열 b에서 해당 요소를 이진 탐색(binarySearch)으로 찾는다. 배열 a의 크기를 n이라고 하면, 이 루프는 최대 n번 실행된다.
 
binarySearch는 배열 b에서 특정 값을 찾는 동작을 수행한다. 이진 탐색의 시간복잡도는 O(log m)이다. 여기서 m은 배열 b의 크기다. 이를 합치면, 전체 함수의 시간복잡도는 mergesort의 시간복잡도인 O(m log m)와 for 루프의 시간복잡도 O(n log m)의 합이 된다.
 
최종적으로, 이 함수의 전체 시간복잡도는 O(m log m + n log m)이다.
 
 
 
 
 
 
 
 
 
 
 
다음으론 주차별 커리큘럼에 포함되어 있는 백준 문제들을 풀어보자.
 
처음엔 브루트 포스(Brute Force) 문제들을 풀며 구현에 대한 감과 반복적으로 수를 검사하는 과정을 익혀보았다.
 
 
 
 
 
백준 2309번 문제이다 
https://www.acmicpc.net/problem/2309
 

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

예제 입력 1

20
7
23
19
10
15
25
8
13

예제 출력 1

7
8
10
13
19
20
23

 
 
정답 코드:

#백준 2309
def find_seven_dwarfs(dwarfs):
    total_sum = sum(dwarfs)
    for i in range(8):
        for j in range(i+1, 9):
            if total_sum - (dwarfs[i] + dwarfs[j]) == 100:
                dwarf1, dwarf2 = dwarfs[i], dwarfs[j]
                dwarfs.remove(dwarf1)
                dwarfs.remove(dwarf2)
                dwarfs.sort()
                return dwarfs

# 난쟁이들의 키 입력 받기
dwarfs = []
for _ in range(9):
    dwarfs.append(int(input()))

# 일곱 난쟁이를 찾고 출력
seven_dwarfs = find_seven_dwarfs(dwarfs)
for dwarf in seven_dwarfs:
    print(dwarf)

 
 
 
코드와 해결방법을 설명해보겠다.
 
이 문제의 핵심은 9명의 난쟁이 중에서 2명을 제외한 7명의 난쟁이를 선택하여 이들의 키 합이 100이 되도록 하는 것이다.
 

전체 난쟁이 키의 합 계산을 하여 9명의 난쟁이들의 키를 모두 더한다. 예를 들어, 주어진 키가 [20, 7, 23, 19, 10, 15, 25, 8, 13]이라면, 전체 합은 140이다.

 

두 번째 스텝은 두 난쟁이의 키 합 찾는 것이다. 7명의 난쟁이들의 키 합이 100이 되어야 하므로, 전체 키 합에서 100을 뺀 값을 구한다. 예를 들어, 140 - 100 = 40이 된다. 이 값이 두 난쟁이의 키 합이 되어야 한다. 즉, 이 합을 만드는 두 명의 난쟁이를 찾아야 한다.

 

그리고 두 난쟁이 제거해야 한다. 9명의 난쟁이 중에서 합이 40이 되는 두 난쟁이를 찾는다. 이 두 난쟁이를 리스트에서 제거하면, 남은 7명의 난쟁이의 키 합이 100이 된다. 마지막으로 남은 7명의 난쟁이들의 키를 오름차순 정렬 및 출력한다.

 
 
 
 

 

 

 

 

 

백준 1065번 문제이다 

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

 

문제

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 

입력

첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다.

 

 

 

예제 입출력은 사이트에 들어가 참고 바란다.. (너무 많음)
 

 

정답 코드:

#백준 1065
def is_hansu(number):
    digits = list(map(int, str(number)))  # 숫자의 각 자리를 리스트로 변환
    if len(digits) <= 2:
        return True  # 숫자의 자릿수가 2 이하일 경우 무조건 한수
    difference = digits[1] - digits[0]  # 첫 번째 차이 계산
    for i in range(1, len(digits) - 1):
        if digits[i + 1] - digits[i] != difference:
            return False  # 차이가 일정하지 않으면 한수가 아님
    return True  # 모든 차이가 일정하면 한수

def count_hansu(N):
    count = 0
    for i in range(1, N + 1):
        if is_hansu(i):
            count += 1
    return count

# 입력값 받기
N = int(input())

# 결과 출력
print(count_hansu(N))

 

 

 

코드와 해결방법을 설명해보겠다.

 

이 문제에서는 주어진 자연수 N보다 작거나 같은 한수의 개수를 찾는 것이 목표이다. "한수"는 각 자릿수가 등차수열을 이루는 수를 말한다. 이 문제를 해결하기 위해서는 주어진 수가 한수인지 여부를 판단하는 함수와, 1부터 N까지의 모든 숫자에 대해 이 함수를 적용하여 한수의 개수를 세는 작업이 필요한듯 하다.

 

가장 먼저 코드상에서 한수를 정의 할 수 있는 매커니즘을 만들필요가 있어보인다.

 

한수의 정의:

• 각 자릿수가 등차수열을 이루는 수.
• 예를 들어, 숫자 123은 1, 2, 3의 차이가 각각 1로 일정하므로 한수.
• 135는 1, 3, 5의 차이가 2로 일정하므로 한수.
• 132는 1, 3, 2의 차이가 일정하지 않으므로 한수가 아님.

한수를 정의했으니, 판별 함수를 만들어보자. 숫자를 문자열로 변환하여 각 자리의 차이를 계산하고 이 차이가 일정한지 확인했다. 판별이 되었으니 1 부터 N까지의 모든 숫자에 대해 한수인지 확인하고 그 수를 세어 출력한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
 
 
...1주차에는 시간복잡도와 Big-O 표기법 + 브루트 포스 기본 문제들을 풀어보았다.