본문 바로가기

IT 공부/자료구조&알고리즘21

알고리즘 4 우선순위 큐와 힙 우선순위 큐 ; 큐의 각 요소가 우선순위를 갖는 큐 -> 삽입 시, 우선순위에 맞게 큐가 다시 정렬된다-> 제거 시, 가장 앞의 노드가 제거된다 힙 ; * 여기서 힙은 힙 순서 속성을 만족하는 이진 트리를 말하는 것으로, 프로그래밍 언어에서 말하는 자유저장소 힙이 아니다 힙순서속성; 트리 내의 모든 노드가 부모 노드보다 큰 완전 이진트리 * 힙은 단순히 힙순서속성만 만족하므로 이진트리+이진트리탐색을지원하지않는다 * 힙의 존재가치는 루트 노드가 항상 최솟값 노드라는 점! 힙의 두 가지 연산1. 새 노드 삽입- 완전이진트리를 만족하는 가장 낮은 곳으로 새 노드 삽입 판단 - 부모노드와 비교 - 부모보다 우선순위 높을 경우, 부모와 교환 -> 반복 2. 최솟값 삭제 - 최솟값 삭제 = 루트 노드 삭제 .. 2025. 2. 22.

알고리즘 3 이진탐색트리 리스트로는 이진탐색을 구현하기가 대개 어렵기 때문에,트리기반으로 데이터를 적재하고 이진탐색을 구현하는 방법이다. 탐색 자체는 리스트보다 훨씬 수월해진다. 문제는 관리 측면이다. 특히 관리 중에서도, 삭제가 그렇다. 특정 노드를 삭제하게 될 경우,삭제되는 트리의 차일드 트리의 처리를 별도로 해줘야 하기 때문이다. 1. 차일드가 없는 경우 -> 아무 문제 없다2. 차일드가 하나 있는 경우 -> 차일드를 삭제한 노드 위치에 차일드를 붙인다.3. 차일드가 둘 다 있는 경우 -> 우측 트리의 최솟값 노드를 삭제한 위치로 옮긴다 3번의 경우, 최솟값노드의 차일드 처리도 해주어야 한다.최솟값노드의 차일드는 1번째 아니면 2번째일텐데.. 2025. 2. 15.

알고리즘 2 탐색 / 순차탐색 & 이진탐색 순차 탐색 ; 말 그대로 처음부터 순차적으로 탐색하는 방식 자기 구성 순차 탐색 ; 자주 사용되는 항목을 데이터 앞쪽에 배치하여 검색 효율 향상 - 전진이동법 ; 피탐색시, 가장 앞으로 이동- 전위법 ; 피탐색시, 하나 앞으로 이동 - 빈도 계수법 ; 데이터를 탐색되 횟수에 맞게 정렬 이진탐색 ; 최대 비교 반복횟수는 log2n으로 빠르게 찾을 수 있음 C에는 기본으로 qsort / bsearch 함수를 제공합니다... GitHub - Sukmin-LanternK/AlgorithmContribute to Sukmin-LanternK/Algorithm development by creating an account on GitHub.github.com 2025. 2. 9.

알고리즘 1 조회 (버블/삽입/퀵) 버블 정렬 : 가장 느린 정렬 방법순차적으로 앞-뒤 2개의 데이터 쌍을 비교하여 순서를 바꿔서 정렬하는 방법 무조건 n(n-1)/2의 비교횟수가 발생한다 삽입 정렬 : 순차적으로 자료구조를 순회하면서, 순서에 어긋날 경우, 바른 위치에 바로 삽입최대 n(n-1)/2의 비교횟수가 발생최소 n-1의 비교횟수가 발생한다 퀵 정렬 : 기준 요소 선정 -> 분할 반복 뉴턴 메서드를 정렬에 사용하는 방법기준 요소 선정에 따라, 그 성능이 좌우된다. 매우 이상적인 최상의 조건인 경우 log2N번의 재귀호출로 연산이 종료된다 각 재귀호출 마다, n번의 비교가 발생하므로Nlog2N의 비교횟수가 발생한다. 반대로, 최악의 경우 n(n-1)/2의 비교횟수가 발생한다 GitHub - Sukmin-LanternK/Algor.. 2025. 2. 1.

