복잡도

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

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

최대힙, 최소힙

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

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

[자료구조] 덱

개념Rear와 Front 모두에서 데이터를 넣고 뺄 수 있는 자료구조다. 스택과 큐의 장점을 모두 갖고 있다.특징멤버덱도 큐와 마찬가지로 배열이라 연결리스트를 이용해서 구현할 수 있다. 메모리적인 측면에서 봤을 때 원형큐처럼  배열을 활용해서 구현하는 것이 좋다. 두개의 포인터로 원소들을 관리한다.frontrearfront는 덱의 앞을 가리키고 순서상 가장 앞의 원소의 인덱스보다 -1 값을 가진다.rear는 덱의 뒤를 가리키고 순서상 가장 마지막 원소의 인덱스와 같다. 연산덱은 스택과 큐의 장점을 붙인 자료구조다. 덱의 연산은 다음과 같다.pushFront()pushBack()popFront()popBack()원소들이 어느 방향으로 들어오냐에 따라 포인터의 움직임이 다르다.pushFront()의 경우 덱..

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

추상자료형

정의An abstract data type (ADT) is a data type that is organized in such a way that the specification of the operations on the objects is separated from the representation of the objects and the implementation of the operations.💡 데이터와 그 데이터에 적용할 수 있는 연산을 추상적인 수준에서 정의데이터의 구현 세부사항을 숨기고 사용자는 추상자료형이 제공하는 연산을 통해서만 데이터와 상호작용한다. 핵심개념자료형의 추상화데이터의 구현방식의 세부사항에 대해 숨기고 데이터와 관련 된 연산을 통해서만 상호작용할 수 있도록 정의한 데이터타..

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

[자료구조] 큐

개념 정의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 컴퓨터과학/자료구조와 알고리즘
• · 2024. 8. 25.

[알고리즘] 다이나믹 프로그래밍

의미최적부분구조 | 중복하위문제복잡한 문제를 간단한 하위 문제로 나눠 푸는 최적화기법 중에 하나다. 문제가 최적부분구조이고 하위문제들이 중복되는 경우에 동적 프로그래밍 전략을 적용할 수 있다. 최적부분구조란 문제의 최적 해결방법이 하위 문제들의 최적 해결방법으로 구성되는 구조다.용도배낭 문제와 동전 교환문제와 같은 최적화 문제, 최장공통 부분수열과 편집거리와 같은 문자열 처리, 최단경로 문제, 최소 비용경로와 같은 경로 찾기, 최적 자산 배분문제, 작업 스케줄링 문제 등 복잡한 문제를 효율적으로 해결하는 데에 쓰인다. vs 분할정복유사점문제를 나눠서 푼다작은 문제로 쪼갠다작은 문제도 최적화 문제다차이점최적화 문제 등 쪼개진 문제에서 중복된 문제들이 발생한다.구현전략탑다운큰 문제를 작은 문제로 쪼개서 푸는..

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