알고리즘(18)
-
[알고리즘]정렬-계수 정렬(Counting Sort)
숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)기본적인 정렬 알고리즘 O(n^2)1.선택정렬2.버블정렬3.삽입정렬고급 정렬 알고리즘 O(n*logn)1.병합정렬2.퀵정렬3.힙정렬특수 정렬 알고리즘 O(n)1.계수정렬2.기수정렬 계수 정렬(Counting Sort) 이란계수 정렬(Counting Sort)은 정수나 정수로 변환할 수 있는 자료에 대해서만 적용 가능한 효율적인 정렬 알고리즘입니다. 이 알고리즘의 작동 방식은 입력의 범위가 제한적일 때 매우 효과적이며, 시간 복잡도는 O(n)입니다. 계수 정렬의 기본 아이디어는 각 숫자를 계산(count)하고, 이를 기반으로 정렬된 배열을 생성하는 것입니다. 계수 정렬(Counting Sort) 과정계..
2024.01.13 -
[백준][c++] 12738번: 가장 긴 증가하는 부분 수열 3
문제 해석 주어진 수열 안에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 입니다. 풀이 먼저, 숫자의 개수 N을 입력받습니다. N개의 숫자를 입력받아 numbers 벡터에 저장합니다. lis라는 벡터를 생성하고 첫번째 숫자를 추가합니다. 이 벡터는 가장 긴 증가하는 부분 수열을 저장하는 데 사용됩니다. numbers 벡터의 두 번째 원소부터 마지막 원소까지 순회하며, 현재 숫자가 lis의 마지막 원소보다 크면 lis에 추가합니다. 이는 현재 숫자가 lis에 포함될 수 있음을 의미합니다. 만약 현재 숫자가 lis의 마지막 원소보다 작다면, 현재 숫자가 들어갈 수 있는 lis 내의 위치를 이진 탐색으로 찾아서 그 위치의 값을 현재 숫자로 업데이트합니다. 이는 lis를 최대한 작은 값으로 유지하면서 길..
2024.01.10 -
[알고리즘]정렬-힙정렬(Heap Sort)
숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)기본적인 정렬 알고리즘 O(n^2)1.선택정렬2.버블정렬3.삽입정렬고급 정렬 알고리즘 O(n*logn)1.병합정렬2.퀵정렬3.힙정렬특수 정렬 알고리즘 O(n)1.계수정렬2.기수정렬 정렬(Heap Sort)이란힙 정렬(Heap Sort)은 완전 이진 트리를 바탕으로 한 정렬 방식입니다. 힙 정렬은 이진 힙(이진 트리의 한 종류)의 특징을 활용하여 정렬을 수행하며, 이진 힙에는 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다.힙 정렬의 기본 원리는 다음과 같습니다: 1. 먼저, 정렬되지 않은 배열을 최대 힙으로 변환합니다. 최대 힙이란 부모 노드가 자식 노드보다 크거나 같은 완전 이진 트..
2024.01.10 -
[백준][c++] 1918번: 후위표기식
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 문제 해석 중위 표기식을 후위표기식으로 변환하여 출력하는 문제입니다. 후위 표기식변환은 스택(stack)을 이용합니다. 풀이 각 문자에 대해 다음과 같은 작업을 수행합니다 문자가 문자나 숫자(즉, 피연산자)인 경우, 결과 문자열에 바로 추가합니다. 문자가 여는 괄호 '('인 경우, 이를 스택에 넣습니다. 문자가 닫는 괄호 ')'인 경우, 스택에서 여는 괄호 '('가 나올 때까지 문자를 pop하..
2024.01.08 -
[알고리즘]정렬-퀵정렬(Quick Sort)
숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)기본적인 정렬 알고리즘 O(n^2)1.선택정렬2.버블정렬3.삽입정렬고급 정렬 알고리즘 O(n*logn)1.병합정렬2.퀵정렬3.힙정렬특수 정렬 알고리즘 O(n)1.계수정렬2.기수정렬퀵정렬이란퀵 정렬(Quick Sort)은 분할 정복 방식의 효율적인 정렬 알고리즘 중 하나입니다. 퀵 정렬은 배열을 두 부분으로 분할하고, 각 부분을 재귀적으로 정렬하여 전체 배열을 정렬합니다. 분할 시 기준이 되는 '피벗'을 선택하고, 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 이동합니다. 퀵 정렬의 시간 복잡도는 평균적으로 O(n log n)입니다. 하지만 최악의 경우(이미 정렬된 배열 등) O(n^2)이 될 수 있..
2024.01.07 -
[백준][c++] 11003번: 최솟값 찾기
문제 해석 각 슬라이딩 윈도우 크기 내에서 최소값을 출력하는 문제입니다. 풀이 벡터와 덱을 이용해 해결했습니다. 각 D(i)에 대해 다음을 반복합니다. 현재 추가되는 A(i)와 dq.back(덱에서 가장 큰 수)를 비교하여 A(i)가 더 작다면 dq.back을 pop함 A(i)를 인덱스와 함께 back에 추가 dq.front가 윈도우 크기를 벗어났다면 pop함 dq.front를 출력 코드 #include #include #include using namespace std; int main() { //입출력 최적화 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //입력부 int n,l; cin >> n >> l; vector a(n); ..
2024.01.05