셩잇님의 잡동사니

1. 해시 테이블이란? 해시 맵이라고도 하는 해시 테이블은 키-값 쌍을 효율적으로 저장하고 검색할 수 있는 데이터 구조입니다. 즉, 각 데이터는 고유 키를 기반으로 테이블에 저장됩니다. 또한 해싱이라는 기술을 사용하여 키를 기본 배열의 특정 위치에 매핑하여 관련 값에 빠르게 액세스할 수 있도록 합니다. 해시 테이블은 버킷 배열로 구성되며, 각 버킷은 앞에서 설명한 것과 같이 하나 이상의 키-값 쌍을 저장할 수 있습니다. 해시 테이블은 해시 함수를 사용하여 키를 가져와서 해시 함수를 적용하는 방식으로 작동합니다. 해시 함수는 키-값 쌍이 저장되어야 하는 배열의 인덱스를 반환합니다. 그 다음 해시 값을 사용하여 테이블에서 데이터 위치를 결정합니다. 해시 함수는 두 개의 키가 동일한 인덱스에 해시할 때 발생하..

1. 딕셔너리란? 딕셔너리(맵, 연관 배열, 심볼 테이블이)란 키-값 쌍의 데이터를 저장하는 추상 데이터 유형입니다. 연결된 키를 기반으로 값을 효율적으로 삽입, 삭제 및 검색할 수 있습니다. 각 키는 고유하며 각 값은 모든 유형의 데이터가 될 수 있습니다. 딕셔너리에서 키를 조회하면 딕셔너리는 연관된 값을 반환합니다. 2. 딕셔너리의 주요 개념 키-값 쌍: 딕셔너리는 요소를 키-값 쌍으로 저장하며, 각 키는 컬렉션 내에서 고유하고 각 키는 해당 값과 연관됩니다. 키는 연결된 값에 액세스하기 위한 식별자 또는 색인 역할을 합니다. 값은 정수, 문자열, 객체 또는 기타 데이터 구조와 같은 모든 데이터 유형이 될 수 있습니다. 효율적인 조회: 딕셔너리가 제공하는 기본 작업은 특정 키와 연관된 값을 검색하는 ..

1. 레드 블랙 트리란? 레드-블랙 트리는 삽입과 삭제 중에 균형을 유지하는 자체 균형 바이너리 검색 트리입니다. 빨간색 또는 검은색인 노드 색상의 이름을 따서 명명되었습니다. 레드-블랙 트리는 균형 잡힌 구조를 보장하여 최악의 경우 시간 복잡도가 O(log n)인 효율적인 검색, 삽입, 삭제 작업을 보장합니다. 2. 레드 블랙 트리의 속성 및 개념 이진 검색 트리(BST) 속성: 레드-블랙 트리는 이진 검색 트리로, 각 노드에 키 값이 있으며, 어떤 노드의 왼쪽 하위 트리에 있는 키는 해당 노드의 키보다 작고 오른쪽 하위 트리에 있는 키는 더 큽니다. 노드 색상: 빨간색-검정색 트리의 각 노드는 빨간색 또는 검정색으로 표시됩니다. 이 색상은 트리의 속성을 유지하기 위한 균형 메커니즘을 제공합니다. 빨간..

1. 이진 트리(Binary Tree)란? 이진 트리는 각 노드에 왼쪽 자식과 오른쪽 자식이라는 최대 두 개의 자식이 있는 트리 데이터 구조의 한 유형입니다. 이진 트리의 구조는 검색 및 정렬과 같은 많은 일반적인 알고리즘에 적합합니다. 2. 이진 트리(Binary Tree)의 구조 이진 트리의 각 노드에는 연결된 값이 있으며, 트리는 특정 노드의 왼쪽 하위 트리에 있는 값이 노드의 값보다 작고, 특정 노드의 오른쪽 하위 트리에 있는 값이 노드의 값보다 크도록 구조화되어 있습니다. 이 구조는 검색하는 값에 따라 왼쪽 또는 오른쪽 하위 트리의 값을 확인하여 재귀적으로 검색할 수 있으므로 특정 값에 대한 트리를 효율적으로 검색할 수 있습니다. 이진 트리는 균형 트리 또는 불균형 트리일 수 있습니다. 균형 이..

1. 트리(Tree)란? 트리는 컴퓨터 과학 및 소프트웨어 엔지니어링에서 일반적으로 사용되는 비선형 데이터 구조입니다. 트리는 가장자리 또는 가지로 연결된 노드의 모음으로, 하나의 노드를 루트 노드로 지정합니다. 루트 노드 아래의 노드를 자식 노드라고 하고 루트 노드 위의 노드를 부모 노드라고 합니다. 자식 노드가 없는 노드를 리프 노드라고 합니다. 2. 트리(Tree)의 종류 다음은 가장 일반적인 트리 유형 중 일부입니다: 이진 트리: 이진 트리는 각 노드에 최대 두 개의 자식 노드가 있는 트리로, 왼쪽 자식과 오른쪽 자식이라고 합니다. 이진 검색 트리: 이진 검색 트리는 노드의 왼쪽 자식은 노드의 값보다 작은 값을 포함하고, 노드의 오른쪽 자식은 노드의 값보다 큰 값을 포함하는 이진 트리입니다. 따라..

