진짜 개발자
본문 바로가기

CS(Computer Science)/자료구조 (총 11개)

자료구조 - 힙(Heap)이란? 힙 힙(Heap) 이란?- 힙은 최댓값, 최솟값을 찾아내는 연산을 쉽게하기 위해 고안된 자료형이다.- 힙(Heap)은 각 노드의 키(Key)값이 그 자식의 키값보다 작지않거나(최대 힙), 그 자식의 키값보다 크지 않은(최소 힙) 완전 이진 트리이다. 아래 그림은 최대힙(Max Heap)을 나타내는 그림이다. 최대 힙(Max Heap) - 각 노드의 키값이 그 자식노드의 키값보다 큰 힙최소 힙(Min Heap) - 각 노드의 키값이 그 자식노드의 키값보다 작은 힙 힙 연산아래의 연산들은 최대(Max Heap)힙을 기준으로 설명한다. 삽입 연산- 힙은 완전이진트리의 구조를 유지해야 하므로 삽입시 트리의 가장 마지막에 원소를 추가하는 것으로 시작한다. 5를 키로 가지는 원소 삽입우선 힙은 완전이진트리의 구조를..
자료구조 - 큐(Queue)란? Queue란 Queue란- 큐는 한쪽 끝(rear)에서는 삽입연산만 이루어지며 다른 한쪽 끝(front)에서는 삭제연산만 이루어지는 유한 순서 리스트이다. 특성- 구조상 먼저 삽입된 item이 먼저 삭제가 이루어진다. (FIFO) 큐의 표현1. 순차 표현- 1차원 배열을 이용한 순차표현이다.- 인덱스를 값으로 가지는 front, rear 라는 두개의 변수와 큐의 사이즈를 나타내는 n이라는 변수를 사용한다.- front, rear를 -1로 초기화 하여 큐가 empty임을 나타낸다. (front == rear일 때 큐는 공백)- rear에서 삽입 되므로 rear가 점차 증가하여 rear==n-1인 경우 큐는 full상태이다. 문제점- 큐에 삽입이 되며 점차 rear가 증가하게 되면 결국 full상태가 된다...
자료구조 - Array(배열과) List 비교 Array(배열) 과 List의 차이점 Array(배열) 과 List의 차이점Array? - 다수의 데이터를 그룹핑해서 효율적으로 관리 가능한 자료형으로 데이터에 접근하기 위한 인덱스가 존재한다.장점- 인덱스를 통해 데이터를 가져오기 때문에 조회 속도가 빠르다.단점- 인덱스를 통해 데이터를 가져온다 즉, 데이터의 위치가 인덱스와 맵핑되어 고정된다. 추후 데이터가 삭제되는 경우 배열의 빈부분의 메모리가 낭비된다.- 위의 이유로 배열의 해당 인덱스에 데이터가 존재하는지 파악하는 로직이 추가적으로 필요하다. List? - 배열이 가진 인덱스의 장점을 버리고 대신 빈틈없이 데이터를 적재하는 장점을 취한 자료형. - 순서가 있으며 중복이 허용되는 자료형. 간단한 이해Array(배열) - 주민등록번호와 비교하면 된..
자료구조 - 스택(Stack)이란 스택(Stack) 이란- 스택은 원소의 삽입과 삭제가 "Top"에서만 이루어지도록 제한되어 있는 유한순서 리스트이다.- 삽입 하는 연산을 Push - 삭제 연산을 Pop 이라고 한다. 특징- 한쪽으로만 자료를 넣고 뺄 수 있는 구조로 되어 있어 마지막에 넣은 값이 가장 먼저 출력된다 (LIFO 구조 - Last in First Out(후입선출)) 활용1. 컴퓨터 시스템 - 실행시간 스택이라는 것이 있는데 이 스택의 임무는 호출과 복귀에 따른 실행순서를 정확히 관리 하는 것이다. 서브 프로그램이 호출되면 시스템은 활성화 레코드 라는 것을 만들어 스택의 TOP에 삽입한다 활성화 레코드에는 서브 프로그램의 실행이 끝난뒤 제어를 되돌려 주어야 하는 복귀 주소와, 지역변수 등이 들어 있다 때문에 스택의 TOP에는..
자료구조 - 이진 트리(Binary Tree)란 (이진탐색트리와의 차이점) - 수정중 이진트리(Binary Tree)- 노드의 최대 차수가 2인 트리 편향 이진트리- 말 그대로 노드들이 한쪽으로 편향되어 생성된 이진트리를 말한다 *문제점 1. 탐색속도 저하 : 이진탐색 트리일 경우 편향트리로 형성이 되면 E를 탐색하기 위해 모든 노드를 탐색해야 하므로 연결리스트의 순차탐색과 탐색시간이 동일하다.2. 공간 낭비 : 연결리스트로 구현할 경우는 문제가 없지만 인덱스로 구현할 경우 노드의 개수가 i 라면 최대 2^i 의 공간을 필요로 한다. 포화 이진트리- 높이가 h 일때 최대 노드의 수는 2^(h+1) -1 개이다 이때 이진트리에서 최대 노드의 수를 만족하는 트리를 포화 이진트리라 한다 (ex - 높이가 3인경우 최대 노드 수 : 2^6 - 1 = 15) 완전 이진 트리- 높이가 h인 트리에서..
자료구조 - 트리(Tree)란 트리란- 노드들을 간선으로 연결한 계층형 자료구조- 제일위의 하나의 노드를 루트노드로 하여 나머지 노드들이 간선으로 연결 됨- 하나의 노드는 그자체로 트리이며 루트가 된다용어1. 노드의 차수 - 한노드가 가진 서브트리의 수ex) A의 차수 : 3, B의 차수 : 2, C의 차수 : 0, D의 차수 : 3 2. 리프노드(단말,터미널) - 차수가 0인 노드ex) 리프노드 : E, J, K, L, H, I 3. 자식 노드 - 노드에 연결된 서브트리의 루트노드들ex) A의 자식노드 : B, C, D 4. 부모 노드 - 노드에 연결된 한단계 상위 레벨 노드ex) I의 부모노드 : D 5. 형제 노드 - 부모가 같은 노드ex) G, H, I 는 형제노드 6. 트리의 차수 - 트리노드들의 차수중 최대 차수ex) 트리..
자료구조 - HashMap(해시맵) Hash 자료구조란- Key와 Value를 갖는 자료구조.- 효율적인 검색을 위해 사용된다.- 링크드리스트 같은 자료구조 처럼 처음부터 찾아 나감이 아닌 임의의 길이의 키값을 해시 함수 하여 해당 자료가 위치한 버킷의 주소값을 바로 알아내어 찾아갈 수 있다.그림출처 - Wiki 용어 1. HASH 함수란- 임의의 길이의 데이터를 고정길이의 데이터로 매핑하는 함수 - 아래의 그림을 보면 John Smith 를 해시 함수하여 02라는 해시값을 얻어낸 것을 볼 수 있다. 그림 출처 - https://preamtree.tistory.com/20 문제점 - *비둘기집 원리에 의해 해시함수의 결과값이 중복 될 수 있다. 이는 해시 충돌이라는 문제를 야기한다. 2. HASH란- 해시 함수의 결과값으로 얻어지는 것으로..

티스토리툴바