inflearn logo
강의

강의
N
챌린지

챌린지
멘토링

멘토링
N
클립

클립
로드맵

로드맵
지식공유

[인프런 워밍업클럽 CS 2기] 3주차 발자국👣

f1rstf1y9
2

3주차 학습내용

운영체제

알고리즘

A = [34, 58, 13, 94, 29]

# 이미 정렬된 부분이라고 가정하는 0번째 요소를 제외한 나머지 부분 순회
for i in range(1, len(A)): 

  # 이미 정렬된 부분(0번째~i-1번째)에서 자리 찾기
  # 뒤에서부터 훑으면서 큰 원소들을 만날 때마다 교환
  for j in range(i-1, 0, -1):
    if A[j+1] > A[j]:
      break
    A[j], A[j+1] = A[j+1], A[j]
def merge_sort(unsorted_list):

  # 리스트를 더 이상 나눌 수 없으면 해당 리스트를 그대로 리턴
  if len(unsorted_list) <= 1:
    return unsorted_list
    
  # 리스트를 반으로 나누기
  mid = len(unsorted_list)//2
  
  # 왼쪽 부분을 재귀적으로 정렬
  left = merge_sort(unsorted_list[:mid])
  
  # 오른쪽 부분을 재귀적으로 정렬
  right = merge_sort(unsorted_list[mid:])
  
  
  # left, right 리스트를 처음부터 순회하기 위한 인덱스 초기화
  left_idx = right_idx = 0
  # 정렬된 left, right 두 리스트를 병합한 결과를 저장할 리스트 초기화
  merged = []
  
  # 왼쪽과 오른쪽 리스트의 앞부분 부터 비교해가며 병합
  while (left_idx < len(left) and right_idx < len(right)):
  
    # 현재 가리키고 있는 왼쪽 값이 오른쪽 값보다 작으면 왼쪽 값을 병합리스트에 추가하고, 왼쪽 인덱스에 1 더하기
    if right[right_idx] > left[left_idx]:
      merged.append(left[left_idx])
      left_idx += 1
    
    # 현재 가리키고 있는 오른쪽 값이 왼쪽 값보다 작으면 왼쪽 값을 병합리스트에 추가하고, 왼쪽 인덱스에 1 더하기
    else:
      merged.append(right[right_idx])
      right_idx += 1
      
  # 왼쪽 리스트에 남은 값이 있으면 병합 리스트에 추가
  while (left_idx < len(left)):
    merged.append(left[left_idx])
    left_idx += 1
    
  # 오른쪽 리스트에 남은 값이 있으면 병합 리스트에 추가
  while (right_idx < len(right)):
    merged.append(right[right_idx])
    right_idx += 1
  
  # 병합된 결과 리턴
  return merged

A = [34, 58, 13, 94, 29]
A = merge_sort(A)
A = [34, 58, 13, 94, 29]

def quick_sort(low, high):
  if low < high:
  
  	# pivot을 가장 큰 값으로 임의로 선택
    pivot = A[high]
    
    # 현재 pivot보다 작은 부분의 마지막 요소의 인덱스
    # 주어진 리스트 안에서 pivot보다 작은 요소의 개수 - 1
    i = low - 1 
    
    # 분할 과정
    for j in range(low, high): # low부터 high-1까지 순회
      # pivot보다 작은지 확인
      if A[j] <= pivot: 
        i = i + 1
        A[i], A[j] = A[j], A[i] # 작은 부분(왼쪽 부분)으로 옮기기

    # 작은 부분의 마지막 요소의 바로 뒤 요소와 pivot을 교환
    # pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, 큰 원소는 오른 쪽으로 배치
    A[i+1], A[high] = A[high], A[i+1]
    
    # 분할 과정 이후 pivot의 최종 위치
    pivot_idx = i + 1 
    
    # 재귀적 정렬 - 왼쪽 부분 정렬
    quicksort(low, pivot_idx - 1)
    
    # 재귀적 정렬 - 오른쪽 부분 정렬
    quick_sort(pivot_idx + 1, high)

# 초기 호출
quick_sort(0, len(A)-1)

회고

3주간의 워밍업클럽 2기가 마무리되었다. 끝나고 회고를 작성하면서 드는 생각은 이것저것 챙기려고 하다보니, 3주간 약간은 쫓기면서 수업을 수강하진 않았는가 하는 아쉬움도 들고, 그럼에도 혼자 수강했다면 절대 완강하지 못했을 거란 생각이 들어서 참여하길 잘했다고 생각한다!

알고리즘 공부는 개인적으로도 필요성을 많이 느껴서 블로그에 정리도 해보고, 따로 이런저런 글도 많이 읽어서 익숙했는데 운영체제는 사실 예전에 CS 면접 준비를 위해 잠깐 슥 겉핥기로 훑어본게 전부였고, 그때도 제대로 이해하진 못해서 좀 걱정되는 부분도 있었다. 다행히 친절한 난이도의 강의와 설명 덕분에 큰 무리없이 강의를 수강할 수 있었다. 기회가 된다면 다시 강의를 한바퀴 돌리면서 좀 더 개념을 확실히 익히고 추가적으로 궁금한 점이 생기는 부분을 더 깊게 파고들어보고 싶다. 일단은 기초 개념을 잡았다는 것에 만족:-)

이제 워밍업 클럽은 끝났지만, 이걸로 공부를 완전히 끝내서는 당연히 안될 것이다. 인프런에 올린 발자국의 배운 내용 요약은 내가 강의를 들으면서 휘갈겼던(..) 노트를 그대로 옮긴거라, 추후엔 내 블로그에 이해한 내용을 나만의 방식으로 정리한 것과 강의를 들으면서 생겼던 의문, 그리고 그 의문에 대한 답 등등..을 정리하며 추가적으로 공부할 예정이다. (제발 하길...)

워밍업 클럽 2기 안녕👋

답변 0