보관57 히프 히프(heap) 개념- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진 트리- 여러 개의 값들 중 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료 구조- 히프 트리에서는 중복된 값을 허용(완전 이진 트리에서는 허용 x)- "느슨한 정렬 상태 유지": 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있는 정도- 삭제 연산마다 가장 큰 값을 찾아내기만 하면 되므로 완전히 정렬할 필요 x- 히프는 완전 이진 트리히프의 종류- 2가지의 히프 트리 존재 1. 최대 히프(max heap)- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리- key(부모 노드) ≥ key(자식 노드) 2. 최소 히프(min heap)- 부모 노드의 키 값이 자식 노드의 키 값보다 .. 2024. 8. 24. 우선순위 큐의 구현 배열을 사용하는 방법 1. 정렬되지 않은 배열 사용- 배열의 맨 끝에 새로운 요소를 추가- 삽입 시의 시간 복잡도는 O(1)- 삭제 시 우선 순위가 가장 높은 요소를 찾아야 함- 정렬되어 있지 않으므로 배열의 처음부터 끝까지 모든 요소를 스캔- 삭제 시의 시간 복잡도는 O(n) - 요소 삭제 후, 삭제된 요소 뒤에 있는 요소들을 앞으로 이동시켜야 함 2. 정렬된 배열 사용- 요소 삽입 시, 다른 요소와 값을 비교하여 적절한 삽입 위치를 결정- 삽입 위치 뒤의 요소들을 이동시켜 빈자리를 만든 다음 삽입- 삽입 시의 시간 복잡도는 O(n)- 삭제 시 맨 앞 또는 맨 뒤의 요소를 삭제하면 됨- 삭제의 시간 복잡도는 O(1)연결 리스트를 사용하는 방법- 배열을 사용한 방법과 유사 1. 정렬되지 않은 연결 리스트.. 2024. 8. 24. 우선순위 큐 우선순위 큐- 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 됨- 우선순위 큐는 데이터들이 우선 순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나가게 됨- 적절한 우선 순위를 부여하여 우선순위 큐를 스택이나 큐로 사용할 수 있음- 우선순위 큐는 0개 이상의 요소의 모임- 각 요소들은 우선 순위 값을 가지고 있음- 우선순위 큐는 최소 우선순위 큐와 최대 우선순위 큐로 나뉨최소 우선순위 큐: 우선 순위가 낮은 요소를 먼저 삭제최대 우선순위 큐: 우선 순위가 높은 요소를 먼저 삭제 2024. 8. 24. 이진 탐색 트리 이진 탐색 트리의 정의모든 원소는 유일한 키를 가짐왼쪽 서브 트리의 키들은 루트 키보다 작음오른쪽 서브 트리의 키들은 루트 키보다 큼왼쪽과 오른쪽 서브 트리 또한 이진 탐색 트리 - 찾아야 하는 값과 루트 노드의 값을 비교하여 탐색을 효율적으로 수행할 수 있음- 이진 탐색 트리에서 탐색을 구현하는 방법으로는 순환적인 방법과 반복적인 방법 2가지가 존재순환적인 탐색 연산- 특정한 키 값을 가진 노드를 찾기 위해 주어진 값과 루트 노드의 키 값을 비교- 이 결과는 아래의 3가지로 나뉨주어진 키 값과 루트 노드의 키 값이 같을 경우: 탐색 종료주어진 키 값이 루트 노드의 키 값보다 작을 경우: 루트 노드의 왼쪽 서브 트리에 대해 다시 탐색주어진 키 값이 루트 노드의 키 값보다 클 경우: 루트 노드의 오른쪽 서.. 2024. 8. 23. 웹 기초 웹 표준- 디지털 트랜스폼(digital transform) 환경에서는 웹을 다양한 스마트 기기에서 활용할 수 있게 해야 함*디지털 트랜스폼: 오프라인의 정보와 서비스를 온라인으로 옮기는 작업- 이때 모든 스마트 기기가 공유하는 표준이 웹 표준 네트워크- 네트워크는 여러 컴퓨터를 연결해 놓은 체계- 컴퓨터 간 효율적인 자료 공유를 위해 존재하는 중간 기기를 라우터(router)라 함- 라우터를 이용한 네트워크를 계속 연결하면 대형 네트워크, 즉 인터넷이 됨 서버와 클라이언트- 서버(server): 네트워크에 연결된 컴퓨터가 공개할 정보를 저장하고 클라이언트의 요청을 처리- 서버는 라우터 기능 또한 포함- 인터넷은 전 세계의 서버 컴퓨터를 연결- 클라이언트(client): 서버에 정보 공유 또는 작업 처리.. 2024. 8. 20. 스레드 이진 트리 스레드 이진 트리(threaded binary tree)- 함수를 호출해야 하므로 비효율적인 순환 호출 대신 스레드 이진 트리 사용 가능- 스택 사용 x - 트리의 노드 개수가 n개일 때- 총 링크의 개수는 2n개(각 노드 당 2개의 링크가 있으므로)- NULL이 아닌 링크의 개수는 (n-1)개- NULL인 링크의 개수는 (n+1)개 - 중위 순회 시 NULL 링크에 스레드를 저장- 선행 노드인 중위 선행자(inorder predecessor)나 후속 노드인 중위 후속자(inorder successor)를 저장해 놓은 트리가 스레드 이진 트리- 스레드를 이용하여 노드들을 순회 순서대로 연결- NULL 링크에 스레드가 저장되면, 링크에 자식을 가리키는 포인트가 저장되어 있는지 NULL 대신 스레드가 저장되.. 2024. 8. 19. 이전 1 2 3 4 5 6 7 ··· 10 다음
