난도가 올라가는 것이 느껴지지만 오히려 재밌는 것 같다.
드디어 반으로 나눠져있는 교재 중에 절반을 지나 2권에 진입했다!
5주차 공부 기록
저번에 이어서 내가 메모하고 싶은 문제들만 정리해보았다.
==========================================================================================
문제 51번.(merge sort)
앞에서 버블정렬에 대해 공부했는데 이번엔 병합정렬이다.
정처기에서 해당 내용에 대해 개념만 공부했었는데
내가 직접 코드를 쳐보니 색다른 기분이었다.
병합 정렬은 앞의 버블정렬처럼 하나하나 요소를 모두 순환하면서 정렬을 하는 것이 아니라,
리스트를 반으로 쪼개고 쪼개는 식으로 일단 더이상 쪼갤 수 없는 단위까지 나눈 뒤에
다시 merge 하면서 정렬하는 방식이다.
def 병합정렬(입력리스트):
입력리스트길이 = len(입력리스트)
# 리스트의 길이가 1 이하라면 이미 정렬된 상태로, 그대로 반환
if 입력리스트길이 <= 1:
return 입력리스트
# 리스트를 반으로 나누기 위해 중간값 계산
중간값 = 입력리스트길이 // 2
# 리스트를 반으로 나눔
# 나눈 리스트를 또 병합정렬에 넣는 식으로 반복 (재귀함수 호출)
# 더이상 쪼개지지 않을 때까지 나누게 되고, 그 이후에 밑의 while을 사용해서 병합하게 됨
그룹_하나 = 병합정렬(입력리스트[:중간값])
그룹_둘 = 병합정렬(입력리스트[중간값:])
# 결과를 저장할 리스트 초기화
결과값 = []
# 두 그룹을 병합하는 과정
while 그룹_하나 and 그룹_둘:
# 각 그룹의 첫 번째 요소를 비교하여 더 작은 값을 결과 리스트에 추가
if 그룹_하나[0] < 그룹_둘[0]:
결과값.append(그룹_하나.pop(0))
else:
결과값.append(그룹_둘.pop(0))
# 한 쪽 그룹이 비게 되면, 남은 요소들을 모두 결과 리스트에 추가
while 그룹_하나:
결과값.append(그룹_하나.pop(0))
while 그룹_둘:
결과값.append(그룹_둘.pop(0))
return 결과값
# 함수 실행
병합정렬([1, 8, 5, 4, 6, 7, 2])
해당 정렬은 재귀함수 때문에 진행되는 과정이 굉장히 헷깔리고 복잡해서
거의 1시간 가량을 고민하고 손으로 그려가며 이해했다
https://www.youtube.com/watch?v=FCAtxryNgq4
해당 영상이 이해를 도와주는데 가장 큰 역할을 했다.
아래 코드는 가장 흔하게 구글에 널려있는 기본 병합 정렬 코드인 것 같아서 가져와봤다.
# merge_sort 안에서 반복되는 과정을 이해하면 도움이 된다.
def merge_sort(arr, first, last):
if (first < last):
mid = (first + last) // 2
merge_sort(arr, first, mid)
merge_sort(arr, mid + 1, last)
return merge(arr, first, last)
def merge(arr, first, last):
mid = (first + last) // 2
lp, rp = first, mid + 1
tmp = []
while lp <= mid and rp <= last:
if arr[lp] <= arr[rp]:
tmp.append(arr[lp])
inserted_value.append(arr[lp])
lp += 1
else:
tmp.append(arr[rp])
inserted_value.append(arr[rp])
rp += 1
while lp <= mid:
tmp.append(arr[lp])
inserted_value.append(arr[lp])
lp += 1
while rp <= last:
tmp.append(arr[rp])
inserted_value.append(arr[rp])
rp += 1
# for k in range(first, last + 1):
# arr[k] = tmp[k - first]
arr[first:last + 1] = tmp
return arr
==========================================================================================
문제 52번. (quick sort)
피봇(기준점)을 기준으로 피봇보다 작은 값을 앞쪽 (피봇의 왼쪽)에 몰아놓고,
크면 뒤쪽 (피봇의 우측)에 몰아놓는 게 기본 원리이다.
겁나 복잡하다..........
그래도 병합정렬보다는 기본 원리가 간단해서 이해하고 나니 좀 더 파악하기가 용이했다.
def 퀵정렬(입력리스트):
입력리스트길이 = len(입력리스트)
if 입력리스트길이 <= 1:
return 입력리스트
# 입력받은 리스트의 중간을 기준값으로 잡는다
기준값 = 입력리스트.pop(입력리스트길이//2)
그룹_1 = []
그룹_2 = []
# 첫번째 칸부터 기준값보다 작은 것들은 그룹1로 넣어준다
for i in range(입력리스트길이-1):
if 입력리스트[i] < 기준값:
그룹_1.append(입력리스트[i])
# 기준값보다 큰거나 같은 것들은 그룹2로 넣어준다.
else:
그룹_2.append(입력리스트[i])
# 기준값을 기준으로 작은 것들은 그룹 1, 큰것들은 그룹2 로 일렬로 나열해서 합쳐준다.
return 퀵정렬(그룹_1) + [기준값] + 퀵정렬(그룹_2)
# 위 과정을 재귀함수로서 계속 반복해서 그룹_1의 기준값을 또 정해서 왼쪽 오른쪽 구분하고...
계속 반복하다보면 모두 정렬이 되게 된다.
주어진리스트 = input().split(' ')
print(주어진리스트)
주어진리스트 = [int(i) for i in 주어진리스트]
print(퀵정렬(주어진리스트))
솔직히 무슨 소린지는 이해가 가지만
나보고 그냥 이런 형식으로 정렬하는 거 알아서 코딩해봐! 라고 하면
못 할 것 같다...
익숙해지게 연습하는 수밖에 ㅠ
==========================================================================================
문제 53번.
괄호의 짝이 잘 맞게 돼있는지를 판별하는 문제이다.
여기서부터 나는 멘붕이 왔다. 어떻게 접근해야 하는거지? ㅎ..
하지만 강의를 본 순간 생각보다 해답은 간단했다.
이런 문제를 맞닥뜨릴 때 가장 먼저 해야할 일은 경우의 수를 따져보는 것이다.
1. 다양한 경우의 수를 적어보면서 문제 의도를 파악
2. 어떤 방식으로 return 값을 올바르게 뽑아내는 것이 효율적일지 고민
3. 예외 사항은 어떤 것이 있을지를 반영
def 괄호체크(s):
# 일단 괄호 기호 2개의 개수가 동일해야 기본 조건을 만족한다. 여기서 처음 거르기 가능!
if s.count('(') != s.count(')'):
return 'NO'
# 개수가 똑같다면 둘의 순서가 () 인지를 판단해야 함
괄호 = []
# 문자의 괄호 기호를 순서대로 리스트에 넣고, 짝을 맞춰서 제거하면서 판별한다.
for i in s:
# 처음 시작은 ( 로 시작해야한다.
if i == '(':
괄호.append('(')
if i == ')':
# 첫 시작 혹은 앞의 괄호를 다 짝을 맞춰서 제거했는데 )가 남으면 탈락!
if len(괄호) == 0:
return 'NO'
괄호.pop()
# 끝까지 문제 없었으면
return 'YES'
내용이 어려운 것보다,
어떤 방식으로 문제를 풀어나가야할지 고민해본 경험이 많지 않아서 당황했던 것 같다.
어떻게 알고리즘을 짜야할지 많은 연습이 필요하다는 것을 느꼈다.
==========================================================================================
문제 54번.
이 문제는 앞에서 배운 것들을 토대로 혼자 짜볼 수 있을 정도로 나름 쉬운 편에 속했다.
# input을 리스트 컴프리헨션 방식으로 해보고 싶었음
Num = [int(x) for x in input().split(' ')]
def 연속일까(s):
# 입력받은 것을 일단 오름차순으로 정렬
s = sorted(s)
# 앞 뒤 1씩 차이나는지 확인
for i in range(len(s)-1):
if s[i] + 1 != s[i+1]:
return 'NO'
return 'YES'
print(연속일까(Num))
==========================================================================================
문제 55번. (하노이의 탑)
재귀함수의 기본인 하노이 탑....
어질어질하다.
원판의이동경로 = []
def 하노이(원반수, 시작기둥, 보조기둥, 목표기둥):
# 원판이 한 개일 때는 A-> C 옮기면 됨
if 원반수 == 1:
원판의이동경로.append([시작기둥,목표기둥])
return None
# 원반의 n-1개를 경유기둥 (A -> B) 으로 옮기고
하노이(원반수-1, 시작기둥, 목표기둥, 보조기둥)
# 가장 큰 원반은 목표기둥 (A -> C) 으로
원판의이동경로.append([시작기둥, 목표기둥])
# 경유기둥과 시작기둥을 바꿈 (B에 지금 n-1 개 원판을 옮겨놔서, 시작점이 됐음))
하노이(원반수-1, 보조기둥, 시작기둥, 목표기둥)
원반수 = int(input())
하노이(원반수, 'A', 'B', 'C')
print(원판의이동경로)
굉장히 헷깔리는데...
가장 단순하게 생각하면 맨 마지막 원판을 C로 옮기는 것을 기본 로직으로 생각하고 재귀함수를 적용하면 된다.
원판 1개 -> [A -> C]
원판 2개 -> [원판 1개 B에 옮기고] -> 밑 판을 C에 옮긴 뒤 -> [다시 원판 1개를 C 위에 얹기]
원판 3개 -> [원판 2개 B에 옮기고] -> 밑 판을 C에 옮긴 뒤 -> [다시 원판 2개를 C 위에 얹기]
원판 4개 -> [원판 3개 B에 옮기고] -> 밑 판을 C에 옮긴 뒤 -> [다시 원판 3개를 C 위에 얹기]
....
이런식으로 하노이(n-1) + 1 + 하노이(n-1) 값을 구하면 된다.
하노이(n) = 2 * 하노이(n-1) + 1
ex.
하노이(3) = 2 * 하노이(2) + 1 = 2 * ( 2 * 하노이(1) +1 ) + 1
이런시그로 자기 자신을 계속 호출하여 계산이 된다.
==========================================================================================
문제 56번.
처음에 나는 혼자 풀어볼 때 굉장히 돌아가는 방법을 썼다.
단순하게 똑같이 면적 차를 구하는 딕셔너리를 만들어서, 해당 딕셔너리의 value값을 순환해 최소값을 구하는...
아주 코드가 지저분한 방식이었다.
그런데 nationWidth의 아이템들을 통째로 리스트화하는 방법이 있었다...! 😂
이 코드 한줄로 내가 순환하고, 딕셔너리를 따로 만드는 과정을 다 생략할 수 있었다고 한다.
nationWidth = {
'Korea' : 220877,
'Russia' : 17098242,
'China' : 9596961,
'France' : 543965,
'Japan' : 377915,
'England' : 242900}
# nationWidth 그대로 써주기 위해 pop 활용
Korea_width = nationWidth.pop('Korea')
print(Korea_width)
# 내가 놓쳤던 부분!!!! 이렇게 리스트화하면 키, value를 하나의 리스트로 묶어서 사용 가능
l = list(nationWidth.items())
min_gap = abs(max(nationWidth.values())-Korea_width)
print(min_gap)
for i in l:
gap = abs(i[1]-Korea_width)
if gap < min_gap:
min_gap = gap
country = i[0]
print(f"{country} 가 한국과 가장 비슷한 면적으로 {min_gap} 차이가 납니다.")
==========================================================================================
문제 57번.
이번주에 공부한 문제 중에 가장 간단했다.
>> 내가 푼 버전
count = 0
for i in range(1001):
count += str(i).count('1')
print(count)
>> 강의 버전
def count(n):
s = str(list(range(n+1))).count('1')
print(count(1000))
차이점은 나는 리스트에 실제 숫자를 넣어두고 숫자들을 순환하면서 1의 개수를 셌고,
강사님은 전체 리스트를 하나의 string으로 합쳐서 해당 글자를 순환하며 1의 개수를 count한 것이다.
강사님의 방법이 훨씬 간단하고 일을 덜하는 것 같다... ㅎ
실제로 %%time, %%timeit 을 사용해 측정해봐도 count 메소드 사용이 더 효율적이라는 사실을 알 수 있었다.
=========================================================================================
이번 문제들은 하나하나 너무 복잡하고 어렵게 느껴졌다.
그래서 진도를 얼마 나가지 못했는데 이번달이 서포터즈 마지막달이다보니.. 목표를 달성하지 못한 것 같아 부끄럽다.
서포터즈 기간이 끝나도 남은 문제들을 모두 풀어서 정복해야겠다는 생각이 들었다.
<해당 강의 링크>
제주코딩베이스캠프 Code Festival: Python 100제 강의 | 제주코딩베이스캠프 - 인프런
제주코딩베이스캠프 | 이 강좌를 통해 문법을 보다 명확하게 이해하시고, 문제 풀이에 대한 자신감을 얻으시길 바랍니다., [사진] [사진] 안녕하세요! 제주코딩베이스캠프입니다 :) 이번에는
www.inflearn.com
'위니브 엠버서더' 카테고리의 다른 글
| [위니브 엠버서더 3기] 파이썬 코딩테스트 기초 입문 강의 6주차 도전 (0) | 2024.08.30 |
|---|---|
| [위니브 엠베서더 3기] 제주 하간디 이신 데이터들 Python으로 몬딱 분석해불게 수강후기 (0) | 2024.08.29 |
| [위니브 엠버서더 3기] Python 엑셀 프로그래밍 - with xlsxwriter 수강 후기 (0) | 2024.08.23 |
| [위니브 엠버서더 3기] 파이썬 코딩테스트 기초 입문 강의 4주차 도전 (0) | 2024.07.30 |
| [위니브 엠버서더 3기] 아주 쉽다 클라우드! AWS Lightsail 자습서! 인프런 클라우드 강의 수강 후기 (13) | 2024.07.30 |