swk의 지식저장소

힙(Heap) 알아야할 것 1.힙의 개념 2.힙의 삽입 및 삭제 힙은, 우선순위 큐를 위해 만들어진 자료구조다. 먼저 우선순위 큐에 대해서 간략히 알아보자 우선순위 큐 : 우선순위의 개념을 큐에 도입한 자료구조 데이터들이 우선순위를 가지고 있음. 우선순위가 높은 데이터가 먼저 나감 스택은 LIFO, 큐는 FIFO 언제 사용? 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 우선순위 큐는 배열, 연결리스트, 힙으로 구현 (힙으로 구현이 가장 효율적!) 힙 → 삽입 : O(logn) , 삭제 : O(logn) 힙(Heap) 완전 이진 트리의 일종 여러 값 중, 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조 반정렬 상태 힙 트리는 중복된 값 허용 (이진 탐색 트리는 중복값 허용X) 힙 종류 최대 힙(..

스택(Stack) 입력과 출력이 한 곳(방향)으로 제한 LIFO (Last In First Out, 후입선출) : 가장 나중에 들어온 것이 가장 먼저 나옴 언제 사용? 함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법 데이터 넣음 : push() 데이터 최상위 값 뺌 : pop() 비어있는 지 확인 : isEmpty() 꽉차있는 지 확인 : isFull() +SP push와 pop할 때는 해당 위치를 알고 있어야 하므로 기억하고 있는 '스택 포인터(SP)'가 필요함 스택 포인터는 다음 값이 들어갈 위치를 가리키고 있음 (처음 기본값은 -1) private int sp = -1; push public void push(Object o) { if(isFull(o)) { return; } stack[++s..

Array vs ArrayList vs LinkedList 세 자료구조를 한 문장으로 정의하면 아래와 같이 말할 수 있다. Array는 index로 빠르게 값을 찾는 것이 가능함 LinkedList는 데이터의 삽입 및 삭제가 빠름 ArrayList는 데이터를 찾는데 빠르지만, 삽입 및 삭제가 느림 좀 더 자세히 비교하면? 우선 배열(Array)는 선언할 때 크기와 데이터 타입을 지정해야 한다. int arr[10]; String arr[5]; 이처럼, array은 메모리 공간에 할당할 사이즈를 미리 정해놓고 사용하는 자료구조다. 따라서 계속 데이터가 늘어날 때, 최대 사이즈를 알 수 없을 때는 사용하기에 부적합하다. 또한 중간에 데이터를 삽입하거나 삭제할 때도 매우 비효율적이다. 4번째 index 값에 ..

Linked List 연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조 (포인터를 사용해서 연결된다) 각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성 왜 Linked List를 사용하나? 배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함 새로운 요소를 삽입하는 것은 비용이 많이 듬 (공간을 만들고, 기존 요소 전부 이동) 장점 동적 크기 삽입/삭제 용이 단점 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 (이진 검색 수행 불가능) 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요 노드 구현은 아래와 같이 데이터와 다음 노드에 대한..

배열 (Array) C++에서 사이즈 구하기 int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); // 7 1. 배열 회전 프로그램 기본적인 회전 알고리즘 구현 #include using namespace std; //왼쪽으로 한번 회전 void leftRotatebyOne(int arr[], int n){ int temp = arr[0], i; for(i = 0; i < n-1; i++){ arr[i] = arr[i+1]; } arr[i] = temp; } // d만큼 회전 void leftRotate(int arr[], int d, int n){ for(int i = 0; i < d; i++) leftRotatebyOne..