자료구조12 [자료구조] 연결된 구조 (Linked Structure) 앞에서 우리는 스택과 큐, 덱을 구현할 때 배열을 이용했다.배열을 이용하면 쉽고 간단하게 구현할 수 있어서 편리하지만 일정 크기로 용량이 고정되고 메모리가 불필요하게 낭비된다는 단점이 있다. 이러한 문제점들을 해결할 수 있게 고안된 자료구조가 바로 연결된 구조이다! 연결된 구조는 노드(node)를 여러 개 연결시켜 구현하는데, 노드 하나에는 요소를 담는 데이터 필드와 다음 노드를 가리키는 링크 필드를 갖는다.즉 가장 처음 노드만 알면 링크 필드를 거치고 거쳐 배열을 사용하지 않고도 해당 자료구조의 모든 요소에 접근할 수 있다는 것이다! (물론 n번째 요소에 접근하는 데에는 O(n)이 소요될 것이다)이 때 가장 처음 노드를 가리키는 변수를 ‘헤드 포인터(head pointer)’라고 한다. 연결 리스트의 .. 2024. 1. 7. [자료구조] 덱 (Deque) 덱: 전단(front)와 후단(rear) 모두에서 삽입 삭제가 가능한 큐즉 큐의 업그레이드된 버전이라고 볼 수 있다. 그래서 원형 큐를 상속해서 덱을 구현하는 게 효과적임! 큐의 기능isEmpty(): 덱이 비어있으면 True를, 아니면 False를 반환한다.addFront(e): 항목 e를 덱의 맨 앞(front)에 추가한다.deleteFront(): 덱의 맨 앞(front)에 있는 항목을 삭제하고 반환한다.getFront(): 덱의 맨 앞(front)에 있는 항목을 반환한다.addRear(e): 항목 e를 덱의 맨 뒤(rear)에 추가한다.deleteRear(): 덱의 맨 뒤(rear)에 있는 항목을 삭제하고 반환한다.getRear(): 큐의 맨 뒤(rear)에 있는 항목을 반환한다.isFull():.. 2024. 1. 7. [자료구조] 큐 (Queue) 큐: 선입선출(FIFO)의 자료구조후단(rear)에서 삽입하고 전단(front)에서 삭제한다.큐를 단순히 front와 queue가 있는 리스트로 구현하면 front의 인덱스는 항상 0, rear의 인덱스는 항상 -1이 되는 문제점이 발생하는데, 이렇게 될 경우 삭제나 삽입 연산 중 하나는 적어도 O(n)의 시간복잡도를 가져서 비효율적임.그래서 원형 큐를 구현하는 것이 더 효율적이다!rear과 front 변수를 삽입과 삭제 시에 바꿔줌으로써 항상 O(1)의 시간을 가질 수 있도록 만들어준다!컴퓨터와 프린터 사이에 인쇄 작업실시간 비디오 스트리밍의 버퍼링은행의 대기표큐의 기능isEmpty(): 큐가 비어있으면 True를, 아니면 False를 반환한다.enqueue(e): 항목 e를 큐의 맨 뒤(rear)에 .. 2024. 1. 7. [자료구조] 스택 (Stack) 스택: 후입선출(LIFO)의 자료구조출입구가 하나밖에 없는 일직선 통로와 같다. 스택이 사용되는 예시로는 아래를 들 수 있다.되돌리기 기능 (Ctrl + Z)브라우저의 이전 페이지로 이동함수 호출 후 메인으로 복귀괄호 닫기 프로그램등등에 사용된다. 스택의 기능isEmpty(): 스택이 비어있으면 True를, 아니면 False를 반환한다.push(e): 항목 e를 스택의 맨 위에 추가한다.pop(): 스택의 맨 위에 있는 항목을 꺼내 반환한다.peek(): 스택의 맨 위에 있는 항목을 반환한다. (꺼내지 않음)size(): 스택의 항목 개수를 반환한다.clear(): 스택을 전부 비운다.스택의 구현class Stack: def __init__(self): self.top = [] d.. 2024. 1. 7. [자료구조] 집합 (Set) 집합: 항목들이 나열되어 있는 중복과 순서가 없는 자료구조.리스트와 유사한 구조이나 집합에는 중복되는 요소가 없으며 순서가 존재하지 않는다는 차이가 있다. 집합의 기능size(): 집합의 원소 개수를 반환한다.contains(e): 집합이 e라는 원소를 포함하는지 검사한다.insert(e): 원소 e를 새로 삽입하나 이미 e가 있다면 삽입하지 않음.delete(e): 원소 e를 집합에서 삭제하고 반환한다.equals(setB): setB와 같은 집합인지 검사한다.union(setB): setB와의 합집합을 만들어 반환한다.intersect(setB): setB와의 교집합을 만들어 반환한다.difference(setB): setB와의 차집합을 만들어 반환한다.display(): 집합을 출력한다.집합의 구현.. 2024. 1. 7. [자료구조] 리스트 (List) 리스트: 항목들이 나열되어 있는 자료구조.굉장히 자유로운 선형 구조이며 우리가 일상생활에서 가장 흔히 접할 수 있는 구조이다.간단하게 생각하면, 여러 요소들을 마구잡이로 하나로 모아 놓은 구조라고 생각하면 될 듯...? 리스트의 기능insert(pos, e): pos 위치에 새로운 요소 e를 삽입한다.delete(pos): pos 위치에 있는 요소를 삭제하고 반환한다.isEmpty(): 리스트가 비어있으면 True를, 아니면 False를 반환한다.getEntry(pos): pos 위치에 있는 요소를 반환한다.size(): 리스트의 요소 개수를 반환한다.clear(): 리스트를 초기화한다.find(e): 리스트에서 e를 찾아 인덱스를 반환한다.replace(pos, e): pos에 있는 요소를 e로 바꾼다.. 2024. 1. 7. 이전 1 2 다음 반응형
