[ 자료구조 ] 힙(heap)

개념특징힙은 영어로 ‘더미’다. 컴퓨터공학에서 힙은 데이터 더미를 완전이진트리 구조로 표현하여 최대값 또는 최소값을 빠르게 찾을 수 있는 자료구조다. 우선순위큐를 구현하는 데 자주 사용된다. 힙은 최대힙과 최소힙이 있다.최대힙최대힙은 루트노드가 최대값이다. 부모노드의 값이 자식노드의 값보다 커야한다.최소힙최소힙은 루트노드가 최소값이다. 부모노드의 값이 자식노드의 값보다 작아야한다.연산힙 연산이 끝난 후에도 완전이진트리 구조를 유지해야한다. 최대힙 기준으로 삽입연산과 삭제연산을 설명하면 다음과 같다.삽입연산데이터 삽입은 힙의 맨 끝에서 이뤄진다. 부모노드와 우선순위를 비교해 부모보다 자식이 높으면 부모와 자식의 위치를 바꾸면서 루트노드까지 비교한다.1. 이진트리의 맨 마지막 자리에 노드를 추가한다.2. 부..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 7.

[ 알고리즘 ] 기준값에 의한 분할

알고리즘 목적기준값(pivot, 피벗)을 기준으로 배열을 분할하는 알고리즘이다. 배열을 피벗보다 낮은 영역과 피벗보다 큰 영역으로 나눈다. 영역을 나눈 후에 피벗을 자기 자리에 배치한다.기준값을 기준으로 배열을 분할한다고 해서 반드시 정렬되어야 하는 것은 아니다.시간복잡도는 Θ(N)이다.알고리즘 구현동작과정pivot을 정한다pivot보다 작은 값을 발견할 경우, 왼쪽 영역을 확장하고 자리를 교체한다.모든 데이터를 순회했으면 pivot을 배치한다.구현#include #include using namespace std;void Print(vector &arr) { for (int i = 0; i arr = {5, 2, 7, 3, 8, 5, 6, 4}; // vector arr = { 2, 8, ..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 9. 28.

분할정복으로 중복 데이터 개수 찾기

문제데이터가 정렬 된 배열에서 특정 값의 개수를 찾는 문제였다. 값은 중복될 수 있다. 접근법선형탐색이분탐색데이터가 정렬되어 있는 형태였기 때문에 선형탐색보다 이분탐색을 하기로 하였다. 그런데 이번 문제의 경우 데이터의 중복이 존재하는 경우였다. 따라서 이분탐색으로 값의 위치를 찾되, 찾은 위치를 기준으로 값이 존재하는 위치 구간을 찾기로 하였다.구현값의 위치 찾기이분탐색을 적용한다.int binarySearch(const vector &arr, int x) { int left = 0; int right = arr.size(); int check = -1; while (left x) { right = mid - 1; } else if (arr[mid..

• format_list_bulleted 기록/기타
• · 2024. 9. 27.

병합정렬 디버깅

디버깅프로그램을 짜는 것보다 중요한 것은 프로그램이 원하는 대로 돌아가는지 확인하는 과정인 것 같다. 코드를 작성하더라도 반드시 내 의도대로 돌아가는 보장이 없다. 그래서 디버깅을 해야한다. 디버깅을 하면 내 논리가 어디서 막히는 지 확인할 수 있기 때문이다.디버깅도 상황에 따라 다르게 쓰고 있다. 변수가 뭔지 해석할 때는 출력코드를 사용하고 반복문이 어떻게 작동하는지 확인할 때는 디버깅툴을 사용한다. 코테도 봐야하는 상황을 고려할 때 출력코드를 사용하는 것에 익숙해져야겠다.병합정렬을 구현하는데 합병 로직이 제대로 작동하지 않았다.void Merge(vector &a, int lo, int mid, int hi) { cout 구간: lo ~ mid, mid+1 ~ hi // c..

• format_list_bulleted 기록/기타
• · 2024. 9. 27.

[ C++ ] 문자열 패딩을 만드는 법

예제문자열 “123” 앞에 “0” 패딩을 3개 붙이기string a("123");string b = string(3, '0');int paddings = 4;a.insert(0, b); // "000123": 첫째 인수는 삽입하고자하는 위치, 두번째는 삽입하려는 문자열!a.insert(a.size(), string(paddings, '0')); // "0001230000"디버깅아래의 함수를 헷갈리면 안된다. 2번째 매개변수는 문자열이 아니라 문자 리터럴을 사용해야한다. string b = string(3, '0'); // 좋은 예안그러면 문자열의 null캐릭터까지 추가가 되어 패딩으로서의 역할을 하지 못한다.string(paddings, "0"); // 널캐릭터까지 추가되어 패딩이 망가진다.

• format_list_bulleted 프로그래밍 언어/C++
• · 2024. 9. 26.

[ 자료구조 ] 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 컴퓨터과학/자료구조와 알고리즘
• · 2024. 9. 26.