정렬14 유클리드 호제법 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 입력으로 두 수 m,n(m>n)이 들어온다. n이 0이라면, m을 출력하고 알고리즘을 종료한다. m이 n으로 나.. 2023. 6. 19. 10814번: 나이순 정렬 - 관련 사이트: https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 첫번째 나이 값을 기준으로 비교 함수를 정의하였다. 단, 첫번째 값이 같을 경우 순서가 변경되지 않아야 하므로 일반적인 sort 함수가 아닌, stable_sort 함수를 사용하였다. #include #include #include using namespace std; bool compare(pair prev, pair next) { return prev.first < next.fir.. 2023. 6. 13. 25305번: 커트라인 - 관련 사이트: https://www.acmicpc.net/problem/25305 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net N명들 중 k번째로 높은 점수를 구하는 문제이다. 내장 함수 sort를 사용하여 문제를 해결하였다. 1) N명의 점수 입력받은 후 내림차순으로 정렬 2) k번째 점수 확인 #include #include #include using namespace std; int main() { int N, k, x; cin >> N >> k; vector scores(N); for (int i = 0; i > scores[i]; sort.. 2023. 6. 8. 2751번: 수 정렬하기 2 - 관련 사이트: https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net "N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오." "시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다." 입력된 숫자를 정렬하는 문제이다. vector를 사용하여 값을 저장하고 C++ 내장 함수, .. 2023. 6. 6. 정렬 정렬 알고리즘 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 효율적인 정렬은 탐색이나 병합 알고리즘처럼 (정렬된 리스트에서 바르게 동작하는) 다른 알고리즘을 최적화하는 데 중요하다. 또 정렬 알고리즘은 데이터의 정규화나 의미있는 결과물을 생성하는 데 유용히 쓰인다. sort(vector.begin(), vector.end(), operator) sort(array, array + int, operator) [출처] 위키백과 - 정렬 알고리즘 * 연관 문제: - [백준] 11651번: 좌표 정렬하기 2 - [백준] 10817번: 세 수 (배열 정렬) 안정 정렬 (Stable Sort) 동등한 요소의 순서는 보존하면서 정렬하는.. 2023. 6. 6. 이전 1 2 3 다음