[파이썬] DAY9 자료구조(기초개념, 리스트)

데이터를 저장하는 방법

자료 구조: 자료를 효율적으로 사용하기 위해 자료의 특성에 따라 분류하여 구성하고 저장 및 처리하는 작업

 

 

자료구조의 분류

1) 단순 구조: 기본 자료형 ex) 정수, 실수, 문자형

2) 선형 구조:  자료들 간의 앞뒤 관계가 1:1의 선형 관계 ex) 리스트, 연결 리스트, 스택(append, pop()), 큐, 덱

3) 비선형 구조: 자료들 간의 앞뒤 관계가 1:다 또는 다:다의 관계 ex) 트리, 그래프

4) 파일 구조: 레코드의 집합인 파일에 대한 구조 ex) 순차파일, 색인파일, 직접파일 -> 집합으로 자료구조에서 구현하지 않는다.

 

자료의 구조 도식

 

자료의 표현 4개 - 10진수 - 두 가지 나뉘는 이유(16진법, 10진법)

고정 소수점 vs 부동소수점

 

 

존 형식의 표현

 

 

고정 소수점 : 정수부분을 표기할 수 없다는 한계점이 있다.

부도 소수점 : 정수부분 표기하는 부분이 있다. 소수부와 지수만으로 적용한다. 

 

 

문자에 이진수 코드표

BCD : 6BIT 대문자만 표현 할 수 있다. 

EBCDIC : 8비트로 늘려서 대문자, 소문자, 특수 문자를 표현

ASCLL : 7BIT로 줄이고 컴팩트하게 쓴다. 안 쓰는 빈 공간을 없앤다.

유니코드: 16BIT로 쓴다.  각 나라마다 쓰는 문자까지 포함 ex) 게임할 때 한국팩을 설치한다.

 

 

 

논리 자료

1바이트 표현

3가지로 표현, ex) 참이면 하나 이상의 비트를 1로 표시한다. -> 하나의 불리언 자료로 표현   

 

 

알고리즘 하는 방법

 

가상코드로 먼저 쓰자

공간복잡도 = 컴파일 영역, 정적 할당(코드영역 데이터영역 스택영역) + 동적 할당(힙영역)

 

시간복잡도 = 컴파일 시간 + 실행 시간(명령문의 빈도수로 판단)

최악의 케이스로 판단한다. - 빅오 표기법

빅오 : 이하 모두 표현

세타: 둘의 교집합

오메가: 최상부터 끝까지

 

 

정렬 알고리즘 중에 가장 느린 것이 O(n^2)이다. 

 

n^2 < 2^n < n^3

 

코드를 쪼개면 logn 으로 본다. (if elif)

 

 

 

 

---

리스트

1. 선형 리스트

논리적인 순서와 물리적인 순서가 일치

원소 삽입이나 삭제 시에 논리적인 순서가 한 칸씩 뒤로가거나 앞으로 가는 등 물리적인 순서와 엇나가는 한계가 있다.

파이썬의 리스트는 선형리스트와 비슷하지만 가변할 수 있다는 점에서 장점이 있다.

문제점 : 삽입 -> 이동, 삭제 -> 이동을 하므로 비효율적인 성능

ex) HD

 

2. 연결 리스트

각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식

논리적인 순서와 물리적인 순서가 일치하지 않음

장점: 물리적 순서를 맞추기 위한 오버헤드가 발생하지 않는다.

크기 변경이 유연하고 더 효율적으로 메모리를 사용한다.

ex) SSD

 

1) 단순 연결 리스트

한 개의 링크 필드 + 한 개의 데이터 필드

객체는 동적할당, 링크 필드가 객체의 주소를 기억한다.

삽입,  삭제 방식은 3가지 : 머리, 가운데, 꼬리

 

2) 원형 연결 리스트

단순 연결 리스트를 연결

맨 마지막 노드와 첫번째 노드가 연결모든 노드의 링크 부분이 존재한다.리스트의 시작지점인 head point로 첫번째 지점을 알아낸다.

 

3) 이중 연결 리스트

두 개의 링크 필드 + 한 개의 데이터 필드로 구성

노드와 노드를 양방향으로 이동 가능하다.

삽입할 때 끊김이 발생하지 않으려고 순서대로 한다.

 

 

4) 이중 원형 연결 리스트

 

 

파이썬은 끝에 NONE을 쓰자

마지막에 이름을 지우는 건 del 이다.

del n 을 해주자

왜냐하면 n은 앞의 노드가 쳐다보고 있으므로 가비지가 아니다. 따라서 자동으로 삭제되지 않는다.