CS (27) 썸네일형 리스트형 고정 소수점 컴퓨터에서 실수를 저장하는 방법에는 고정 소수점과 부동 소수점이 있습니다.이 글에서는 고정 소수점에 대해 다루겠습니다. 고정 소수점고정 소수점(fixed-point)은 소수 부분의 자릿수를 고정하여 분수(비정수) 숫자를 표현하는 방법입니다.부호 비트, 정수부, 소수부로 나누어집니다. 고정 소수점에서는 소수 부분이 정수 부분과 동일한 숫자 기반으로 표현되지만, 밑(base) b의 음의 거듭제곱을 사용합니다. 가장 일반적인 변형은 10진법과 2진법입니다. 후자는 일반적으로 이진 스케일링(binary scaling)이라고 합니다.따라서 n 개의 소수 자릿수가 저장되면 값은 항상 b^-n의 정수 배수가 됩니다.고정 소수점은 본질적으로 소수부를 고정된 scaling factor로 곱하여 정수로 표현하는 것입니다.. [알고리즘] 오일러 피 오일러 피오일러의 피 함수는 𝜙(𝑁) 또는 P[N] 으로 표시되며, 자연수 N 이하의 양의 정수 중에서 N과 서로소인 수의 개수를 나타내는 함수입니다. 두 수가 서로소라는 것은 공약수가 1 뿐인 경우를 말합니다. 오일러 피 알고리즘'2' 부터 구하고자 하는 값의 제곱근까지의 소인수를 구합니다.결괏값을 갱신합니다.N값에서 소인수를 나눠줍니다.N이 1보다 크면 결괏값을 최종 조정합니다.오일러 피 구현int N; // 구하고자 하는 수int result = N;for (int k = 2; k 1) { // 소인수가 남아있을 때 result -= result / N;}오일러 피 시간복잡도오일러 피의 시간복잡도는 O(Φn logn)입니다. 여기서 Φn 은 서로소 개수 입니다. 증명은 생략하겠.. [알고리즘] 소수 구하기 소수소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 예를 들어, 5는 1 ×5 또는 5 ×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수입니다. 그러나 6은 자신보다 작은 두 숫자의 곱(2 ×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수나 비소수라고 합니다. 에라토스테네스의 체소수를 구하는 대표적인 방법으로 에라토스테네스의 체가 있습니다.에라토스테네스의 체 알고리즘은 다음과 같습니다.구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.'2'부터 시작해 특정 수의 배수에 해당하는 수를 모두 지웁니다. 이때 특정 수 자신은 지우지 않습니다.배열의 끝까지 2를 반복합니다. 에라토스테네스의 체 구현boolean[].. [알고리즘] LCM LCM최소공배수(LCM, Least Common Multiple)는 두 개 이상의 정수의 공통 배수 중 가장 작은 수를 의미합니다.LCM을 구하는 방법에는 여러 방법이 있지만, 가장 흔히 알려진 방법은 GCD를 이용하는 방법입니다. GCD [알고리즘] GCD - 유클리드 호제법유클리드 호제법이란유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방tkxxls.tistory.com LCM 알고리즘두 수 a와 b의 최소 공배수 lcm(a, b)는 다음과 같이 계산됩니다lcm(a, b) = a × b / gcd(a, b)LCM 구현int gcd(int a, int b).. [알고리즘] GCD - 유클리드 호제법 유클리드 호제법이란유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이라는 뜻입니다. GCD 알고리즘 두 개의 정수 a와 b (단, a ≥ b)가 주어집니다.a를 b로 나눈 나머지를 구합니다. 즉, r = a mod b.r이 0이라면, b가 a와 b의 최대 공약수이며, 알고리즘을 종료합니다.r이 0이 아니라면, a는 이전의 b가 되고, b는 이전의 r이 되어 위 과정을 반복합니다.GCD 구현int gcd(int a, int b) { if (b == 0) return a; retu.. [자료 구조] 동적 배열 vs 연결 리스트 동적 배열과 연결 리스트의 가장 큰 차이점은 삽입, 삭제, 임의 원소 접근에 드는 시간입니다.삽입과 삭제를 할 일이 없거나, 배열의 끝에서만 삽입, 삭제를 하면 되는 경우, 동적 배열의 거의 항상 좋습니다.임의 원소에 빠르게 접근할 수 있으며, 메모리에 연속적으로 배치되어 있기 때문에 CPU 캐시 효율이 높습니다. 특정 원소의 삭제가 빈번히 일어나는 경우에는 연결 리스트가 좋습니다. 비교 요약특징연결 리스트동적 배열이전 원소/ 다음원소 찾기O(1)O(1)메모리 할당필요할 때마다 동적 할당초기 크기 할당 후 동적 증가접근 속도O(n)O(1)삽입/삭제 속도O(1) (특정 위치)O(n)메모리 오버헤드높음 (포인터 저장)낮음캐시 적중률낮음높음구현 복잡성높음낮음 [자료구조] 원형 연결 리스트 원형 연결 리스트원형 연결 리스트(Circular Linked List)는 마지막 노드가 첫 번째 노드를 가리키는 구조를 갖습니다. 이로 인해 리스트의 끝에서 다시 리스트의 시작으로 원활하게 순환할 수 있는 특성을 가집니다. 원형 이중 연결 리스트의 각 노드는 일반적으로 두 부분으로 구성됩니다.데이터(Data): 노드에 저장된 실제 정보.다음 포인터(Next Pointer): 다음 노드를 가리키는 참조. 마지막 노드의 다음 포인터는 다시 첫 번째 노드를 가리킵니다.이전 포인터(Previous Pointer): 이전 노드를 가리키는 참조. 첫 번째 노드의 이전 포인터는 마지막 노드를 가리킵니다.특징시작 노드를 자유롭게 설정할 수 있어서, 어떤 특정 노드를 기준으로 리스트 전체 순회가 가합니다.순환 구조 .. [자료구조] 이중 연결 리스트 이중 연결 리스트이중 연결 리스트(Doubly linked list)는 각 노드가 두 개의 링크 필드를 가지며 이 링크 필드를 통해 양방향으로 움직일 수 있도록 만든 리스트입니다.단순 연결 리스트의 각 노드는 일반적으로 세 부분으로 구성됩니다. 데이터(Data): 노드에 저장된 실제 정보.다음 포인터(Next Pointer): 다음 노드를 가리키는 참조. 마지막 노드의 다음 포인터는 보통 null로 설정됩니다.이전 포인터(Previous Pointer): 이전 노드를 가리키는 참조. 첫 번째 노드의 이전 포인터는 보통 null로 설정됩니다. 특징노드 추가 및 제거의 용이성: 리스트의 중간에 노드를 추가하거나 제거할 때, 이전 노드를 추적할 필요가 없으므로 삽입 및 삭제 작업이 상대적으로 간단하고 효율적입.. 이전 1 2 3 4 다음
