본문 바로가기

코딩 테스트39

큐(Queue)와 트리(Tree), 힙(Heap) 큐(Queue)자료를 보관할 수 있는 선형구조선입선출(FIFO : First-In-Fisrt-Out)의 특징을 가진다.큐의 연산의 정의size() - 큐에 들어있는 데이터 원소의 수를 구한다. O(1)isEmpty() - 현재 큐가 비어 있는지를 판단 O(1)enqueue(x) - 원소x를 큐에 추가 O(1)dequeue() - 큐의 맨 앞에 저장된 원소를 제거 O(n)peek() - 큐의 맨 앞에 저장된 원소를 반환 O(1)큐의 활용자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우자료의 생성이 여러곳에서 일어나는 경우자료의 생성과 그 자료를 이용하는 작업이 양쪽 다 여러곳에서 일어나는경우(컴퓨터 시스템내부) 등환형 큐(Circular Queue)정해진 개수의 저장공간을 빙 돌.. 2024. 4. 28.
연결 리스트(Linked Lists)와 스택(Stack) 추상적 자료구조(Abstract Data Structures)Data : 정수, 문자열, 레코드 등A sete of operations : 삽입, 삭제, 순회, 정렬, 탐색 등연결리스트(linked lists) : 각 원소들을 줄줄이 엮어서 늘어 놓은 것 배열과 연결리스트의 차이저장공간 : 배열 - 연속한 위치, 연결리스트 - 임의의 위치특정 원소 지칭 : 배열 - 매우 간편 O(1) , 연결리스트 - 선현탐색과 유사 O(n) 연결리스트의 원소 삽입def insertAt(self, pos, newNode) :if pos  연결 리스트 원소 삽입의 복잡도맨 앞에 삽입하는 경우 : O(1)중간에 삽입하는 경우 : O(n)맨 끝에 삽입하는 경우 : O(1) 연결리스트의 원소 삭제연결 리스트 원소 삭제의 복잡도.. 2024. 4. 28.
자료구조와 알고리즘 자료구조(Data Structures)리스트리스트에서 최대값을 구하려면 모든 원소를 뒤져보지 않고서는 찾을 수 없다.단위가 큰 리스트에서 최대값을 찾는 max함수를 이용하면 갯수에 비례하는 만큼의 시간이 걸린다.풀어야 하는 문제에 따라 내가 이용하는 자료구조가 어떤 성질을 가지느냐를 이해해야 한다.알고리즘(algorithm)이란?[사전적 정의]어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합[프로그래밍] 주어진 문제의 해결을 위한 자료구조와 연산 방법에 대한 선택 해결하고자 하는 문제에 따라 최적의 해법이 다르기 때문에 이 선택을 어떻게 해야 하느냐를 알기 위해 자료구조를 이해해야 한다. 배열(Arrays)같은 종류의 데이터가 줄지어 늘어서 있는 것-원소들을 순서대로 늘어 놓은 것 리스트(List.. 2024. 4. 28.

티스토리툴바