분류 전체보기(25)
-
[알고리즘] 선택 알고리즘 - 선형 시간 선택 알고리즘(QuickSelect)
숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 선택 알고리즘이란 선택 알고리즘은 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 알고리즘을 의미합니다. 이 알고리즘은 다양한 방법으로 구현될 수 있습니다. 선형 시간 선택 알고리즘은 최악의 경우에도 O(n)의 시간 복잡도를 가지는 알고리즘입니다. 이 알고리즘의 대표적인 예는 QuickSelect입니다. QuickSelect는 QuickSort 알고리즘을 기반으로 하며, 분할-정복 방식을 사용합니다. 피벗을 선정하고 이를 기준으로 리스트를 두 부분으로 나눈 후, k가 어느 부분에 있는지에 ..
2024.02.26 -
[백준][c++] 2206번: 벽 부수고 이동하기
2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 해석 N*M 배열의 1,1 에서 N,M까지의 최단경로를 찾아내는 문제 0은 벽이 없고 1은 벽이 있는 칸 벽은 최대 한번까지 부술수 있다. 풀이 큐를 이용한 BFS(너비 우선 탐색)으로 최단경로를 찾았습니다. 코드 #include #include #include #include #include using namespace std; //입력부 static int n,m; static int least = INT_MAX; //이동 횟수..
2024.02.19 -
[알고리즘]정렬-기수 정렬(Radix Sort)
숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)기본적인 정렬 알고리즘 O(n^2)1.선택정렬2.버블정렬3.삽입정렬고급 정렬 알고리즘 O(n*logn)1.병합정렬2.퀵정렬3.힙정렬특수 정렬 알고리즘 O(n)1.계수정렬2.기수정렬 기수 정렬(Radix Sort)은 정수들의 정렬을 위해 사용하는 알고리즘 중 하나입니다. 비교 기반의 정렬 알고리즘이 아니라, 각 숫자의 자리수를 기준으로 정렬을 수행하는 방식을 사용합니다. 기수 정렬의 시간 복잡도는 O(NK)입니다. 여기서 N은 정렬할 숫자의 개수, K는 숫자의 최대 자리수입니다. 따라서 데이터의 개수가 많고, 숫자의 범위가 클 경우에는 다른 정렬 알고리즘에 비해 빠른 성능을 보여줍니다.하지만 기수 정렬..
2024.02.14 -
[알고리즘]정렬-계수 정렬(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