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

알고리즘 목적기준값(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.

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

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

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 19.

[ BOJ / Python ] 1181 - 단어정렬

문제출처https://www.acmicpc.net/problem/1181 걸린시간: 16분 47초 문제분석문자열이 여러개 주어졌을 때 중복되는 문자열은 제거하고 길이가 짧은 순부터 단어가 정렬하되 동일한 길이의 경우, 사전 순으로 정렬해야하는 문제다.최대 2초 내에 최대 20000개의 데이터를 처리해야하므로 알고리즘의 시간복잡도는 O(N^2)을 넘어서는 안된다.  문제접근내 접근from sys import stdininput = stdin.readlinen = int(input())my_words = [input().strip() for x in range(n)]# 사전순으로 정렬하기my_words.sort() # 문자열인 경우 사전순으로 정렬하는 듯 하다.# 길이순으로 정렬하기my_words.sort(..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 12.

알고리즘의 성능측정

성능측정을 해야하는 이유알고리즘이 창의적이거나 좋더라도 실행시간이 느리다면 사용하기가 어렵다. 따라서 알고리즘을 만들고 나면 성능을 측정해야한다.성능측정방법알고리즘의 성능을 분석하는 방법은 지표가 시간이냐, 공간이냐에 따라 달라진다. 시간복잡도알고리즘이 문제를 해결하는 데에 걸리는 시간을 시간복잡도라고 한다. 시간을 기준으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 시간복잡도를 측정한다. 시간복잡도는 빅오표기법으로 표현한다.  공간복잡도알고리즘이 문제를 해결하는 데에 사용하는 메모리량을 공간복잡도라고 한다. 시간을 공간으로 알고리즘을 평가할 경우, 데이터의 크기에 따른 공간복잡도를 측정한다. 공간복잡도도 또한 빅오표기법으로 표현한다. 원본데이터를 기준으로 알고리즘이 문제를 해결하는데 필요한 추가적인..

• format_list_bulleted 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 11.

이진탐색

목적과 특징💡 조사범위를 절반씩 줄여가며 원하는 원소를 찾는 전략두개의 포인터(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 프로그래밍/자료구조와 알고리즘
• · 2024. 8. 10.