공부하는 블로그 ✍️

순차 탐색 (Sequential Search) 이진 탐색을 알아보기 전에 가장 기본적인 탐색 방법인 순차 탐색을 알아보자 리스트 안에 있는 특정한 데이터를 찾기 위해 가장 앞에서부터 데이터를 하나씩 확인하는 방법이다 정렬되어 있지 않은 리스트에서 특정 값을 찾을 때 주로 사용한다 리스트 내에 많은 데이터가 있더라도 시간만 있다면, 원하는 데이터를 찾을 수 있다 따라서 데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로, 최악의 경우 시간 복잡도는 O(N)이다 위와 같은 리스트에서 짱구를 찾을 때, 순차 탐색에서는 먼저 첫 번째 순서인 유리를 확인한다 짱구가 아니므로 그다음인 철수를 확인하고, 그다음으로 넘어가 짱구를 찾는다 순차 탐색 구현 # 순차 탐색 구현 # n:arr길이 # target..

실전문제 01) 위에서 아래로 하나의 수열에는 다양한 수가 존재한다. 수는 크기에 상관없이 나열되어 있다 이 수열의 수들을 큰수부터 작은 수의 순서로 정렬해야한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오 ✏️ 입력 조건 - 첫번째 줄에 수열에 속해 있는 수의 개수 N이 주어진다 - 두번째 줄부터 N+1 번째 줄에는 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다 - 입력 예시 3 15 27 12 🖨 출력 조건 - 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다 - 동일한 수의 순서는 자유롭게 출력해도 된다 - 출력 예시 27 15 12 💡 풀이 방법 - 파이썬의 sorted() 함수를 사용해 배열의 요소를 정렬한 뒤 순서대로 출력한다 n ..

퀵 정렬의 시간 복잡도 - 퀵 정렬의 평균 시간 복잡도는 O(NlogN) 으로 다른 정렬 알고리즘에 비해 매우 빠른 편이다 - 피벗값의 위치가 변경되어 분할이 일어날 때 마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다고 가정해보자 - 데이터의 개수를 8개라고 가정하고, 정확히 절반씩 나누어 간다는 가정을 해보자 - 이 때 높이를 확인해보면 데이터의 개수가 N 개일 때 높이는 약 logN 이라고 판단할 수 있다 - 즉, 분할이 이루어지는 횟수가 기하급수적으로 감소한다 - 데이터의 개수가 많아질수록 다른 정렬에 비해 압도적으로 빠르게 동작하게 된다 - 다만, 퀵 정렬의 평균 시간 복잡도는 O(NlogN) 이지만, 최악의 경우의 시간 복잡도는 O(N²) 이다 - 데이터가 무작위로 입력되는 경우 퀵 ..

호어 분할 방식 구현하기 / Python - 퀵 정렬에 대해 알아보고, 첫 번째 데이터를 피벗(Pivot)으로 사용하는 호어 분할 방식의 전체적인 과정은 위와 같다 - 예제로 들었던 배열을 사용해, 퀵 정렬을 파이썬으로 구현해 보도록 하자 arr = [ 5, 7, 9, 0, 3, 1, 6, 2, 4, 8 ] - 예제의 데이터를 배열의 형태로 선언하여 사용한다 def quick_sort(arr, start, end): if start >= end: # 요소가 하나인 경우 종료 return pivot = start # 호어 방식이므로 첫번째 데이터를 pivot으로 사용한다 left = start + 1 # 왼쪽 데이터는 pivot의 바로 오른쪽 데이터를 사용한다 right = end # 오른쪽 데이터로 마지..

퀵 정렬 - 퀵 정렬은 가장 많이 사용되는 알고리즘이다. - 퀵 정렬과 비교할 만큼 빠른 알고리즘에는 병합 정렬 알고리즘이 있다 - 기준을 설정하고, 다음 큰 수와 작은 수를 교환하여 리스트를 반으로 나누는 방식으로 동작한다 피벗 (Pivot) - 피벗(Pivot) : 큰 숫자와 작은 숫자를 교환할 때, 교환의 기준을 말한다 - 퀵 정렬에서는 피벗(Pivot)이 사용된다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다 - 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다 - 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬이 분류된다 호어 분할 방식(Hoare Parition) - 가장 대표적인 분할 방식인 호어 ..

📌 그래프 탐색 - 하나의 정점으로부터 시작, 차례대로 모든 정점을 방문하는 것. - 방문한 노드와, 방문할 노드를 저장해두어야 무한루프를 방지할 수 있다. - 대표적으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 💡 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 1. 너비우선 탐색(BFS) A → B → C → H → D → I → J → M → E → G → K → F → L 한 단계씩 나아가며 현재 노드와 같은 레벨에 있는 노드(형제 노드)들을 순회하는 방식. 큐(Queue) 를 사용해 선입선출(FIFO) 원칙으로 탐색. 2. 깊이 우선 탐색(DFS) A → B → C → D → E → F → G → H → I → J → K → L → M 노드 하나의 자식을 타고 끝까지 순..