회고
2023-04-09
오늘은 서울에 갔다왔다. 아는 형과 점심 약속을 잡았고, 12시 30분에 합정역에서 만나 고기를 구워먹었다. 타지에서 아는 사람을 만나니 좋더라.
18시 전에 시흥으로 돌아와서 19시부터 오늘의 공부를 시작했다. 오늘은 리액트보다는 알고리즘에 집중했다. 파이썬 알고리즘 교재를 읽어보며 예전에 배워서 가물가물한 알고리즘을 새로 공부해보고자 했다. 확실히 다시 읽어보니 몰랐던 파이썬 문법이나 잘 기억이 나지 않던 알고리즘에 대해 복기할 수 있었다.
팀원들과 서로 풀었던 문제에 대해 풀이를 공유하며 문제 복기와 더 나은 알고리즘에 대해 이야기를 나누었다. 어쩌다 내가 강의를 하게 됐지만.. 동료들이 나를 보는 시선이 점점 달라짐에 따라, 미묘한 부담감도 느낀다. 알고리즘은 설렁설렁할 생각이었는데 열심히 해야할 것 같다.
써보고 느끼는 건데 이건 회고가 아니라 그냥 일기장 같다. 모르겠다. 그냥 이렇게 써야지.
TIL
for-else
파이썬 알고리즘 교재를 읽다 생전 처음 본 문법을 발견했다.
for i in range(5):
print(i, end=' ')
else:
print("완료")for문 밑에 바로 else가 붙어있는 모습이다. if문도 없는데 대체 어디에 else가 붙어있는 건지 몰랐는데, 검색해보니 python에 for-else 문법이 있더라. 정말 신기하다..
보초법(Sentinel method)
보초법: 배열 선형 탐색 시, 배열의 마지막에 찾고자 하는 값을 추가한다.
선형 검색은 반복할 때마다 2가지 종료 조건을 체크한다. (1) 찾고자 하는 값을 찾았을 때와 (2) 배열의 끝에 도달했을 때이다. 반복문을 통해 종료 조건을 검사하는 cost는 무시할 수 없다. 그러나 보초법을 사용하면 (2) 배열의 끝에 도달했는지를 검사하는 cost를 줄일 수 있다.
찾는 값: 2
배열: 1, 3, 6, 2, 5, 4, 8, 7
-> 선형 탐색할 배열: 1, 3, 6, 2, 5, 4, 8, 7, 2
- 일반적인 선형 탐색
whie True:
if i == len(arr):
return 찾지 못했다.
if arr[i] == key:
return 찾았다.- 보초법을 적용한 선형 탐색
whie True:
# if i == len(arr): 필요없음
# break
if arr[i] == key:
break
return 찾지못했다. if i == len(arr) else 찾았다.그러나 while문 기반 선형 탐색에서만 사용할 수 있을 것 같다. 어차피 for문에서는 종료조건 없이 정해진 범위 내에서만 탐색하는거니까.
정렬 알고리즘
오랜만에 복기함. 퀵 정렬은 아직도 익숙해지지 않는다.
- 버블 정렬
- 단순 선택 정렬
- 단순 삽입 정렬
- 이진 삽입 정렬: 정렬된 구간에서 이진 탐색을 수행하여 탐색 시간을 줄인 삽입 정렬.
- 셸 정렬
- 퀵 정렬
- 병합 정렬
- 힙 정렬
- 도수 정렬
점화식
하노이탑 문제를 풀며 이동 횟수를 계산하기 위해 점화식으로 일반항을 계산하려 했는데, 어떻게 하는지 하나도 기억이 안나더라.. 검색해서 풀긴 풀었다. 고등수학을 벌써 까먹다니..
- 원반이 n개인 하노이탑의 점화식
f(n) = 2 * f(n-1) + 1
참고
