DAY01

OT.

-수업 출결은 HRD-NET앱과 프로그래머스 사이트 이용

-공지 사항과 QA등 모든 연락은 Slack이라는 앱 이용

-실시간 수업은 ZOOM 이용

-블로그에 배움 기록

-Git Hub으로 코드 공유

-언어는 파이썬, 개인적으로 IDE(Integrated Development Environment)는 Jupyter Notebook으로 쓸 예정

-lambda, map, filter, reduce

파이썬 코딩 도장: 32.2 람다 표현식과 map, filter, reduce 함수 활용하기

 

개인적으로 공부 기록할 때, 개인 감상 같은 걸 너무 많이 적어서 공개 블로그를 팠는데 결국 여기서도 그럴 듯...

그나저나 계속 티스토리를 써왔어서 티스토리로 팠는데 velog나 notion 보니까 저것들로 옮기고 싶어짐.

깃 헙을 이용하는 것은 계속 미뤘었는데 금요일 안에 사용법을 익혀야 할 것 같다.

 

---

DAY01.

01강. 안녕, 자료구조 & 알고리즘

-실습: 리스트 원소 두 개의 합 구하기

 

 

02강. 선형 배열(Linear Array)

배열(array) → 파이썬에선 리스트(list) 이용

리스트 연산

.append(), .pop(), .insert(), .del(), .index()

 

-실습(1): 리스트에 새로운 요소 삽입하기

-실습(2): 리스트에서 원소 찾아내기

 

 

03강. 정렬(Sort), 탐색(Search)

sorted(), sort()

reverse=True

sort(key=lambda x: len(x))

sort(key=lambda x: x[], reverse=True)

탐색 알고리즘: 선형 탐색(linear search)=순차 탐색(sequential search), 이진 탐색(binary search)

이진 탐색은 이미 정렬되어 있는 경우에만 적용 가능

 

-실습: 이진 탐색 구현해보기

 

 

4강. 재귀 알고리즘(Recursive Algorithms) 기초

이진 트리(binary trees)

재귀 호출의 종결 조건 매우 중요

재귀 vs 반복

 

-실습: 피보나치 순열 구현하기

 

 

5강. 재귀 알고리즘(Recursive Algorithms) 응용

조합의 수 계산

하노이의 탑

피보나치 수열 - 중복 호출로 인한 성능 저하

 

-실습: 재귀적 이진 탐색 구현하기

 

 

6강. 알고리즘 복잡도(Complexity of Algorithms)

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

평균 시간 복잡도(Average Time Complexity)와 최악 시간 복잡도(Worst-case Time Complexity)

Big-O Notaton: 점근 표기법(asymptotic notation)의 하나

선형 시간 알고리즘 - O(n)

로그 시간 알고리즘 - O(logn)

이차 시간 알고리즘 - O(n^2)

삽입 정렬(insert sort), 병합 정렬(merge sort)

배낭 문제(Knapsack Problem) - dynamic programming

 

-퀴즈

 

7강. 연결 리스트(Linked Lists)

추상적 자료구조(Abstract Data Structures)

기본적 연결 리스트 - Node(Data, Link(next)), Head, Tail, NodeCount

단방향 연결 리스트 (singly linked list)

첫 노드에 1을 지정(0이 아닌 1부터 시작)

연산 정의

1.특정 원소 참조(k번째) - def getAt(self, pos)

2.리스트 순회

3.길이 얻어내기

배열 vs 연결 리스트

 

-실습: 연결 리스트 순회 구현하기

 

 

8강. 연결 리스트(Linked Lists) (2)

연산 정의

4.원소 삽입 - def insertAt(self, pos, newNode)

삽입하려는 위치가 리스트 맨 앞일 때 - prev가 없으므로 head 조정 필요

삽입하려는 위치가 리스트 맨 끝일 때 - tail 조정 필요

빈 리스트에 삽입할 때 - 위 두 조건에 의해 처리

5.원소 삭제 - def popAt(self, pos)

삭제하려는 node가 맨 앞일 때 - prev가 없으므로 head 조정 필요

리스트 맨 끝의 node를 삭제할 때 - tail 조정 필요

유일한 노드를 삭제할 때

6. 두 리스트 합치기 - def concat(self, L)

뒤에 붙일 리스트가 비어있는 경우

 

9강. 연결 리스트(Linked Lists) (3)

삽입과 삭제가 유연하다는 것이 큰 장점

새로운 메서드 - insertAfter(prev, newNode), popAfter(prev)

맨앞에 dummy node를 추가한 형태로

1.길이 얻어내기

2.리스트 순회 - def traverse(self)

3.특정 원소 참조(k번째) - def getAt(self, pos) getAt(0) → head

4.원소의 삽입 - def inserAfter(self, prev, newNode)

pos 범위 조건 확인

pos == 1 인 경우에는 head 뒤에 새 node 삽입

pos == nodeCount + 1 인 경우는 prev ← tail

그렇지 않은 경우에는 prev ← getAt

5.원소의 삭제 -  def popAfter(self, prev)

prev가 마지막 node일 때 (prev.next == None) 삭제할 Node없음 return None (?) -> 없어도 실행 가능

리스트 맨 끝의 node를 삭제할 때 (curr.next == None) tail 조정 필요

6.두 리스트 합치기 - def concat(self, L)

 

10강. 양방향 연결 리스트(Doubly Linked Lists)