TIL. 201030_PYTHON(3)

51-60 리뷰

개인적으로 너무 어려웠고...한 문제 푸는데 시간도 오래걸린다...
자료구조&알고리즘 처음 공부하는 거니 욕심버리고 꾸준히 할 것 !

51: merge sort를 만들어보자

병합정렬(merge sort)은 대표적인 정렬 알고리즘 중 하나로 다음과 같이 동작합니다.
1. 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
(출처: 위키피디아)

def 병합정렬(입력리스트):
    입력리스트길이 = len(입력리스트)
    if 입력리스트길이 <= 1:
        return 입력리스트
    중간값 = 입력리스트길이 // 2
    그룹_하나 = 병합정렬(입력리스트[:중간값])
    그룹_둘 = 병합정렬(입력리스트[중간값:])
    결과값 = []
    while (그룹_하나) and (그룹_둘):
        if (그룹_하나 < 그룹_둘):
            결과값.append(그룹_하나.pop(0))
        else:
            결과값.append(그룹_둘.pop(0))
    while 그룹_하나:
        결과값.append(그룹_하나.pop(0))
    while 그룹_둘:
        결과값.append(그룹_둘.pop(0))
    return 결과값
주어진리스트 = [180, 145, 165, 45, 170, 175, 173, 171]
print(병합정렬(주어진리스트))

52: quick sort

def 퀵정렬(입력리스트):
    입력리스트의길이 = len(입력리스트)
    if 입력리스트의길이 <= 1:
        return 입력리스트
    기준값 = 입력리스트.pop(입력리스트의길이//2)
    그룹_하나 = []
    그룹_둘 = []
    for i in range(입력리스트의길이-1):
        if 기준값 > 입력리스트[i]:
            그룹_하나.append(입력리스트[i])
        else:
            그룹_둘.append(입력리스트[i])
    return 퀵정렬(그룹_하나) + [기준값] + 퀵정렬(그룹_둘)
주어진리스트 = input().split(' ')
주어진리스트 = [int(i) for i in 주어진리스트]
print(퀵정렬(주어진리스트))

53: 괄호 문자열

def math(e):
    if e.count('(') != e.count(')'):
        return False
    괄호 = []
    for i in e:
        if i == '(':
            괄호.append('(')
        if i == ')':
            if len(괄호) == 0:
                return False
            괄호.pop()
    return True
n = input()
if math(n) == True:
    print("YES")
else:
    print("NO")

• 일단 '('와 ')'의 갯수가 맞아야한다
• ')'가 먼저 나오는 순간 잘못된 문자열
• '('가 나오는 순간 ')'도 언젠간 나와야한다
• '('와 ')'을 짝지어 준다고 생각하자...! 짝이 맞는 순간 pop 해버리자

54: 연속되는 수

data = list(map(int, input().split()))
data.sort()
def check():
    for i in range(0, len(data) - 1):
        if data[i] + 1 != data[i+1]:
            return print("NO")
    return print("YES")
check()

55: 하노이의 탑

하노이의 탑은 프랑스 수학자 에두아르드가 처음으로 발표한 게임입니다. 하노이의 탑은 A, B, C 3대의 기둥과 기둥에 꽂을 수 있는 N개의 원판으로 이루어져 있습니다. 이 게임에서 다음의 규칙을 만족해야 합니다.
1. 처음에 모든 원판은 A기둥에 꽂혀 있다.
2. 모든 원판의 지름은 다르다.
3. 이 원반은 세 개의 기둥 중 하나에 반드시 꽂혀야 한다.
4. 작은 원반 위에 큰 원반을 놓을 수 없다.
5. 한 번에 하나의 원판(가장 위에 있는 원판) 만을 옮길 수 있다.

원판의이동경로 = []
def 하노이(원반의수, 시작기둥, 목표기둥, 보조기둥):
    #원판이 한개일 때에는 옮기면 됩니다.
    if 원반의수 == 1:
        원판의이동경로.append([시작기둥, 목표기둥]) 
        return None
    #원반의 n-1개를 보조기둥으로 옮기고
    하노이(원반의수-1, 시작기둥, 보조기둥, 목표기둥)
    #가장 큰 원반은 목표기둥으로
    원판의이동경로.append([시작기둥, 목표기둥]) 
    #보조기둥과 시작기둥을 바꿉니다!
    하노이(원반의수-1, 보조기둥, 목표기둥, 시작기둥)
하노이(3,'A','C','B')
print(원판의이동경로)
print(len(원판의이동경로))

• 재귀함수...하노이탑
  뭘 하고싶은가..(A출발, C끝, B임시)

1. A에 있는걸, C로 옮기고 싶다
2. 3개의 원판이 있다면 2개를 B로 보내야한다.
3. A에 남은 원판 하나 C에 넣는다
4. B에 있는 원판 2개를 C에 넣는다...
   탈출조건은 재귀함수에서 원판이 하나인 경우 C로 가면 함수 return 한다...
   3개일 때는 2개 2개일 때는 1개...n개일 때는 n-1개
   나눠서 생각할 것 !

• 진짜 쉽게 다시 한번 더!
  나는 원판 3개 가지고 있다...
  2개는 B로 보내야한다. ->(A출발, B끝, C임시)
  나머지 남은 하나는 C로 보낸다
  B로 보낸 원판 2개를 C로 보낸다 -> (B출발, C끝, A임시)
• n개도 마찬가지 원리 적용!
• 추상화 -> 구체화

56: 리스트의 함수 응용

nationWidth = {
    'korea': 220877,
    'Rusia': 17098242,
    'China': 9596961,
    'France': 543965,
    'Japan': 377915,
    'England': 242900
}
nationWidth_list = list(nationWidth.values())
nationWidth_list.sort()
for i in nationWidth.keys():
    if nationWidth[i] == nationWidth_list[1]:
        print(i, nationWidth_list[1] - nationWidth_list[0])

57: 내장함수 응용하기

s = []
count = 0
for i in range(0, 1001):
    s.append(str(i))
s = "".join(s)
for i in s:
    if i == "1":
        count += 1
print(count)

58: 콤마 찍기

num = int(input())
print(format(num, ","))

59: 빈칸채우기

data = input()
data = data.center(50,"=")
print(data)

• 이렇게도 가능

user_input = input()
print("{0:=^50}".format(user_input))

60: enumerate

student = ['강은지', '김유정', '박현서', '최성훈', '홍유진', '박지호', '권윤일', '김채리', '한지호', '김진이', '김민호', '강채연']
student.sort()
for i, name in enumerate(student):
    print(f"번호: {i+1}, 이름: {name}")