[ 자료구조 ] Stack

#1 스택스택은 데이터를 쌓는 형태로 가장 마지막에 들어온 데이터가 가장 먼저 나가는 LIFO(Last in First Out) 자료구조다.#2 연산push스택에 데이터를 삽입하는 연산으로 스택의 가장 위에 데이터를 저장한다.pop스택에 데이터를 삭제하는 연산으로 가장 마지막에 저장한 데이터를 제거한다.peek스택의 가장 위 데이터를 확인한다.#3 스택의 사용파이썬# 빈 스택 초기화stack = []print("stack:", stack)# 스택에 원소 추가stack = [1, 2, 3]stack.append(4)print("stack:", stack)# 스택 원소 제거stack = [1, 2, 3]stack.pop()print("stack:", stack)# 스택 원소 찾기stack = [1, 2, 3..

• format_list_bulleted IT 취업 준비
• · 2024. 9. 26.

최대힙, 최소힙

힙힙은 완전이진트리로 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조다. 우선순위큐를 구현하는 데 자주 사용된다.힙은 삽입연산과 삭제연산이 있다.삽입연산데이터 삽입은 힙의 맨 끝에서 이뤄진다. 부모노드와 우선순위를 비교해 부모보다 자식이 높으면 부모와 자식의 위치를 바꾸면서 루트노드까지 비교한다.삽입연산의 과정이진트리의 맨 마지막 자리에 노드를 추가한다.부모노드와 우선순위를 비교 후 자식 노드가 우선순위가 높으면 부모노드와 자리를 교체한다.부모노드가 우선순위가 높을 때까지 2를 반복한다.삭제 연산데이터 삭제는 힙의 루트노드에서 이뤄진다. 루트노드를 삭제한 후 가장 마지막에 추가한 노드를 루트노드의 위치로 이동한다. 이동한 노드와 자식노드의 우선순위를 비교해 힙을 재정렬한다.삭제연산의 과정트리의 마지막..

• format_list_bulleted IT 취업 준비
• · 2024. 9. 24.

[자료구조] 큐

개념 정의FIFO(First in First Out)의 자료구조 Front: 가장 처음에 들어온 원소의 인덱스 - 1Rear: 가장 마지막에 들어온 원소를 가리키는 인덱스capacity: 큐가 최대로 담을 수 있는 원소의 개수(배열의 크기 - 1)size: 현재 큐에 담겨져 있는 원소의 개수(size = rear - front)enqueue: 큐에 데이터를 넣는 연산(rear = (rear + 1) % capacity)dequeue: 큐에서 데이터를 빼는 연산(front = (front + 1) % capacity)Front 와 Rearfront, rear 두 개의 인덱스를 사용해서 전체 배열의 시작과 끝을 추적한다.front와 rear의 값이 동일할 경우, 해당 큐는 비어있다.front는 가장 먼저 추..

• format_list_bulleted IT 취업 준비
• · 2024. 8. 25.

[자료구조] Stack

자료구조를 사용하는 이유데이터는 구조화 된 여부에 따라 정형, 비정형으로 구분한다. 컴퓨터 시스템에서 데이터를 효율적으로 다루기 위해서는 데이터가 구조화되어야한다. 데이터를 효율적으로 저장하고 관리하기 위해 구조화 된 형태를 자료구조라고 한다. 배열, 스택, 큐 모두 자료구조이다. 자료구조마다 각기 다른 방식으로 데이터를 관리하고 처리한다. 스택개념스택은 후입선출원칙(LIFO)에 따라 데이터를 관리한다. 데이터를 넣는 순서와 반대로 데이터가 꺼내진다. 즉, 가장 마지막에 넣은 데이터가 가장 먼저 나오게 된다.스택에서 가장 마지막에 들어간 데이터의 위치를 top이라고 한다.스택은 push, pop, peek 연산이 있다. push 연산은 데이터를 넣는다. pop은 top에 있는 데이터를 제거한다. peek..

• format_list_bulleted IT 취업 준비
• · 2024. 8. 19.

이진탐색

목적과 특징💡 조사범위를 절반씩 줄여가며 원하는 원소를 찾는 전략두개의 포인터(left, right)를 활용해 조사범위를 설정한다찾고자하는 원소와 middle 값의 크기를 비교해서 조사범위를 조정한다middle 값이 찾고자하는 원소보다 큰 경우, 왼쪽 조사를 위해 right의 인덱스를 내려서 갱신middle 값이 찾고자하는 원소보다 작은 경우, 오른쪽 조사를 위해 left의 인덱스를 올려서 갱신찾고하는 값이 있는 경우에 해당 원소의 인덱스를, 없으면 -1을 반환한다.구현코드C++int BinarySearch(int *arr, int n, int x) // 이진 탐색{ int left = 0; int right = n - 1; while (left x) { // REVIEW: 찾고자하는..

• format_list_bulleted IT 취업 준비
• · 2024. 8. 10.

swap 알고리즘

개요💡두 변수의 값의 교체알고리즘에서 swap은 두 변수의 값들을 서로 교체하는 과정이다. swap은 여러 알고리즘에서 기본 연산으로 사용된다. 예를 들어 정렬 알고리즘에서는 요소를 올바른 위치로 이동시키기 위해 swap 연산을 사용한다. 기본개념1) 임시변수를 사용하는 경우temp = aa = bb = temp2) XOR 연산을 하는 경우a = a ^ bb = a ^ ba = a ^ b3) 덧셈, 뺄셈을 하는 경우a = a + bb = a - ba = a - b Swap의 구현1) 포인터를 사용하는 경우void swap(int *i, int *j){ int temp = *i; *i = *j; *j = temp;}2) 레퍼런스를 사용하는 경우void swap(int &i, int &j){ int tem..

• format_list_bulleted IT 취업 준비
• · 2024. 8. 2.