분류 전체보기
-
머큐리얼...3일지 2021. 6. 23. 08:58
연산자 not x(또는 !x) 주어진 x가 아닌 체이진 셋을 찾는다. x::y(또는 x..y) 리비전 x와 y 사이에 존재하는 모든 체인지 셋을 찾는다. x:y 리비전 x와 y 사이에 존재하는 모든 체인지 셋을 찾는다. 단, x와 y는 동일한 브랜치여야 한다. x and y(또는 x & y) 체인지 셋 x와 y의 교집합을 찾는다. x or y(또는 x | y 또는 x + y) 체인지 셋 x와 y의 합집합을 찾는다. x - y 체인지 셋 x와 y의 차집합을 찾는다(x와 y 중 x에만 포함된 경우를 찾는다). x % y 체인지 셋 x의 조상이면서 y의 조상이 아닌 체인지 셋을 찾는다. x^n 체인지 셋의 n번째 부모 체인지 셋을 찾는다(n이 0이면 자신을 가리킨다). x~n 체인지 셋의 n번째 조상을 찾는다..
-
JUNGOL...77일지 2021. 6. 23. 08:43
Beginner_Coder/소분류/연속부분합 찾기 문제 N개의 정수를 담고 있는 배열이 주어졌을 때, 여기서 가능한 연속 부분합의 최댓값을 구하는 프로그램을 작성하라. 여기서 연속 부분합이라는 것은 배열에서 연속된 숫자들을 선택해서 합하였을 때의 값을 말한다. 아무 배열도 택하지 않는 경우도 연속 부분합에 포함됨을 유의하자. 입력 형식 입력의 첫 번째 줄에는 정수 N(1≤N≤105)가 입력된다. 그리고 그 다음 줄에는 N개의 배열에 담긴 숫자가 순서대로 입력된다. 숫자의 범위는 -100이상 100이하의 정수다. 출력 형식 입력에 대한 가장 큰 연속 부분합을 출력한다. 입력 예 4 | 10 1 2 -2 4 | 3 -4 0 1 7 -4 13 -9 8 -3 출력 예 5 | 17 FindMaximumSubarr..
-
정렬 알고리즘 개요프로그래밍 기초/알고리즘 2021. 6. 23. 08:26
정렬 알고리즘 정렬이란? n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다. 정렬의 종류 정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다. 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, 평균 Ο(n²) 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(n²) 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(nlogn) 퀵 정렬 특정 값을 기준으로 영역을 나누..
-
알고리즘...11일지 2021. 6. 22. 21:40
테스트용 난수 생성 및 시간 체크 함수 구현 알고리즘의 효율성 테스트를 위해 1,000,000 개의 난수를 생성하여 텍스트 파일로 저장 및 불러오기 함수 구현 common.hpp #pragma once #include #include #include #define MAKE_RANDOM_NUMBERS #ifdef MAKE_RANDOM_NUMBERS #include #include #endif namespace Common { #ifdef MAKE_RANDOM_NUMBERS int* GenerateRandomNumber(int n = 100'000) { std::default_random_engine randomEngine; std::uniform_int_distribution distribution(0, ..
-
알고리즘...10일지 2021. 6. 16. 10:44
선택 정렬_계속 위 알고리즘을 실제 구현하고 과정을 살펴보면 다음과 같다. SelectionSort.hpp #pragma once #include "../Common.hpp" void SelectionSort(int arr[], int n) { Common::PrintArray(arr, n); for (int i = 1; i < n; i++) { int biggest{ n - i }; for (int j = 0; j < n - i; j++) { if (arr[biggest] < arr[j]) { biggest = j; } } Common::Swap(arr, biggest, n - i); Common::PrintArray(arr, n); } } main.cpp #include "Sort/SelectionS..
-
알고리즘...9일지 2021. 6. 14. 12:38
선택 정렬 모든 정렬 알고리즘 중 가장 간단한 알고리즘으로 배열 A [1... n]에서 가장 큰 원소를 찾아 A [n]과 자리를 바꾸고 [1... n-1]에 대해 이전 과정을 반복하여 정렬을 마무리한다. 선택 정렬 알고리즘 SelectionSort(A[], n) { for last ← n downto 2 { A[1...last] 중 가장 큰 수 A[k]를 찾는다. A[k] ↔ A[last] } } 이 알고리즘의 수행 시간은 for 루프에 비례하는데 이 루프는 n ~ 2까지 반복하므로 총 비교 회수는 n(n-1)/2 이므로 Θ(n²)이 된다. 더보기 참고문헌 한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘
-
알고리즘...8일지 2021. 5. 26. 09:48
정렬이란 n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다. - 정렬의 종류 정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다. 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, Ο(n²) 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, Ο(n²) 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, Ο(nlogn) 퀵 정렬 특정 값을 기준으로 영역을 나누어 자리를 바꾸는 연산을 반복..
-
알고리즘과 귀납적 사고프로그래밍 기초/알고리즘 2021. 5. 20. 08:57
알고리즘과 귀납적 사고 알고리즘이란? 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것으로 알고리즘을 설계하기 위해서는 해야 할 작업을 명확하게 명시해야 한다. ※ 알고리즘이 명확하다는 것은 모호하지 않고 이해하기 쉬운 것을 의미하며 자세한 것과는 다르다. 알고리즘은 가능하면 효율적이어야 하며 그중 작은 입력보다는 충분히 큰 입력에 대해 관심을 가져야 한다. 이렇게 큰 입력에 대한 분석을 점근적 분석(Asymptotic Analysis)라고 한다. 알고리즘을 분석하는 이유 어떠한 입력을 일정 시간 이내에 처리해야 할 때 적용할 수 있는 알고리즘의 시간 분석을 하면 각 알고리즘이 어느 정도의 시간이 소요되는지 파악하여 적절한 알고리즘을 적용할 수 있다. ※ 일반적인 상황에서..