Hippo's data

오늘은 퀵정렬(Quick Sort) 알고리즘에 대해 알아보겠습니다!퀵정렬은 여러 정렬 알고리즘 중 하나로 이름에서도 알 수 있듯이 빠른(Quick) 속도를 보이는 알고리즘입니다!! # 특징 - 정렬 알고리즘 - 비교 정렬: 다른 원소와 비교를 통해 정렬 수행 - 1959년 토니 호어(Tony Hoare)에 의해 개발- 분할 정복(Divide and Conquer) 방식: 나열된 수를 두개로 분할하여 각각을 해결한 후, 결과를 모아서 원래 문제를 해결# 동작 원리퀵정렬을 한문장으로 정의하면 이렇게 표현할 수 있습니다!"pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식" 동작은 크게 3가지로 확인할 수 있는데욥 1. 리스트(나열된 숫자)에서 기준값( = pivot) 선택2. 기준값( = pivot)과..

안녕하세욥! 오늘은 비교 기반의 정렬 알고리즘(Comparison-based Sorting) 시간 성능의 하한(lower bound)에 대해 알아보겠습니다!!  비교 기반의 정렬 알고리즘(Comparison-based Sorting)에는 여러 종류가 있는데욥! 버블 정렬 (Bubble Sort): 인접한 두 요소를 비교하며 정렬선택 정렬 (Selection Sort): 최솟값 또는 최댓값을 찾아가며 정렬삽입 정렬 (Insertion Sort): 정렬된 부분과 비교하며 새 요소를 삽입합병 정렬 (Merge Sort): 배열을 분할한 후 병합하면서 정렬퀵 정렬 (Quick Sort): 피벗을 기준으로 요소를 나눈 후 재귀적으로 정렬힙 정렬 (Heap Sort): 최대 힙, 최소 힙을 이용하여 정렬정렬 알고리..

오늘은 우선순위 큐 구현에 대해 알아보겠습니다! # 우선순위 큐란?일반적인 큐(queue) 구조는 선입 선출인 FIFO(First In, First Out) 방식으로 작동합니다! https://hipposdata.tistory.com/11 스택(Stack), 큐(Queue), 덱(Deque)오늘의 포스팅은 자료구조인 스택, 큐, 덱입니다!! 특히 차례대로 쌓이는 작업을 어떤 순서대로 처리할지 나타내는 자료구조들 입니다 알고리즘 문제를 풀 때 막무가내로 풀다가 시간초과가 나hipposdata.tistory.com하지만 높은 우선순위(제일 큰 값, 작은 값 등)을 기준으로 자료를 꺼낼때, 매번 모든 자료의 우선순위를 계산해야하는데욥 이를 쉽게 해결할 수 있는 데이터 구조가 우선순위 큐입니다! 우선순위 큐 구..

오늘은 투 포인터(Two Pointer) 알고리즘에 대해 알아보겠습니답! 투 포인터 알고리즘이란 쉽게 말해서 배열(array) 구조 혹은 리스트(list) 형식에서 두개의 포인터(인덱스)를 이용하여 문제를 해결하는 방법입니다이중 반복문을 사용하는 문제에서 효과적으로 시간복잡도를 줄일 수 있는데요배열의 길이만큼 최대 N번 움직이기 때문에 보통 O(N)의 시간복잡도를 갖게됩니다두개의 포인터가 순차적으로 움지기며 효율적으로 원하는 값을 찾거나 구간을 탐색할 수 있습니답 두개의 포인터는 시작지점에 따라 두가지 방식으로 구분됩니다1. 한쪽에서 출발 -> 다른쪽 끝에 도달 시 종료2. 양쪽 끝에서 출발 -> 중간에서 교차할 시 종료 특히 두 요소의 합, 연속된 구간의 합을 구하는 문제에서 주로 사용되며 이중 for..

오늘은 그리디 알고리즘(Greedy Algorithm)에 대해 알아보겠습니다! 그리디 알고리즘은 탐욕법, 욕심쟁이 알고리즘으로도 불리는데욥 그리디(Greedy)는 '탐욕스러운'이라는 뜻을 의미합니다즉, 현재 상황에서 당장 좋은 것만 고르는 방법으로 문제를 푸는 알고리즘입니다!매 순간 가장 좋아보이는 선택을 하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않습니다 # 현재 상황에서 최적의 방법을 선택하게 되므로 풀이법이 항상 최적의 해를 보장할 수 있는지, 정당한지 판단 필요함  예제1) 거스름돈당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의..