본문 바로가기

algorithm3

정렬 알고리즘의 성능 비교와 상황별 선택 기준 목차1. Properties to Compare2. 정렬 알고리즘들의 성능 비교3. 특정 상황에서의 정렬 알고리즘 선택 기준 1. Properties to Compare성능을 비교하기에 앞서 고려해야 할 속성들에 대해 간단히 알아보자.  ① Time Complexity Comparison- Best: 가장 효율적으로 동작할 경우의 시간 복잡도- Average: 일반적인 경우의 시간 복잡도- Worst: 최악의 경우의 시간 복잡도 ② Auxiliary Space Complexity Comparison (보조 공간 복잡도)알고리즘이 추가로 필요한 메모리 공간을 의미한다. 예를 들어, In-Place 알고리즘(ex. quick, heap)은 추가적인 공간이 거의 필요하지 않고 입력 데이터 자체를 사용해 정렬을.. 2024. 8. 7.
[자료구조] Hash Table 목차 - Intro - Array vs Hash Table - 어떻게 O(1)을 만들었을까? - Hash function과 Collision - Collision을 최소화해 보자 - JavaScript의 Hash Table - 마치면서Intro코드를 더 빠르게 만들어주는 Hash Table에 대해 배워보자! Hash Table이란 단어를 처음 들어봤어도 개발하다가 이미 써봤을 확률이 매우 높다. Hash Table은 key-value 쌍으로 데이터를 저장하는 자료구조이다. 이 자료구조는 생각보다 똑똑한 방법으로 효율성을 높이는데, 어떤 식으로 구현되어 있는지 뜯어보자. Array vs Hash Table배열은 index를 통해 데이터를 순차적으로 저장한다. 특정 index의 값을 읽거나 추가할 때는 O(.. 2024. 5. 9.
Stack 2개로 Queue, Queue 2개로 Stack 만들기 Stack 2개로 Queue를, Queue 2개로 Stack을 만드는 방법과, 그 시간복잡도에 대해 알아보겠다.  1. Stack 2개로 Queue 만들기 아이데이션inStack과 outStack이 있다. inStack의 입구가 Qin이 되고, outStack의 출구가 Qout이 된다. enqueue 호출 시 1, 2, 3번 공이 순서대로 Stack1에 입력된다. 위에서부터 [3, 2, 1] dequeue 호출 시 outStack이 비어있으면, inStack의 모든 항목을 outStack으로 이동. inStack에서 하나씩 pop해서 outStack에 push한다. 완료되면 outStack은 위에서부터 [1, 2, 3]이 되고, dequeue 호출 시 가장 위에 있는 1부터 제거된다. (그 후의 dequ.. 2024. 5. 7.

티스토리툴바