Notepad

C++/Algorithm

[Algorithm/C++] 에라토스테네스의 체 - 특정 범위 수 소수 판별

1. 설명 에라토스테네스의 체는 소수를 찾는 방법 중 하나로서 수학자인 에라토스테네스가 발견하여 에라토스테네스의 체라고 한다. 에라토스테네스의 체는 소수를 판별해야 하는 상황 중 "2부터 N까지 수 중 소수 찾기"와 같이 특정 범위 수 중에서 소수를 찾는 데 사용할 수 있는 효율적인 방법이다. 원리를 요약하여 설명하자면 1. N+1의 크기를 갖는 bool 값을 저장할 배열 혹은 vector를 생성하고 True로 초기화한다. 크기를 N+1로 해주는 이유는 index로 보았을 경우 0부터 시작하여 N-1까지이기 때문에 N 위치의 저장하기 위하여 N+1 크기로 생성하는 것이다. 2. i=2부터 반복문을 시작하며 2의 배수들은 곧 2를 약수로 갖는다는 의미로서 소수가 아니다. 따라서 2의 배수 index 값들을..

C++/Algorithm

[Algorithm/C++] 퀵 선택(Quick Select) - N 번째 수 구하기

1. 설명 퀵 선택(Quick Select)이란 퀵 정렬을 응용하여 리스트를 정렬하지 않아도 리스트에서 N번 째 작은 값 혹은 큰 값을 구하는 방법이다. 퀵 정렬이란 분할과 재귀를 사용하여 빠르게 정렬을 할 수 있는 방법으로 자세한 내용은 아래 글을 참고하면 된다. [Algorithm/C++] 퀵 정렬(Quick Sort) - 분할과 재귀 1. 설명 퀵 정렬(Quick Sort)란 분할과 재귀를 사용하여 최종적으로 정렬된 리스트를 얻는 정렬 방식 중 하나이다. 여기서 분할이란 처음의 1개 문제가 있었다면 이를 2개 혹은 3개처럼 더욱 작은 문 notepad96.tistory.com 앞서 퀵 정렬을 응용한다고 하였지만 정확하게 말하자면 퀵 정렬을 수행하는 것은 아니다. 오히려 퀵 정렬이라기보다는 이진 검색..

C++/Algorithm

[Algorithm/C++] 퀵 정렬(Quick Sort) - 분할과 재귀

1. 설명 퀵 정렬(Quick Sort)란 분할과 재귀를 사용하여 최종적으로 정렬된 리스트를 얻는 정렬 방식 중 하나이다. 여기서 분할이란 처음의 1개 문제가 있었다면 이를 2개 혹은 3개처럼 더욱 작은 문제로 나누어서 문제를 각각 해결한 후 합하여 처음의 복잡하였던 1개의 문제의 해답을 구하는 방법이다. 재귀란 간단하게 함수 속에서 해당 함수를 호출하는 형태라고 할 수 있으며, 계속 반복하여 실행되기 때문에 반복하여 실행되는 중 실행을 중단하는 조건을 포함해야만 하며 그렇지 않으면 무한 루프에 빠지게 된다. 퀵 정렬은 분할과 재귀를 사용한다고 하였는데, 우선 분할을 수행하여 동일한 형태이지만 작은 문제 2개로 만들고 동일한 형태이기 때문에, 재귀를 통하여 나누어진 작은 문제에서도 앞서 수행한 분할 작업..

C++/Algorithm

[Algorithm/C++] 삽입 정렬(Insertion Sort) - 비교 후 삽입

1. 설명 삽입 정렬(Insertion Sort)란 리스트의 값들을 순차적으로 인접한 원소와 비교를 하여 위치를 교환해주며 정렬을 하는 방법 중 하나이다. 한 원소를 선택하여 위치를 변경해준다는 점에서 선택 정렬(Selection Sort)과 유사하다고 할 수도 있으며 인접한 원소 간 비교를 통하여 위치를 교환해주므로 거품 정렬(Bubble Sort)과도 유사하다고 할 수도 있다. 동작 예시를 살펴보면 오름차순 정렬을 위해서는 리스트의 첫 번째 위치에는 리스트에서 가장 작은 값이 위치하여야 한다. 시작은 두 번째 Index부터 시작하며 왼쪽에 있는 원소들과 비교를 통하여 더 큰 값이 왼쪽에 위치하고 있다면 교환하는 작업을 수행한다. 이 작업을 반복하여 수행함으로써 가장 작은 원소는 가장 왼쪽의 위치하게 ..

