기록보관소

계수 정렬에서 배열로 숫자의 빈도를 세는 방식을 응용해서 코드를 작성해보았습니다. #include #include int N; int sum; int max = -5000, min = 5000; int count[10000]; int temp; int first_mode; int second_mode=999999; int mode; //count sort //ceil - 올림, floor - 내림 //반올림은 floor(x+0.5) int main(void) { scanf("%d", &N); for (int i = 0; i max) max = temp; if (temp < min) min = temp; t..

계수정렬은 n개의 입력원소가 있고 각각의 원소가 0부터 k 사이에 있는 정수이며. k=O(n) 일 때 Θ(n) 시간에 수행되는 정렬이다. 계수 정렬은 각 입력 원소 x에 대해 x보다 작은 원소의 개수를 센다. 이 수는 출력 배열에서 원소 x의 위치를 정하는 데 사용된다. 예를 들어, x보다 작은 원소가 5개라면 x는 출력 배열에서 6번째 자리가 된다. 값이 같은 원소가 여러 개 있는 경우에는 모두 같은 자리에 둘 수 없으므로 방법을 약간 고쳐야 한다. 같거나 작은 원소의 개수를 구하여야 하며, 안정성을 유지하기 위해 입력 원소를 뒤에서부터 확인하여 출력배열의 적절한 위치에 넣어야 한다. 계수정렬의 코드에서는 입력 배열과 출력배열, 같거나 작은 원소의 개수를 저장하기 위한 임시 배열이 필요하다. 입력 원소..

수 체계와 변환 R 진법 체계 : 숫자의 자릿수와 관련이 있는 표기법으로 각 자리의 숫자에 자릿수에 비례하는 가중치가 부여된다는 점이 특징이다. 어떤 R 진법의 경우, 0 ~ R-1의 숫자를 사용하며 R> 10인 경우, 수를 표기하기 위해 알파벳을 사용하기도 한다. R 진법에서 소수는 가중치인 거듭제곱에서 지수의 음과 양을 나눈다. 2진법에서는 소수점 아래 첫 번째 자리의 가중치가 과 같다. 각 체계에서 다른 체계로 변환할 수 있다. 다만 10진법이 아닌 진법에서 10진법이 아닌 진법으로 변환하는 것은 추천되지 않는다. 해당 진법에서의 연산규칙(연산 테이블)을 고려해야 하며 그것은 우리가 익숙하지 않아 시간이 오래 걸리기 때문이다. 예로 들면 다음과 같다. 쉬운 예이지만 4진법의 곱셈과 덧셈을 해야 한다..

루프 불변성은 알고리즘이 타당한지 확인하기 위해 사용되는 성질 중 하나이다. 쉽게 설명하자면 우리가 작성한 알고리즘 내부에 for나 while 같이 반복문이 삽입되어 있을 때 그것이 원하는 결과를 출력하는지 루프 불변성을 통해 확인하는 것이다. 루프 불변성을 통해 알고리즘의 타당성을 증명하기 위해 만족시켜야 하는 3가지 조건들이 있다. 1. 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 유지되어야 한다. 2. 루프가 반복되기 전에 루프 불변성이 유지되었다면 다음 반복이 시작되기 전까지도 계속 유지되어야 한다. - 위의 2가지만 만족시키더라도 루프 불변성이 유지됨을 알 수 있다. 3. 루프가 종료될 때 유지된 루프 불변성이 알고리즘 타당성 증명에 의미가 있어야 한다. - 확인한 루프 불변성을 알고리즘..

어떤 입력을 받았을 때 출력을 내놓는 일련의 계산 과정. 입출력 관계를 지탱하는 계산 과정이라고 할 수 있다. 지금까지 많은 알고리즘이 개발되었지만 모든 문제에서 최적의 해를 도출하는 알고리즘은 찾기 힘들기 때문에 상황에 따라 필요한 알고리즘을 선택하거나 개발해서 사용해야 한다. 알고리즘이 모든 입력에 대해 올바른 출력을 내놓고 종료한 다면 그 알고리즘은 타당하다고(Correct) 하며 문제에 대해 그런 알고리즘을 찾는 것을 푼다고(Solve) 한다. 알고리즘과 항상 함께 하는 것이 있다. 바로 자료구조다. 자료구조는 알고리즘을 사용할 때 자료에 쉽게 접근하고 변경하기 위해서 자료를 저장하고 조직하는 방법이다. 알고리즘의 중요성은 날이 갈수록 커지고 있다. 우리 주위를 둘러싼 시스템들의 성능이 하드웨어 ..