탐욕(Greedy) 알고리즘 문제를 해결하는 과정에서 그 순간순간 최적이라고 생각되는 결정을 하는 방식 지역적으로 최선의 선택을 하여 전체적으로 최적의 결과를 도출하겠다. 탐욕적 선택 속성 : 현재의 선택이 그 이후의 선택에 영향을 주지 않는다. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 해결방법으로 큰 문제를 해결할 수 있다. # 1260원을 동전으로 바꾸려고 하는데 가장 적은 동전이 몇개인가? def greedy_algorithm(money): coin_type = [500, 100, 50, 10] count = 0 for coin in coin_type: count += money // coin money %= coin return count print(greedy_a..
퀵 정렬(Quick Sort) 분할 정복(Divide and Conquer) 방식을 사용하는 알고리즘 퀵 정렬은 리스트를 임의의 피벗값으로 분할하고, 피벗보다 작은 값은 왼쪽 큰 값은 오른쪽으로 이동시킨다 1. 리스트의 하나의 요소를 선택한다. 이를 피벗이라고 부른다. 2. 피벗을 기준으로 리스트를 두 부분으로 분할한다. (피벗보다 작은 부분과 피벗보다 큰 부분) 3. 각 부분 리스트의 위 과정을 재귀적으로 반복해서 리스트를 정렬한다. 평균 시간 복잡도 : O(n log n) 최악의 경우 : O(n^2) 실제 서비스에서 일반적으로 좋은 성능을 보여주며, 인-플레이스 알고리즘으로 추가 메모리를 거의 사용하지 않아 많이 사용된다. 문제 : 누락된 숫자 범위에 고유한 숫자가 nums포함된 배열이 주어지면 배열..
버블 정렬(Bubble Sort) 이웃한 두 요소를 비교하여 큰 값(작은 값)을 뒤로 거품처럼 떠오르게 하는 방식 1. 리스트의 처음부터 시작해서 이웃한 두 요소를 비교한다. 2. 만약 첫 번째 요소가 두 번째 요소보다 크다면 두 요소의 위치를 바꾼다. 3. 위 과정을 리스트의 마지막까지 반복한다. (가장 큰 값이 리스트의 마지막 위치로 이동) 4. 위 과정을 전체 리스트에 대해 반복하여 전체 리스트를 정렬한다. [29, 10, 14, 37, 13] [10, 29, 14, 37, 13] [10, 14, 29, 37, 13] [10, 14, 29, 13, 37] [10, 14, 13, 29, 37] [10, 13, 14, 29, 37] [10, 13, 14, 29, 37] 시간복잡도 : O(n^2) def..
연결 리스트(Linked List) 노드(node)들이 포인터로 서로 연결되어 있는 자료구조 노드 : 데이터와 다음 노드를 가르키는 포인터(주소) 1. 단일 연결 리스트(Singly Linked List) 각 노드는 데이터 필드와 다음 노드를 가르키는 포인터 필드로 구성된다. 마지막 노드의 포인터 필드 값은 보통 NULL이며, 이는 리스트의 끝을 나타낸다. 장점) 삽입, 삭제가 효율적이고 간단하다. 앞, 뒤 노드만 수정하면 되기 때문에 동적 크기 조정이 가능하다. 단점) 특정 위치에 직접 접근하기 위해서는 처음부터 순차적으로 탐색해야 한다. (탐색시간 증가) 2. 이중 연결 리스트(Doubly Linked List) 각 노드는 데이터 필드와 이전 노드를 가리키는 포인터 필드, 다음 노드를 가리키는 포인터..
이진 탐색(Binary Search) 이진 탐색은 정렬된 배열에서 특정 값을 찾는데 사용되는 효율적인 알고리즘 중간 값과 찾으려는 값을 비교해서 검색 범위를 절반으로 줄여나간다. 매 단계 검사해야할 요소가 절반으로 줄어들기 때문에 시간 복잡도는 O(log N)이다. 문제 : Search Insert Position 고유한 정수의 정렬된 배열과 대상 값이 주어졌을 때, 대상이 발견되면 인덱스를 반환합니다. 그렇지 않은 경우 순서대로 삽입되었을 경우의 인덱스를 반환합니다. O(log n) 시간 복잡성이 있는 알고리즘을 작성해야 합니다. 예시 1: 입력: 숫자 = [1,3,5,6], 대상 = 5 출력: 2 예시 2: 입력: 숫자 = [1,3,5,6], 대상 = 2 출력: 1 예시 3: 입력: 숫자 = [1,3..
큐 선입선출(FIFO, First-In-First-Out) 가장 처음 삽입된 요소가 가장 먼저 제거된다. Enqueue : 큐의 뒤쪽(rear)에 요소를 추가한다. Dequeue : 큐의 앞쪽(front)이 요소를 제거하고 반환한다. Front, Peek : 큐이 앞쪽에서 요소를 조회한다. 문제 : 카드 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일..
