본문 바로가기
파이썬(PYTHON)/자료구조
 (5)
[Python] 큐, 그래프, 트리 4. 큐(Queue) - 선형데이터 구조 - FIFO(First In First Out), 먼저 입력된 것이 먼저 삭제됨.(먼저 입력된 소비자가 먼저 서비스를 받는다.) - 데이터의 한쪽에서는 입력, 다른 한쪽에서 삭제 발생 - 데이터의 시작부분: front, 데이터의 끝부분: Rear - 한번에 하나의 데이터만 처리가능 #리스트로 구현 queue = [] queue.append(10) queue.append(7) queue.append(5) queue.append(8) print(queue) #10, 7, 5, 8 queue.pop(0) print(queue) #7, 5, 8 queue.pop(0) print(queue) #5, 8 #Node 이용해 구현 class Node : def __init__(..
[Python] 자료구조 - 스택 3. 스택(Stack) - 선형 데이터 구조 - 데이터의 한쪽에서만 삽입(push)과 삭제(pop)가 발생함. - ★LIFO(Last In First Out), 나중에 입력된 데이터가 가능 먼저 삭제됨. - 데이터를 저장할 공간이 부족하면 오버플로(Overflow) 발생 - 삭제할 데이터가 없으면 언더플로(Underflow) 발생 - 한번에 하나의 데이터만 처리 가능 #파이썬에서 제공하는 list로 구현 stack = [] #push - 입력 stack.append(10) stack.append(5) stack.append(7) print(stack) #pop - 삭제 stack.pop() print(stack) #노드를 이용하여 구현 class Node : def __init__(self, data):..
[Python] 배열, 연결리스트 #자료구조의 종류 - 배열(Array) - 연결리스트(Linked List) - 스택(Stack) - 큐(Queue) - 그래프(Graph) - 트리(Tree) 1. 배열(Array) #파이썬에는 없는 개념(list와 그나마 가장 유사함) - 가장 기본적인 자료구조, 선형 데이터구조 - 배열 생성되는 순간 인덱스 부여(인덱스 표기법) - 배열 크기 고정 - 배열크기가 고정되어 있어 데이터를 추가, 삭제과정이 비효율적 ~ 더 큰 배열을 추가로 만들고 이전 값을 복사한 후 새로운 값 추가 ~ 더 작은 배열을 추가로 만들고 삭제할 값을 빼고 이전 값을 복사 - 데이터가 삭제되면 남은 공간이 생겨 메모리 낭비 발생 - 하나의 변수명으로 여러 데이터를 관리가능함. 2. 연결리스트(Linked List) 2-1. ..
[Python] 정렬 3-1. 정렬(선택) - 가장 작은 데이터를 선택하여 맨 앞으로 보내 순서대로 정렬하는 방식 ~ 최소값을 찾아서 맨 앞으로 교체한다. - 맨 앞부터 작은 데이터를 채워넣음. - 이미 정렬되어 있어도 상관 없이 작은 값을 찾아서 수행하기 때문에 성능이 떨어짐. ~ 맨앞은 이미 정렬된 상태이므로, 맨앞은 제외하고 나머지 부분에서 다시 최소값을 찾아서 앞으로 교체한다.(반복) - 반복문을 통해 모든 인덱스에 접근이 필요함. - 시간 복잡도 O(n²) list = [64, 25, 12, 22, 11] for i in range(0, len(list)) : min_idx = i for j in range(i+1, len(list)): if list[min_idx] > list[j] : min_idx = j lis..
[Python] 재귀호출, 시간복잡도 1. 재귀호출 2. 시간복잡도 3. 정렬★★★ 4. 배열★ 5. 연결리스트★ 6. 스택★ 7. 큐★ 8. 그래프★ 9. 트리★ #자료구조 : 데이터를 구조적으로 관리 및 표현하는 방식으로, 필요한 기능을 가능하게 하는 기술 - 최소한의 메모리 사용 가능 (메모리는 적게 쓰고) - 처리 속도 향상으로 실행시간 단축 (속도는 빠르게!) 1. 재귀함수 : 자기가 자기를 호출 - 동일한 문제를 계속해서 간단하고 쉽게 반복 수행하여 문제를 해결함. - 동일 함수의 복사본이 스택 메모리에 생성되고 쌓임. ~ 재귀함수는 기본함수와 별개의 함수 - 호출한 함수가 모두 return 되어야 되돌아와서 실행함. - 재귀호출의 종료 조건이 필요함.★★★ ~ 종료 조건이 없으면 무한 반복됨. - 재귀호출할 때 함수가 메모리에 ..

티스토리툴바