Brute force Study

선택 문제n개의 숫자들 중에서 k 번째로 작은 숫자를 찾는 문제이다.선택 문제 해결 방법간단한 방법 1.  최소 숫자를 k번 찾는다. 단 최수 숫자를 찾은 뒤에는 입력에서 최수 숫자를 제거한다숫자를 제거하는 과정에서 추가 수행시간 또는 추가 메모리가 필요하다O(kn)간단한 방법 2 : 숫자들을 정렬한 후 k 번째 숫자를 찾는다.O(nlogn)의 수행 시간이 필요하다k가 작을 경우 최소 숫자를 k번 찾는 것이 유리하고, 그렇지 않은 경우 정렬하여 찾는 것이 유리하다이진탐색 아이디어를 활용해보자이진 탐색에서는 정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써 입력을 1/2로 나눈 두 부분 중에서 한 부분만 검색했다.분할 후 각 그룹의 크기를 알아야 k번째 작은 숫자가 어느 그룹에 있는지를 알..

퀵 정렬이란?이전 챕터에서 본 병합 정렬의 목적이 대용량의 데이터를 정렬하는 것이라면, 퀵 정렬은 평균 실행 시간을 줄이는 것이 목표이다.분할 정복 접근법을 이용하는 기본 아이디어는 병합 정렬과 동일하다. 다만 퀵 정렬의 핵심은 병합이 아니라 분할이다.퀵 정렬은 문제를 2개의 부분문제로 분할하는데, 각 부분문제의 크기가 일정하지 않은 형태의 비균등 분할 정복 알고리즘이다퀵 정렬의 분할 연산 방법입력 배열이 주어지고, 입력 배열 중 피벗(pivot) 원소 P를 선택했을 경우, 퀵 정렬을 위한 분할 연산은 다음 두 단계로 이루어진다 입력 배열을 두 개의 부분 배열 L과 R로 나눈다. L은 입력 배열에서 P보다 작거나 같은 원소를 포함하는 부분 배열이고, R은 입력 배열에서 P보다 큰 원소를 포함하는 부분 배..

분할 정복을 이용한 정렬 알고리즘유명한 알고리즘 문제 중의 하나인 정렬(sorting)을 분할 정복으로 구현하는 방법에 대해 알아보자 정렬 알고리즘 구현에 있어 필요한 요구사항모든 데이터 타입에 대해 동작해야 한다. 심지어 C++ 구조체, 클래스에 대해서도 서로 다른 멤버를 기준으로 정렬할 수 있어야 한다많은 양의 데이터를 처리할 수 있어야 한다.점근적 시간 복잡도 측면이나 실제 동작 시에 빠르게 동작한다현실적으로 두 번째와 세 번째 요구사항을 동시에 만족하기는 어렵다. 두 번째 요구사항은 외부 정렬(external sorting), 즉 컴퓨터의 메모리에 데이터가 상주하지 않은 상태에서 수행되는 정렬을 필요로 한다.외부 정렬 알고리즘은 실행 중 임의 시점에서 전체 데이터의 일부만을 메모리에 올려놓고 동작..

C++에서 istream, ostream, sstream는 모두 표준 라이브러리에서 제공하는 스트림 클래스입니다. 이 클래스들은 입출력 작업을 추상화하여 파일, 콘솔, 문자열 등을 손쉽게 다룰 수 있도록 도와줍니다. 각각에 대해 자세히 설명하겠습니다.1. istreamistream은 입력 스트림을 나타내는 클래스입니다. 이 클래스는 데이터 입력을 위한 다양한 메소드를 제공합니다. istream의 주요 역할은 데이터의 입력을 관리하는 것입니다.주요 기능연산자 오버로딩 (>>, stream insertion operator): 데이터를 입력받을 때 사용하는 연산자입니다.ex) cincin은 c++ 표준 라이브러리에서 제공하는 객체로, istream 클래스의 객체임int x;std::cin >> x; // 콘..

(알고리즘 코드를 보다가 GPT를 통해서 얻은 답변을 따로 정리해둔 게시글이에요) std::distance()와 std::advance() 함수는 C++ 표준 라이브러리에서 제공하는 반복자 관련 함수입니다. 이 두 함수는 반복자를 다루는 데 유용하게 사용될 수 있습니다.std::distance()std::distance(first, last) 함수는 두 개의 반복자 first와 last 사이의 거리를 계산하여 반환합니다. 이 함수는 다음과 같은 형태로 사용됩니다:template typename std::iterator_traits::difference_typedistance(InputIt first, InputIt last);first: 거리를 계산할 첫 번째 반복자last: 거리를 계산할 두 번째 반복..

이진 검색(binary search) (a.k.a 이진 탐색) 일반적인 검색 문제정렬되어 있는 정수 시퀀스가 있고, 여기에 숫자 N이 있는지 확인하려고 한다.이러한 검색 문제는 두 가지 방법으로 접근할 수 있다.  선형 검색(linear search)시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지를 확인하는 방식이다.bool linear_search(int n, vector& sequence) { for (auto i : sequence) { if (i == n) { return true; } } return false;} 장점 : 입력 시퀀스의 정렬 여부와 상관 없이 항상 잘 동작한다단점 : 효율적이지 않음.O(N)주어진 배열이 정렬되..

분할 정복 설계 패러다임효율적인 알고리즘을 설계하기 위한 일반적인 접근 방법이 개발되어 다양한 문제 해결에 사용되고 있다.분할 정복(divide-and-conquer)은 가장 널리 사용되는 알고리즘 설계 패러다임 중 하나이다.분할 정복 알고리즘이란?주어진 문제를 작은 부분 문제로 나누고, 나줘진 각 부분 문제의 솔루션을 구하고, 각 부분 문제 솔루션을 합쳐서 전체 문제에 대한 솔루션을 구하는 방식binary search(이진 탐색), quick sort(퀵 정렬), merge sort(병합 정렬), matrix mulitplication(행렬 곱셈), Fast Fourier Trnasform(고속 푸리에 변환), skyline algorithm(스카이라인 알고리즘) 등에서 사용되는 패러다임이다.분할 정복..

Introduction of Algorithm자료 구조 : 다양한 방식의 데이터 저장 방식을 의미하고, 그 안에 저장된 데이터에 접근하는 데 필요한 비용을 결정알고리즘: 주어진 문제가 있을 때, 데이터에 대한 정확한 정의와 데이터 변환 순서에 대한 일련의 명령알고리즘의 좋고 나쁨은 알고리즘 동작의 효율성에 의해 결정된다. 또는 알고리즘 수행에 필요한 명령의 개수도 판단의 근거가 될 수 있다.알고리즘 문제 분류(계산 복잡도 기준)P 문제: 다항 시간 알고리즘을 이용하여 솔루션을 구할 수 있는 문제NP 문제: 특정 솔루션을 다항 시간으로 검증할 수는 있지만 알려진 다항 시간 솔루션은 없는 경우EXPTIME 문제(지수 시간 문제): 입력 크기에 대한 지수 함수 형태의 시간 복잡도 솔루션을 갖는다PSPACE(다..