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임시)
- A에 있는걸, C로 옮기고 싶다
- 3개의 원판이 있다면 2개를 B로 보내야한다.
- A에 남은 원판 하나 C에 넣는다
- 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}")
