선형시간으로 최대값과 최소값 찾기

문제배열을 정렬을 하지 않고도 선형시간으로 최대값과 최소값을 찾을 수 있다.접근법배열의 크기가 짝수인지 또는 홀수인지에 따라 나뉜다. 홀수인 경우에는 추가작업이 필요하다. 공통 접근법은 다음과 같다.배열의 인덱스 0번과 1번 자리를 각각 최소자리와 최대자리로 지정한다.배열을 2만큼씩 간격으로 i번째와 i+1번째의 값의 크기를 비교한다. i번째가 더 크다면 두 값의 위치를 교체한다.0번째 값은 i번째와 비교하여 0번째가 값이 더 큰 경우에 위치를 교체한다.1번째 값은 i+1번째와 비교하여 1번째가 값이 더 큰 경우에 위치를 교체한다.배열의 크기가 짝수인 경우에 배열 전부에 위의 과정을 반복하고 홀수인 경우에는 마지막 원소를 제외하고 실행한다.짝수 크기의 배열은 0번째가 최소값, 1번째가 최대값이 된다.홀수..

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

[ 자료구조 ] 힙(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.

[ 자료구조 ] 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.

복잡도

시간과 공간프로그램을 실행하기 위해서는 시간과 메모리가 필요하다. 같은 기능을 수행하는 프로그램 둘이 있을 때 시간과 메모리를 덜 소모할수록 효율적인 프로그램이다.복잡도복잡도란 작성한 알고리즘이 효율적인지 시간, 공간적으로 효율적인지를 판단하는 기준이다. 알고리즘의 효율성을 정량화한다. 시간복잡도는 알고리즘의 실행시간을 정량화한 것이다. 공간복잡도는 알고리즘의 실행에 필요한 메모리량을 정량화한 것이다.빅오표기법빅오표기법은 알고리즘의 복잡도를 표기하는 방법 중에 하나로 최악의 경우의 상관관계를 표현한다. 입력 데이터 대비 함수를 실행하는 데에 필요한 비용(시간, 공간)의 상관관계를 수식의 최고차항으로 표현한다.그래프는 시간복잡도를 표현한 것이다. 최고차항이 커질수록 동일 입력 데이터 대비 소요되는 시간이 ..

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

최대힙, 최소힙

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

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