자료구조 8 이진트리 일반적인 트리의 문제는 자식 노드의 갯수가 통제가 되지 않는다는 점이다. 따라서, 데이터를 조회하는 데 드는 시간을 제어하기 어렵다. 이진 트리는 자식 노드의 갯수를 2개로 제한한다. 하나의 기준을 가지고 이분하여 노드를 구성하기 때문에조회에 있어서 탁월한 성능을 가질 수 밖에 없다마치, 미분에서 뉴턴 메서드 처럼 말이다 이진트리의 순회 방법에는 총 3가지가 있다.1. 전위 순회: 뿌리노드부터 시작 -> 왼쪽 자식노드 -> 오른쪽 자식노드 2. 중위 순회: 왼쪽 하위 자식 노드 부터 왼쪽 트리-> 뿌리노드 -> 오른쪽 하위 자식 노드부터 하위 트리 3. 후위 순회 : 왼쪽 하위 자식 노드 -> 오른쪽 하위 자식노드 -> 뿌리노드 그리고 이는 링크르 리스트 스택에서 배웠던, 수식에도 똑같이 대응해 볼.. 2025. 1. 26.

자료구조 4-1 링크드리스트스택을 활용한 계산기 링크드리스트스택을 이용한 계산기를 만들기 전에, 설명해야 할 개념이 있다. 바로, 중위표기식과 후위표기식이다. 중위표기식은 우리가 보통 사용하는 표기식이다 1+2 처럼 피연산자 사이에 연산자가 위치하는 방식이다.반면, 후위표기식은, 연산자가 피연산자 뒤에 나타난다. 12+처럼 말이다. 후위표기식을 계산하는 법은 다음과 같다.1. 숫자를 순서대로 스택에 삽입한다 2. 연산자가 나오면 스택의 피연산자 2개를 꺼내어 연산을 실행한다3. 결과값을 다시 스택에 넣는다 중위표기식을 입력으로 받아서, 바로 연산할 수 없는 이유는사칙연산 간의 우선순위 그리고 괄호의 존재 때문이다.따라서, 우선순위를 먼저 고려한 상태의 수식으로 변환시켜놓고, 계산해야하는 것이다. 그럼, 코드로 구성할 것도 크게 2가지다.1. 중위표기식.. 2025. 1. 25.

자료구조 7 트리 트리는 루트- 브랜치-리프로 이뤄지는 자료구조다.이진트리가 아닌 일반 트리 구조에서브랜치는 무수히 많이 달릴 수 있다.이 때문에, 노드를 구성하는 데 약간의 지혜가 필요하다.무턱대고 모든 차일드에 대해서 주소를 가졌다가는 노드의 크기가 무한정 늘어날 것이기 때문이다. 이런 표현상의 문제에 대한 해결책으로Left Child와 Right Sibling의 주소만을 기억하는 방법이 있다. 노드의 구조를 최대 단순하게 만드는 방법이다.하지만, 자료를 조회할 때 마냥 빠르다고 볼 수는 없다 GitHub - Sukmin-LanternK/TreeContribute to Sukmin-LanternK/Tree development by creating an account on GitHub.github.com 2025. 1. 5.

자료구조 6. 링크드 큐 링크드 큐 링크드 큐로도 구현할 수 있다.링크드 큐 특성상, 순환 큐와 달리 용량에 대한 자유도가 높게 운영할 수 있다. - Front- Rear- 노드 갯수 또한, 순환 큐처럼, 순환구조가 아니므로, 빈 상태와 꽉찬 상태를 구분하기 위한 번거로움을 거치지 않아도 된다. 따라서, 사용 자체는 링크드 큐가 편하다 하지만 ! 성능은 순환큐가 더 좋다 순환큐는 생성해놓고, 동적 메모리 관리를 지속해서 하지 않아도 되기 때문이다. 따라서, 범위가 정해져있고 고성능이 요구되는 상황이라면 순환큐를 사용하는 게 좋겠다 GitHub - Sukmin-LanternK/Data_Structure_QueueContribute to Sukmin-LanternK/Data_Structure_Queue development.. 2024. 12. 29.

자료구조 5. 순환 큐 큐 : FIFO를 구현한 자료구조 -> 퍼스트 인 퍼스트 아웃 기본적으로, AWS 공부 당시, SQS 등의 서비스에서 중요하게 접한 개념이라, 받아들이는 게 전혀 어렵지 않았다. 스택은 인/아웃이 일어나는 주소 자료구조가 Top만 추종하면 되었지만,큐는 인과 아웃의 주소가 다르므로, Front/Rear를 동시 추종하게 설계된다. 배열을 이용한 큐 -> 순환 큐 배열은 시작점과 끝이 있으므로, 전단에서 Dequeue가 일어날 때 마다,Enqueue가 가능한 가용영역이 점점 좁아진다는 문제가 있다.따라서, 일반 배열은 큐 구조로 구현할 수가 없다. 1. 이 문제를 해결하기 위해서, 마지막 노드가 첫 노드를 가리키도록순환 큐를 만듦으로써 해결 할 수 있다. 2. 한 가지 더 문제가 남아있는데, 바로 .. 2024. 12. 29.

이전 1 2 3 다음

티스토리툴바