패스트캠퍼스 환급챌린지 8일차 : 네카라쿠배 취업 끝장내는 파이썬 코딩테스트 마스터

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.

 

 

8일차.. 아직 습관 생성은 안 된 것 같다.

침대에 눕고싶다.. 잠온다.. 하지만 난 어른이니까🥲

 

오늘 강의 목록

Chatper 2 기초 알고리즘

7강. 완전 탐색 알고리즘 소개

8강. 완전 탐색 사용 예제 1

9강. 완전 탐색 사용 예제 2

 

공부 시작 시각과 종료 시각

 

 

완전 탐색 이란?

완전 탐색(Brute Force)은 모든 경우의 수를 다 고려하여 탐색하는 알고리즘

 

경우의 수를 계산하여야 하기 때문에 순열, 조합, 부분집합 등의 개념을 사용한다.

 

 

사용 라이브러리

• 조합: itertools.combinations
• 순열: itertools.permutations
• 부분 집합: 
  • 예를 들어 pocket 리스트의 값이 4개일 때, 부분 집합은
  • 값이 0개인 경우, 값이 1개인 경우, 값이 2개인 경우, 값이 3개인 경우, 값이 4개인 경우. 총 5가지가 있으며
  • 이들은 각각 조합으로 구할 수 있다.  

from itertools import combinations

pocket = [1,2,3,4]
subset = []
for i in range(len(pocket) + 1):
	subset.extend(list(combinations(pocket, i)))

 

 

 

문제 1. 2309번: 일곱 난쟁이

오. 오랜만에 쉬운 문제가

 

나의 풀이

import sys
from itertools import combinations

heights: list = sys.stdin.read().splitlines()

heights_combinations = list(combinations(heights, 7))

for c in heights_combinations:
    int_list = list(map(int, c))
    if sum(int_list) == 100:
        for i in sorted(int_list):
            print(i)

 

 

강사님 풀이

from itertools import combinations

heights = []
for _ in range(9):
    height = int(input())
    heights.append(height)

for a in combinations(heights, 7):
    if sum(a) == 100:
        a = list(a)
        a.sort()
        for x in a:
            print(x)
        break

 

 

보완할 점

조합 조건 검색하고 일치하는 거 나오면 break 하는 부분을 빠뜨렸다!!

다음에는 강사님 코드처럼 넣어주자..!!

 

 

문제2 10819번: 차이를 최대로

내 풀이

import sys
from itertools import permutations

N, A = sys.stdin.read().splitlines()
N = int(N)
A = list(map(int, A.split()))


def calculate(arr: tuple) -> int:
    result = 0
    for i in range(len(arr)-1):
        result += abs(arr[i] - arr[i+1])

    return result


max_score = 0
for i in list(permutations(A, N)):
    score = calculate(i)
    if score > max_score:
        max_score = score

print(max_score)

 

 

강사님 풀이

from itertools import permutations

N = int(input())
A = list(map(int, input().split()))

max_diff_sum = 0
for a in permutations(A, N):
    diff_sum = 0
    for i in range(N-1):
        diff_sum += abs(a[i] - a[i+1])

    max_diff_sum = max(max_diff_sum, diff_sum)

print(max_diff_sum)

 

 

으음.. 역시 더 깔끔하군...

 

내 풀이에서 개선할 점

1. permutations(A, N)은 이미 iterable이므로 list로 감쌀 필요 없다.

2. 스코어 계산하는 부분을 함수 분리했는데, 한 줄짜리라 굳이 할 필요없다.

 

 

 

 

 

 

 

https://abit.ly/lisbva

#패스트캠퍼스 #환급챌린지 #패스트캠퍼스후기 #습관형성 #직장인자기계발 #오공완