YunaNote

🔷 유클리드 호제법( euclidean - algorithm ): 두 수의 최대 공약수를 구하는 알고리즘이다. 유클리드 호제법을 사용하기 위해선 MOD 연산을 알고있어야한다.  MOD ?최대 공약수를 구하는 연산으로 Modulo 나머지 연산으로도 불린다. 🔷 유클리드 호제법의 원리🔻 큰 수에서 작은 수로 나누는 MOD 연산 🔻 앞에서 진행한 작은 수와 MOD 연산 결과값과 MOD 연산 수행🔻 반복하다가 나머지가 0이 되는 순간 작은 수를 최대 공약수로 선택

🔷 오일러 피( Eluer's phi )?해당 기호를 사용하며 phi라고 읽으며 대표적으로 서로소 관련 문제에서 사용된다. 🔷P[N] ?1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 💡 서로소란?두 수 사이의 관계에서 공통되는 약수가 최대 1이며 1 밖에 없는 수를 뜻한다. 서로소의 예시로는 아래와 같이 확인 할 수 있다. ◾ 5의 약수 : 1 , 5◾ 6의 약수 : 1 , 2 , 3 , 6◻ 5와 6의 최대 공약수는 1이며 두 수가 일치하는 수는 1이므로 서로소라고 할 수 있다.  🔷  오일러 피의 원리🔻 구하고자 하는 오일러 피의 범위만큼 배열 초기화🔻 2부터 시작해서 인덱스가 같을 때(소수일 때) 현재 선택된 숫자의 배수에 해당되는 수(K)의 배열 끝까지 탐색 후  P[i..

🔷 소수(Prime number)?1과 자기 자신 외의 약수가 존재하지 않는 수를 의미한다. 🔷 소수를 구하는 판별법에라토스테네스의 체 ( Sieve of Eratosthenes ) : 소수들을 대량으로 빠르고 정확하게 구하는 방법 🔷 에라토스테네스의 체의 원리🔻 구하고자하는 소수의 범위만큼 1차원 배열 생성한 뒤 초기화한다.🔻 2부터 시작해서 현재 선택된 숫자의 배수의 해당되는 수를 모두 지운다. (이때 자기자신은 지우지않으며, 이미 지워진 수는 건너뛴다.)🔻 배열이 끝날 때까지 반복한 뒤 2부터 시작하여 남아 있는 수를 모두 출력한다  🔷 에라토스테네스의 체의 시간 복잡도이중 for문을 이용하여 O(N^2) 으로 판단될 수 있지만 배수를 삭제하여 생략하는 경우도 있기 때문에 O(n * l..

[ Algorithm ] 그리디 알고리즘그리디 (Greedy) / 탐욕 알고리즘 : 현재 상황에서 최적이라고 생각하는 해를 선택하는 방법이다. 하지만 앞으로 남은 단계의 선택을 고려하지않고 현재 단계의 가장 최선의 선택만 고려하기 때문o-joyuna.tistory.com 이전에 그리디 알고리즘을 공부하면서 정리한 내용이다. 또 코딩테스트 때 자주나오는 알고리즘의 하나이다. 🔷 그리디(Greedy) ?: 탐욕법이라고도 불리며, 현재 상태에서 보는 선택지 중 제일 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 즉 눈 앞의 가장 큰 이익을 추구하는 기법이다.  대부분의 그리디 문제에는 일반적으로 "최대한 적은, 최대한 많은" 이라는 문구가 문제에 들어가는 경우가 많다. 즉 최대/최..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 ..

문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. #include #include #include #include using namespace std; int main() { int count = 0; string num; vector v; int sum = 0; cin >> count; cin >> num; for (int i = 0; i < num.length(); i++) { int inum = num[i] - '0'; v.push_back(inum); } sum = accumulate(v.begin(), v.end(), 0); cout

퀵 정렬(Quick Sort)? 기준 값(Pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하여 반복해서 정렬하는 알고리즘 분할과정과 정복과정으로 나누어짐 Pivot을 정한 뒤 왼쪽 퀵 소트, 오른쪽 퀵소트를 진행 시간복잡도 평균 O(n log n) 최악의 경우 O(n^2) 참고 자료

삽입 정렬(Insertion Sort)이란? 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입해 정렬하는 방식 시간 복잡도는 O(n^2)로 느린 편 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입 삽입 정렬 수행과정 🔹현재 Index에 있는 데이터 값을 선택 🔹현재 선택한 데이터가 정렬된 데이터 범위에 삽입된 위치를 탐색 🔹삽입 위치부터 index에 있는 위치까지 shift 연산 수행 🔹삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행 🔹전체 데이터의 크기만큼 index가 커질 때까지 수행 ( 선택할 데이터가 없을 때까지 반복 수행 ) 탐색하는 부분에서 이진 탐색과 같은 탐색 알고리즘을 통해 시간 복잡도를 줄일 수 있다. 관련 문제 [ 백준 ]..

선택 정렬 : 대상 데이터에서 최대나 최소 데이터를 나열된 순으로 찾아가며 선택하는 방법 구현 방법이 복잡하고, 시간복잡도는 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 사용하지 않음 1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다. 2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 Swap한다. 3. 가장 앞에 있는 데이터의 위치를 변경해 남은 정렬 부분의 범위를 축소 4, 남은 정렬 부분이 없을 때까지 정렬