Computer Science5 자료구조 - 큐 (원형큐) 앞서 이야기한 선형큐에는 많은 문제점이 있다. 1. 배열의 앞부분이 비어있더라도 사용할 수 없어 메모리 낭비가 심하다. 2. 큐의 크기가 제한적이다. 3. 데이터 이동 비용이 크다. 4. 큐가 포화상태일 경우 사용 불가하다. 때문에 동적으로 조정하여 해결해야한다. 이러한 선형큐의 문제점들을 쉽게 해결할 수 있는 것이 원형큐이다. 원형큐 연산 front 와 rear 의 초기값은 모두 0이다. front 는 큐의 첫 번째 요소의 하나 앞을, rear 은 마지막 요소를 가리킨다. front 와 rear 의 값이 (배열의크기 - 1) 의 위치에서 하나 증가할 땐 0이 된다. - 데이터 삽입 시 포화상태 검사 후 rear 증가, 증가된 위치에 새로운 데이터 삽입 - 데이터 삭제 시 공백 상태 검사 후 front .. 2023. 12. 1. 자료구조 - 큐 (선형큐) 큐란? 스택의 경우 데이터를 차곡차곡 쌓아 올리는 형태이지만, 큐는 데이터를 줄 세우는 형태로 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있습니다. 이러한 특성을 선입선출 (FIFO - First In First Out) 이라고 합니다. 새로운 데이터는 큐의 뒤에서 추가되고, 데이터를 삭제할 때에는 큐의 앞에서 삭제하는 구조입니다. 그렇기 때문에 큐에서의 삽입과 삭제는 다른쪽에서 일어나게 됩니다. 큐 연산 # 큐 생성 create(max_size) ::= 최대 크기가 max_size 인 공백큐를 생성한다. # 큐 초기화 init(q) ::= 큐를 초기화한다. # 큐 공백 검사 is_empty(q) ::= if(size == 0) return TRUE; else return FALSE; # 큐 포화상.. 2023. 11. 27. 자료구조 - 스택 스택이란? 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다. 스택에서의 입출력은 맨 위에서만 일어나며, 스택의 중간에서 데이터를 삭제할 수 없습니다. 그렇기 때문에 후입선출이라는 특징을 가지고 있습니다. LIFO (Last In First Out) 후입선출 스택 용어 Stack Top - 스택 상단 Stack Bottom - 스택 하단 element - 스택에 저장되는 요소 empty Stack - 요소가 하나도 없는 공백 상태의 스택 스택의 구현 stack[ ] 배열에 스택의 요소들을 저장한다고 가정했을 때, 스택에 가장 최근 입력된 자료를 가리키는 top 변수가 필요하며 가장 먼저 들어온 요소는 stack[0] 에 가장 최근에 들어온 요소는 stack[top] 에 저장된다. 스택의 연산 공백상태 검.. 2023. 11. 24. 자료구조 - 선형자료구조 (연결리스트) 선형자료구조란 요소가 일렬로 나열되어 있는 자료구조를 말한다. 연결리스트 : 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시키는 자료구조이다. 연결리스트의 종류 1. 단순 연결리스트 : 하나의 노드가 하나의 링크필드와 데이터를 갖고 있는 연결리스트이다. * 마지막 노드의 링크필드에는 null 값이 들어있다. (그림으로 표현한 단순연결리스트이다.) [ 단순 연결리스트의 삽입과 삭제 ] insert_first() : 리스트의 시작부분에 노드를 삽입하는 함수 1. 동적 메모리 할당을 통해 새로운 노드 p 생성 2. 노드 p->data 에 데이터 값을 저장 3. 노드 p->link 를 현재의 head 값으로 변경 4. head 를 p 값으로 변경 5. 변경된 헤드 포인터 반환 insert() .. 2023. 9. 23. 자료구조 - 복잡도 자료구조(data structure) 이란 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 의미한다. 시간 복잡도 : 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. 효율적인 코드로 개선하는 데 쓰이는 척도가 되기 때문에 필요하다. 빅오 표기법 시간 복잡도 표기할 때 가장 많이 사용하는 방법으로, 복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애 복잡도를 나타내는 표기법이다. ex) '입력 크기 n '의 모든 입력에 대한 알고리즘에 필요한 시간이 10n² + n 이라고 가정했을 때 이를 빅오표기법으로 나타내면 O(n²) 이 된다. n 의 값이 커질 수록 10n² 의 항이 연산량이 가장 커지고 이에 비해 나머지 항들의 연산량.. 2023. 9. 22. 이전 1 다음
