파이썬 Python | 알고리즘 | 백준 일곱 난쟁이

⭕ 파이썬 Python | 알고리즘 | 백준 일곱 난쟁이

➡️ 문제링크

• https://www.acmicpc.net/problem/2309

 

➡️ 문제 탐색하기

난쟁이의 수가 9명으로, input의 크기가 매우 작습니다. 7명을 선택하는 모든 경우의 수를 탐색할 수 있을지 생각 해봅시다. 이렇게 모든 경우를 탐색하는 것을 완전 탐색이라고 부르며, 완전탐색은 보통 input의 크기가 작을 때  사용 할 수 있습니다. 9명의 난쟁이 중 2명의 난쟁이를 선택하는 모든 경우의 수는 9 * 8로, 총 72가지입니다. 한 가지 경우에 대해 정답인지 판단하기 위해서는 난쟁이의 키의 합을 구하는 단순 연산만 필요합니다. 따라서 2초의 시간 제한안에 아주 넉넉하게 완전 탐색이 가능합니다. 코딩테스트에서는 1억번의 연산이 대략 1초 정도 걸린다고 생각하면 쉽습니다.

---

정렬

• 7명의 키의 합이 100을 만족하는지 확인한 이후에 정렬을 해도 좋지만, 정답으로 선택된 7명의 키를 다시 배열에 새롭게 넣고 정렬을 해야 해서 조금 번거롭습니다. 결과를 오름차순으로 출력해야 하므로 데이터를 먼저 오름차순으로 정렬해야 한다. 
  
  1. 파이썬 내장 정렬 라이브러리를 써서 간편하게 구현할 수 있다. (+ 신뢰성과 검증된 성능)  > 시간복잡도를 체크한다.
  2. 직접 구현할 수 있는 정렬 알고리즘을 찾아본다. > 각 정렬간 시각복잡도를 비교한다.
• 정답으로 선택된 7명의 키를 다시 배열에 새롭게 넣고 정렬을 해야 해서 조금 번거롭습니다.

---

9명 중 합이 100이 되는 7명 찾기

• 9명의 총합을 구하고, 여기서 100을 만들기 위해 제외해야 할 2명의 합을 찾아야 한다.
  
  1. for 문을 사용하여 2명의 합을 구하는 것은 비교적 덜 중첩될 것이다. (7번의 합을 구하는 것에 비해서...)
  2. 조합을 구하기 위해 파이썬 내장 조합 라이브러리를 사용한다.

 

➡️ 코드 설계하기

정렬

1. list.sort(): O(NlogN), timesort 알고리즘을 기반으로 한다. 퀵 정렬보다 효율적일 수 있다. 크기 9의 배열(9명의 난쟁이)을 정렬하기 때문에 1초의 시간제한안에 충분히 가능한 연산이다.
2. 선택 정렬: O(N^2), 무작위 데이터에서 가장 작은 데이터를 맨 앞으로 이동한다. 비효율적이지만 가장 작은 데이터를 찾는 경우 유용할 수 있다.
3. 삽입 정렬: O(N^2), 거의 정렬된 데이터에서 데이터를 한 칸씩 이동시키며 자신보다 작은 데이터를 만나면 교환한다.
4. 퀵 정렬(가장 많이 사용): O(N log⁡N), 기준 데이터를 설정하고 이를 기준으로 큰 데이터와 작은 데이터의 위치를 교환해 리스트를 분할하는 과정을 반복한다.
5. 계수 정렬: O(N+K), 데이터 크기 범위가 제한된 정수 형태인 경우

---

9명 중 합이 100이 되는 7명 찾기

1. 이중 for문: O(N^2), 구현이 간단하지만 이중 for문으로써 비효율적일 수 있다고 생각했다...
2. itertools 모듈의 combination 함수: 더 효율적인 방법으로 문제를 해결할 수 있을까 고민하다가, 구글링을 통해 combination 함수를 사용하는 것이 더 나은 방법일 수 있다는 결론에 도달했다.

 

➡️ 시도 회차 수정 사항 (Optional)

1회차 (이중 for문 )

• 시간 88ms

# 9개의 숫자를 저장할 배열을 선언
numbers = []

# 사용자로부터 9개의 숫자를 입력받아 배열에 추가
for _ in range(9):
    numbers.append(int(input()))

# 배열을 오름차순으로 정렬
numbers.sort()

# 배열의 모든 숫자의 합을 계산
total_sum = sum(numbers)

# 두 명의 숫자를 제외했을 때 합이 100이 되는 경우를 찾음
for i in range(len(numbers)):
    for j in range(i + 1, len(numbers)):
        if total_sum - numbers[i] - numbers[j] == 100:
            for k in range(len(numbers)):
                if k != i and k != j:
                    print(numbers[k])
            exit()

 

---

2회차 (itertools 사용)

• 시간 92ms
• 처음에는 이중 for문이 비효율적이라고 생각했으나, 실제로는 속도가 빠르게 나왔다. 이후, 블로그를 참고하여 브루트 포스 알고리즘을 직접 구현하는 것이 코딩 테스트 공부에 도움이 된다는 점을 확인했다. 특히 삼성 코딩 테스트의 경우 itertools 라이브러리를 사용하지 못하기 때문에 직접 구현하는 습관을 들이는 것이 중요하다고 한다...

import itertools

# 9개의 숫자를 저장할 배열을 선언
numbers = []

# 사용자로부터 9개의 숫자를 입력받아 배열에 추가
for _ in range(9):
    numbers.append(int(input()))

# 배열을 오름차순으로 정렬
numbers.sort()

# 배열의 모든 숫자의 합을 계산
total_sum = sum(numbers)

# itertools.combinations를 사용하여 2개의 숫자 조합을 만듦
for combo in itertools.combinations(numbers, 2):
    if total_sum - sum(combo) == 100:
        # combo에 포함되지 않은 숫자들을 출력
        for number in numbers:
            if number not in combo:
                print(number)
        exit()

 

➡️ 정답 코드

• 완전 탐색은 input의 크기가 유난히 작으면서 모든 경우의 수를 탐색하는 코드 구현이 가능할 경우에 고민해보는 것이 좋다. 완전 탐색은 모든 경우의 수를 빠뜨리지 않고 탐색할 수 있게 구현하는 것이 중요하다.

# 9개의 숫자를 저장할 배열을 선언
numbers = []

# 사용자로부터 9개의 숫자를 입력받아 배열에 추가
for _ in range(9):
    numbers.append(int(input()))

# 배열을 오름차순으로 정렬
numbers.sort()

# 배열의 모든 숫자의 합을 계산
total_sum = sum(numbers)

# 두 명의 숫자를 제외했을 때 합이 100이 되는 경우를 찾음
for i in range(len(numbers)):
    for j in range(i + 1, len(numbers)):
        if total_sum - numbers[i] - numbers[j] == 100:
            for k in range(len(numbers)):
                if k != i and k != j:
                    print(numbers[k])
            exit()