알고리즘 복잡도

알고리즘 복잡도 알고리즘 복잡도는 시간 복잡도와 공간 복잡도 두 개로 구분이 된다. # 시간 복잡도 시간 복잡도는 알고리즘의 입력 데이터에 대해 수행하는 연산 횟수의 총합을 나타내며, 대개는 입력 데이터의 크기에 대한 함수로 나타난다. 이 함수를 T(n)으료 표현할 때, 알고리즘의 시간 복잡도는 O(T(n))과 같이 표현이 된다. 여기서 O는 최악의 경우의 복잡도를 나타내는 빅오 표기법이다. 빅오 외 표기법 빅 오메가 (Big Omega) 표기법 : Ω(n) 빅 오메가 표기법은 최악의 경우를 나타내는 빅오 표기법과 달리, 최선의 경우를 나타낸다. 즉, 알고리즘의 실행 시간이 최소한 이 정도 이상이라는 것을 나타낸다. 빅세타 (Big Theta) 표기법 : Θ(n) 빅세타 표기법은 빅오 표기법과 빅 오메가..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 4. 4.
• textsms

최단 경로, 최소 신장

최단 경로 알고리즘 최단 경로 알고리즘은 두 개의 정점 사이의 가장 짧은 경로를 찾는 알고리즘이다. 이 알고리즘은 그래프의 가중치를 이용하여 경로를 선택하며, 가중치는 간선에 할달된 비용을 의미한다. 그래프에서 가장 짧은 경로를 찾는 것은 네트워크 라우팅, GPS 네비게이션, 물류 최적화 증 다양한 분야에서 활용 된다. 가장 대표적인 최단 경로 알고리즘으로는 다익스트라, 벨만-포드, 플로이드-워셜 알고리즘이 있다. # 다익스트라(Dijkstra) 출발점에서 목표점까지의 최단 경로를 구하는 알고리즘을 말한다. 한 노드에서 다른 모든 노드로의 최단 경로를 구하는 데 사용한다. 간선에 음의 가중치가 없어야 한다. 그리디 + DP 형태를 가지고 있다. 알고리즘 복잡도 : O(ElogN) E: 간선, N:노드 순..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 4. 3.
• textsms

분할정복, 다이나믹, 백트래킹

분할정복(Divide and Conquer) 분할정복(Divide and Conquer)은 컴퓨터 알고리즘디자인 패러다임 중 하나로, 주어진 문제를 작은 부분 문제들로 분할하고, 각 부분 문제를 해결하여 전체 문제를 해결하는 알고리즘이다. 각 부분 문제의 해결 과정이 서로 영향을 미치지 않아야 하며, 이를 "서로 disjoint"하다고 한다. 분할정복 알고리즘은 일반적으로 아래와 같은 세 단계로 구성이 된다. 분할(Divide) : 해결하고자 하는 문제를 작은 부분 문제들로 분할한다. 이 단계에서는 주로 문제의 크기를 절반으로 중리거나, 부분 문제들로 분할하는 등의 작업을 수행한다. 정복(Conquer) : 분할된 부분 문제들을 재귀적으로 해결한다. 부분 문제들이 충분히 작아지면, 직접적인 해결이 가능해..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 4. 2.
• textsms

투 포인터, 그리디

투 포인터(Two Pointer) 투 포인터(Two Pointer) 알고리즘은 리스트나 배열과 같은 순차 자료 구조에서 두 개의 포인터를 이용하여 원하는 구간을 탐색하는 알고리즘이다. 일반적으로, 리스트나 배열에서 연속된 구간을 탐색할 때, 시작 인덱스와 끝 인덱스를 정하여 반복문을 사용하여 구간을 탐색한다. 그러나 투 포인터 알고리즘은 시작 포인터와 끝 포인터 두 개의 포인터를 이용하여 구간을 탐색한다. 투 포인터 알고리즘은 두 개의 포인터를 이용하여 구간을 효율적으로 탐색할 수 있다. 시작 포인터와 끝 포인터를 이용하여 구간을 지정하고, 이 구간을 이동하면서 원하는 조건에 맞는 값을 찾아나갈 수 있다. 작동 방식 예를 들어, 오름차순으로 정렬된 정수 배열에서 두 수의 합이 주어진 값과 같은 원소의 인..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 4. 1.
• textsms

이진탐색(Binary Search)

이진탐색 이진탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾기 위한 알고리즘이다. 이 알고리즘은 반복적인 비교를 통해 원하는 값을 찾아낸다. 이진탐색은 배열이 정렬되어 있어야만 사용할 수 있다. 정렬되어 있지 않은 배열에서는 값을 찾을 수 없다. 이 알고리즘은 정렬된 배열에서 원하는 값을 빠르게 찾아낼 수 있기 때문에, 대부분의 프로그래밍 언어에서 기본적으로 제공되는 정렬 알고리즘과 함께 많이 사용된다. 이진탐색의 시간 복잡도는 O(log n)이다. 따라서 배열의 크기가 매우 크더라도, 비교횟수가 크게 늘어나지 않는다. 이는 다른 탐색 알고리즘들과 비교 했을 때 매우 효율적인 알고리즘이다. 작동방식 배열의 중간 값을 선택. 중간 값이 찾고자 하는 값다 같다면 탐색을 종료. 중간 값이 찾..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 4. 1.
• textsms

정렬(Sort)

정렬(Sort) 특정한 값을 기준으로 데이터를 순서대로 배치하는 방법을 말한다. 구현 난이도는 쉽지만, 속도는 느린 알고리즘 버블 정렬, 삽입 정렬, 선택 정렬 구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬 하이브리드 정렬 팀 정렬, 블록 병합 정렬, 인트로 정렬 기타 정렬 알고리즘 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort)는 인접한 두 개의 요소를 비교하면서 정렬하는 알고리즘이다. 두 개의 요소를 비교하면서 더 작은 값을 앞으로 이동시키고, 큰 값을 뒤로 이동시키는 방식으로 정렬을 수행한다. 이를 배열 끝까지 반복하면서 정렬을 완성한다. 이러한 정렬되는 모습이 거품이 수면위로 ..

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 31.
• textsms