1. 해시 맵(Hash map)이란? 해시 맵은 효율적인 조회, 삽입, 삭제를 위해 키를 값에 매핑하는 데이터 구조입니다. 해시 테이블 또는 사전(Dictionary)이라고도 합니다. 해시 맵은 해시 함수를 사용하여 원하는 값을 찾을 수 있는 버킷 또는 슬롯 배열로 인덱스를 계산합니다. 해시 맵의 기본 개념은 키-값 쌍을 배열에 저장하는 것으로, 키는 해시 함수를 사용하여 배열 인덱스로 해시됩니다. 해시 함수는 키를 입력으로 받아 해당 값을 찾을 수 있는 배열의 인덱스를 반환합니다. 따라서 배열에서 한 번만 조회하면 되므로 해시 맵에서 특정 키를 매우 빠르게 검색할 수 있습니다. 2. 해시 맵(Hash map)의 장점 해시 맵의 주요 장점 중 하나는 조회, 삽입, 삭제의 시간 복잡도가 평균적으로 일정하다..

1. 큐(Queue)란? 큐는 요소를 선입선출(FIFO) 방식으로 저장하는 데이터 구조의 한 유형입니다. 즉, 큐에 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 큐는 일반적으로 작업 스케줄링이나 메시지 전달 시스템과 같이 요소를 수신한 순서대로 처리해야 하는 상황에서 사용됩니다. 2. 큐(Queue)에서 사용되는 작업 1. 큐에 추가(Enqueue): 이 작업은 요소를 큐의 끝에 추가합니다. 2. 큐에 해제(Dequeue): 이 작업은 큐의 맨 앞에 있는 요소를 제거합니다. 3. Peek: 이 작업은 큐의 앞쪽에 있는 요소를 제거하지 않고 반환합니다. 4. IsEmpty: 이 작업은 큐가 비어 있는지 확인합니다. 5. Size: 이 작업은 큐에 있는 요소의 수를 반환합니다. 3. 큐(Queue)의 구..

1. 자료 구조란? 자료 구조(data structure)는 데이터를 효율적으로 액세스하고 조작할 수 있도록 컴퓨터에서 데이터를 구성하고 저장하는 방법입니다. 자료 구조에는 여러 가지 유형이 있으며, 각각 고유한 장단점이 있으므로 올바른 데이터 구조를 선택하는 것은 효율적이고 효과적인 알고리즘이나 프로그램을 설계하는 데 있어 중요한 부분입니다. 2. 자료 구조의 유형 다음은 가장 일반적인 데이터 구조의 몇 가지 유형입니다: 배열: 배열은 인접한 메모리 위치에 저장되는 요소들의 모음입니다. 배열은 인덱스를 통해 빠르게 액세스할 수 있으므로 예측 가능한 순서로 데이터를 저장하고 검색하는 데 유용합니다. 연결 리스트: 링크된 목록은 노드에 저장된 요소의 모음으로, 각 노드는 목록의 다음 노드에 대한 참조를 포..

리스트 구조에서 백만 번째 데이터를 찾기 위해 검색 속도를 줄이는 것은 목록 검색의 선형 시간 복잡성으로 인해 어려울 수 있습니다. 그러나 다음 방법들은 검색 속도를 개선하는 데 도움이 되는 몇 가지 전략입니다. 1. 인덱싱 : 한 가지 접근 방식은 데이터를 목록의 해당 위치에 매핑하는 인덱스를 만드는 것입니다. 이렇게 하면 목록에서 올바른 위치로 빠르게 이동하여 원하는 데이터를 찾을 수 있습니다. 2. 정렬(Sorting) : List의 데이터를 정렬하면 이진 검색 알고리즘을 사용하여 로그 시간으로 원하는 데이터를 찾을 수 있습니다. 3. 해시 테이블 : 또 다른 접근 방식은 해시 테이블을 사용하여 목록에 데이터를 저장하고 데이터를 해당 위치에 매핑하는 것입니다. 이를 통해 일정 시간 조회를 사용하여 ..

1. 힙이란? 힙은 동적 메모리 할당에 사용되는 프로세스의 메모리 영역입니다. 크기가 고정되어 함수 호출 및 함수 실행에 사용되는 스택과 달리 힙은 크기가 가변적이며 프로그램 실행 중에 동적으로 메모리를 할당하는 데 사용됩니다. 프로그램이 메모리를 동적으로 할당해야 하는 경우 C의 malloc 또는 C++의 new와 같은 메모리 할당 함수를 호출합니다. 메모리 할당 함수는 힙에서 사용되지 않는 메모리의 연속 블록을 찾고 블록 시작에 대한 포인터를 반환합니다. 그런 다음 프로그램은 개체, 배열 또는 동적으로 할당된 데이터 구조와 같은 데이터를 저장하기 위해 메모리를 사용할 수 있습니다. 힙은 운영 체제의 메모리 관리자가 관리하며 프로그램에서 필요에 따라 크기를 늘리거나 줄일 수 있습니다. 이를 통해 프로그..

1. 스택이란? 스택은 함수 호출 및 함수 실행과 관련된 데이터를 저장하는 프로세스의 메모리 영역입니다. 프로세스의 각 함수 호출은 함수의 반환 주소뿐만 아니라 함수의 로컬 변수 및 인수를 포함하는 스택에 새 프레임을 만듭니다. 함수가 반환되면 스택의 해당 프레임이 팝되어 함수 호출과 관련된 메모리가 해제됩니다. 스택에는 후입선출(LIFO) 데이터 구조가 있습니다. 즉, 스택에 푸시된 마지막 함수 호출이 함수가 반환될 때 가장 먼저 팝됩니다. 이렇게 하면 함수가 반환될 때 각 함수 호출에 대한 메모리가 자동으로 해제되므로 함수 호출에 사용되는 메모리를 쉽게 관리할 수 있습니다. 스택은 또한 인터럽트 또는 예외가 발생할 때마다 프로그램 카운터 및 레지스터 값을 포함하여 프로세서의 현재 상태를 저장하는 데 ..