C++/Algorithm

[Algorithm/C++] 선택 정렬(Selection Sort) - 선택하여 교환

1. 설명 선택 정렬(Selection Sort)란 리스트를 순차적으로 반복하면서 해당 위치에 해당하는 값을 탐색 후 선택하여 교체함으로써 정렬을 하는 정렬 방법 중 하나이다. 동작 예시를 살펴보면 오름차순 정렬을 위해서는 리스트의 첫 번째 위치에는 리스트에서 가장 작은 값이 위치하여야 한다. 따라서 탐색을 통하여 리스트에서 가장 작은 값의 인덱스를 선택한 후 첫 번째에 있는 값과 교환을 한다. 이 같은 과정을 한 번 수행하게 되면 리스트의 첫 번째 원소는 정렬이 된 상태가 되는 것이다. 이 과정을 마찬가지로 두 번째, 세 번째 원소에도 반복하여 수행하다 보면 결국 최종적으로 정렬된 리스트를 얻을 수 있게 된다. 특징 ▶ 시간 복잡도는 O(N^2)이다. 가장 작은 원소를 탐색하는데 (N - 1), (N ..

C++/Algorithm

[Algorithm/C++] 버블 정렬(Bubble Sort) - 거품 정렬

1. 설명 버블 정렬(Bubble Sort)란 거품 정렬이라고도 하며 인접한 원소 간 비교하는 작업을 반복적으로 수행함으로써 정렬된 리스트를 얻는 정렬 방법 중 하나이다. 동작 예시를 보면 인접한 원소끼리 비교하여 왼쪽의 원소가 오른쪽의 원소보다 클 경우 위치를 교환해주고, 그다음 원소와도 이 작업을 반복하여 수행함으로써 가장 큰 원소가 가장 오른쪽으로 이동하게 된다. 이 과정을 또 반복하여 수행함으로써 가장 큰 값을 갖는 원소가 오른쪽에 차곡차곡 위치하게 되므로, 최종적으로 정렬된 리스트를 얻을 수 있게 된다. 특징 ▶ 시간 복잡도는 O(N^2)이다. 정렬이 되어 있는 상태 이어도 각 원소끼리 비교를 수행하여야 하기 때문에 동일하다. ▶ 공간 복잡도는 O(1)이다. 추가적인 삽입, 삭제 없이 위치만 변..

C++/STL

C++ Random - 범위 랜덤 수 구하기

1. random 랜덤한 임의의 수를 구하기 위해서는 random_device를 사용할 수 있다. 이를 사용하기 위해서는 random 헤더를 include 해주어야 한다. random_device는 구할 수 있는 수의 최소값과 최대값을 min과 max 함수를 사용하여 읽을 수 있다. 특정 범위를 지정하여 랜덤한 수를 구하고 싶다면 추가적인 연산이 필요하다. 2. 코 드 환경 : Visual studio 2019 #include #include using namespace std; int main() { random_device rd; cout

C++/Algorithm

C++ 숫자 각 자릿수 구하기, 문자열 숫자 각 자릿수 구하기

1. 숫자 각 자릿수 구하기 숫자의 각 자릿수를 구하기 위해서는 나누기와 나머지 연산을 사용하여서 가능하다. 또한, 숫자를 문자열로 형변환함으로써 인덱스를 사용하여 각각의 자리의 해당하는 숫자에 접근할 수 있다. 단, 숫자형 문자열에서 각 문자에 접근하여 int형으로 저장한다면 아스키 코드상에 10진수를 얻게 된다. 따라서 올바른 숫자를 얻기 위해서 추가적인 작업을 해주어야 한다. 2. 코 드 환경 : Visual studio 2019 #include #include #include using namespace std; int main() { int a = 1234567; while (a) { cout