CS/자료구조 (8) 썸네일형 리스트형 부동 소수점 부동 소수점은 고정 소수점과 다르게 소수점의 위치를 고정하지 않고 소수점의 위치를 나타내는 수를 따로 저장하는 방식으로, 유효숫자를 나타내는 가수와 소수점의 위치를 나타내는 지수부로 나누어 표현합니다. 정규화부동 소수점 표현 방식은 수를 (가수) × (밑수)^(지수)와 같이 유효숫자를 사용한 곱셈 형태로 표현합니다. 예를 들어, 123.45를 밑수가 10인 부동 소수점으로 나타내면 12.345 * 10^1이 되는데, 가수 부분을 한자리 자연수를 갖도록 바꾸면 1.2345 * 10^2와 같이 됩니다. 이처럼 가수의 첫째 자리가 밑수보다 작은 한자리 자연수가 되도록 바꾸는 것을 정규화라고 합니다.부동 소수점 변환 예시 밑수가 10인 경우에 로마자 E 또는 e를 사용하여 함수 형태로 표시하기도 하는데, -0.. 고정 소수점 컴퓨터에서 실수를 저장하는 방법에는 고정 소수점과 부동 소수점이 있습니다.이 글에서는 고정 소수점에 대해 다루겠습니다. 고정 소수점고정 소수점(fixed-point)은 소수 부분의 자릿수를 고정하여 분수(비정수) 숫자를 표현하는 방법입니다.부호 비트, 정수부, 소수부로 나누어집니다. 고정 소수점에서는 소수 부분이 정수 부분과 동일한 숫자 기반으로 표현되지만, 밑(base) b의 음의 거듭제곱을 사용합니다. 가장 일반적인 변형은 10진법과 2진법입니다. 후자는 일반적으로 이진 스케일링(binary scaling)이라고 합니다.따라서 n 개의 소수 자릿수가 저장되면 값은 항상 b^-n의 정수 배수가 됩니다.고정 소수점은 본질적으로 소수부를 고정된 scaling factor로 곱하여 정수로 표현하는 것입니다.. [자료 구조] 동적 배열 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로 설정됩니다. 특징노드 추가 및 제거의 용이성: 리스트의 중간에 노드를 추가하거나 제거할 때, 이전 노드를 추적할 필요가 없으므로 삽입 및 삭제 작업이 상대적으로 간단하고 효율적입.. [자료구조] 단순 연결 리스트 단순 연결 리스트단순 연결 리스트(Singly linked list)는 가장 간단한 형태의 연결 리스트로, 각 노드는 데이터와 다음 노드를 가리키는 참조를 포함합니다. 이러한 리스트는 헤드(첫 번째 노드)에서부터 테일(마지막 노드)까지 한 방향으로만 순회할 수 있습니다. 단순 연결 리스트의 각 노드는 일반적으로 두 부분으로 구성됩니다데이터(Data): 노드에 저장된 실제 정보.다음 포인터(Next Pointer): 다음 노드를 가리키는 참조. 마지막 노드의 다음 포인터는 보통 null로 설정됩니다. 특징순차 접근: 단순 연결 리스트는 인덱스를 사용한 임의 접근이 불가능합니다.노드의 순서대로 접근해야 하므로 시간 복잡도가 O(n)입니다.단순 연결 리스트의 맨 앞에 노드를 삽입하거나 삭제하는 연산의 시간 .. [자료구조] 연결 리스트 연결 리스트연결 리스트(linked list)는 데이터 구조 중 하나로, 각 요소(노드)가 다음 요소를 가리키는 포인터를 포함하는 방식으로 구성됩니다. 물리적 메모리 위치와 상관없이 논리적으로 데이터를 순차적으로 연결하는 형태입니다.이러한 구조는 요소의 삽입과 삭제가 효율적이며, 동적 메모리 할당을 용이하게 합니다. 특징크기를 미리 지정하지 않고 동적으로 크기를 조절할 수 있습니다. 삽입과 삭제가 상수 시간 내에 이루어질 수 있습니다.노드들이 메모리 내에서 연속적으로 저장되지 않아도 되기 때문에, 메모리 단편화 문제를 줄일 수 있습니다.특정 위치의 노드에 접근하기 위해서는 처음 노드부터 차례로 접근해야 합니다. 선형 시간이 걸립니다.비연속적으로 저장되기 때문에 캐시 효율성이 낮습니다.각 노드는 데이터 외.. [자료구조] 동적 배열 먼저 배열에 대해 알아보겠습니다.배열배열이란 일반적으로 정적 배열을 말합니다. 동일한 타입의 데이터를 하나의 변수에 저장하고, 인덱스를 사용하여 개별적으로 접근할 수 있게 하는 데이터 구조입니다. 배열은 고정된 크기를 가지며, 각 요소는 인덱스를 통해 접근할 수 있습니다. 배열의 인덱스는 보통 0부터 시작하여, 마지막 요소는 배열의 크기-1까지 이어집니다. 특징배열은 선언할 때 크기가 고정되며, 이후 크기를 변경할 수 없습니다.배열에 저장되는 모든 요소는 동일한 데이터 타입을 가져야 합니다.배열의 각 요소는 인덱스를 통해 접근할 수 있으며, 인덱스는 0부터 시작합니다.배열은 메모리에서 연속적인 공간에 저장됩니다.주어진 위치의 원소를 반환하거나 변경할 때 O(1)에 할 수 있습니다. 동적 배열배열의 큰 단.. 이전 1 다음
