section5 최종 목적은 자료구조와 알고리즘을 이해하며 프로그래밍하는 것이다.
521 - 524 목적은 프로그램의 기반이 되는 자료구조와 알고리즘을 반복해서 학습하는 것이다.
학습목표
- 자료구조의 코어가 되는 추상자료형(ADT)과 함께 연결리스트, 큐, 스택의 설계에 대해 익혀야 한다.
핵심 키워드
- 문제해결 & 컴퓨팅 사고력
- 자료구조 (Data Structure)
- 추상자료형 (Abstract Data Type: ADT)
- 연결리스트, 큐, 스택
- 파이썬 내장함수
자료 구조의 미션
- 현실을 프로그래밍적으로 표현하기
- 큰 데이터를 효율적으로 관리하기 (메모리의 효율적인 사용)
적은 양의 데이터로는 자료 구조의 힘을 체감할 수 없다. 그렇기 때문에 나처럼 이제 막 공부를 시작하는 사람은 공감도 안되고 이해하기도 어려울 수 있다. 경험이 어느 정도 쌓여야 자료 구조의 필요성을 체감하고 이해도 될 것이다.
자료 구조 vs. 추상 자료형 ?
추상 자료형
- 기능의 구현 부분을 나타내지 않고 순수하게 기능이 무엇인지 나열한 것이 => 추상 자료형
- 추상 자료형은 객체 지향 언어의 클래스 개념과 같다.
- 추상 자료형은 마치 사용설명서의 개념과 같다.
- 추상 자료형은 구현자와 사용자를 분리해 준다.
- 추상 자료형은 정해진 것이 아니다. 많이 사용되고 있는 형태들은 있지만 자신의 구현 목적에 따라서 추상 자료형은 얼마든 달라질 수 있다.
자료 구조
- 추상 자료형에 구현이 들어가는 순간, 그 구현체를 칭하는 것이 => 자료 구조
- 프로그램에서 자료들을 정리하는 여러가지 구조
- 프로그램은 이러한 자료구조와 문제를 해결하는 절차인 알고리즘으로 구성된다.
연결 리스트
Add psuedo code
▶ Add a value to the head (addFirtst)
STEP 1) 임시변수 temp 에 새로운 숫자 입력값을 할당
temp = input new number(n)
STEP 2) temp 의 next 값으로 기존 head 값을 할당. (포인터 변경)
temp.next = head
STEP 3) head 에 임시변수 temp 값을 할당 (head 교체)
head = temp
▶ Add a value to the middle (addMiddle)
STEP 1) head 값을 임시변수 pre 에 할당
pre = head
STEP 2) pre 에 현재 pre 의 next 인 값을 할당 (pre 교체: head 값 -> add될 숫자 앞 위치의 값)
for문 또는 while (--k != 0):
pre = pre.next
STEP 3) after 에 pre 의 next 인 값을 할당
after = pre.next
STEP 4) new 에 새로운 숫자 입력값을 할당
new = input new number(n)
STEP 5) pre 의 next 값으로 new 값을 할당 (포인터 변경)
pre.next = new
STEP 6) new 의 next 값으로 after 값을 할당 (포인터 변경)
new.next = after
▶ Add a value to the tail (addLast)
STEP 1) 임시변수 temp 에 새로운 숫자 입력값을 할당
temp = input new number(n)
STEP 2) 기존 tail 의 next 값으로 임시변수 temp 값을 할당 (포인터 변경)
tail.next = temp
STEP 3) tail 에 임시변수 temp 값을 할당 (tail 교체)
tail = temp
Remove psuedo code
STEP 1) head 값을 임시변수 cur 에 할당
cur = head
STEP 2) cur 에 현재 cur 의 next 인 값을 할당 (cur 교체: head 값 -> remove될 숫자 앞 위치의 값)
for문 또는 while (--k != 0):
cur = cur.next
STEP 3) del 에 cur 의 next 인 값, 즉 remove될 값을 할당
del = cur.next
STEP 4) cur 의 next 에 cur의 next, next 인 값을 할당 (포인터 변경: remove될 숫자 다음 위치의 값으로)
cur.next = cur.next.next
STEP 5) del 값을 삭제
delete del
[참고자료]
비쥬얼고
데이터 구조 기초
https://dev-emmababy.tistory.com/87
생활코딩 - 유투브 data structure
https://youtube.com/playlist?list=PLuHgQVnccGMDsWOOn_P0EmAWB8DArS3Fk
생활코딩 - 블로그 linked list
https://opentutorials.org/module/1335/8857
연결리스트/배열 - 시간복잡도
https://m.blog.naver.com/raylee00/221944085465
과제도움
https://daimhada.tistory.com/107
'코드스테이츠 AI 부트캠프 > Section 5' 카테고리의 다른 글
| 코드스테이츠_AIB_511 : 파이썬 프로그래밍 (0) | 2022.02.24 |
|---|