🖥 CS/Algorithm

🖥 CS/Algorithm
[Algorithm] 힙 | 최대 힙, 최소 힙
heap이란? : 우선 순위 큐(priority queue)를 구현하기 위해 사용하는 자료구조 중 하나로, 완전이진트리를 base로 한 자료구조. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 점이 특징 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙 자료구조 추출되는 데이터 스택(stack) 가장 나중에 삽입된 데이터 큐(queue) 가장 먼저 삽입된 데이터 우선순위 큐(priority queue) 가장 우선 순위가 높은 데이터 최소 힙 (min heap) : 값이 가장 낮은 데이터가 먼저 삭제 import heapq heap = [] heapq.heappush(heap, 5) heapq.heap..
→2022.02.23
🖥 CS/Algorithm
[Algorithm] DFS & BFS | 그래프 탐색
※탐색: 많은 데이터에서 원하는 데이터를 찾는 과정 그래프 탐색을 위한 자료구조 (1) 스택 (2) 큐 (3) 재귀함수 (4) 그래프 DFS | 깊이 우선 탐색 : 깊은 부분을 우선적으로 탐색 👉 특정 경로로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드 방문 후 다시 돌아가 다른 노드 방문 (1) 탐색 시작 노드를 스택에 삽입하고 방문처리 ※ 방문처리: 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 check (2) 스택의 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드를 스택에 push하고 다시 돌아가 다른 노드를 방문한다. (3) (2) 과정을 반복 수행한다. 결과적으로 노드의 탐색 순서는 스택에 들어간 순서와 같다. 1 → 2 → 5 →6 → 3 → 7 → 4 → 8 첫 ..
→2021.08.14
🖥 CS/Algorithm
[Algorithm] 에라토스테네스의 체 | 소수 찾기
소수를 찾는 방법 중 하나인 에라토스테네스의 체에 대해 알아보자 원리는 다음과 같다. 💡 0부터 구하고자하는 수(n)까지 True로 채운 리스트를 생성한다. 💡 2를 제외한 2의 배수를 False로 바꾼다. 💡 3을 제외한 3의 배수를 False로 바꾼다. 💡 5를 제외한 5의 배수를 False로 바꾼다. . . . 💡n의 최대 약수는 sqrt(n) 이하이므로 sqrt(n)의 배수를 모두 False로 바꾼다. 💡2~n까지의 숫자 중 True인 숫자들이 소수가 된다. 이를 코드로 구현하면 다음과 같다. def isPrime(n): sieve = [True] * n # n의 최대 약수는 sqrt(n) 이하 m = int(n ** 0.5) for i in range(2, m+1): if sieve[i] == ..
→2021.08.01
🖥 CS/Algorithm
[Algorithm] 이진 탐색 | Binary Search
1. 순차 탐색 : 가장 기본적인 탐색 방법 - 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인 - 정렬되지 않은 리스트에서 데이터를 찾을 때 사용 - 파이썬의 count() 메서드 내부에서 순차 탐색이 사용된다. 📌 시간 복잡도: O(n) # target = 찾고자하는 원소 def search(n, target, array): for i in range(n): # 현재의 원소가 target과 동일하면 if array[i] == target: return i # 현재의 위치 인덱스 반환 2. 이진 탐색(이분 탐색) : 범위를 절반씩 나누며 탐색하는 방법 - 배열 내부 데이터가 정렬되어 있어야 사용이 가능 - 변수 3개 필요: 시작점, 끝점, 중간점 - 중간점이 실수 일 때는 소수점 이하..
→2021.07.31
🖥 CS/Algorithm
[Algorithm] 정렬 | 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
정렬이란 주어진 데이터를 특정 기준에 따라 순서대로 나열하여 재배치하는 것을 말한다. 정렬된 배열에서 원하는 값을 탐색하는 이진 탐색(Binary Search)를 위해서는 정렬 알고리즘을 잘 알아두어야 한다. 1. 선택 정렬 📌 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 교환하는 과정을 반복 swap(리스트에서 두 원소의 위치를 변경하는 작업)을 이용하면 선택정렬을 쉽게 구현할 수 있다. arr = [4,3,1,7,2,8,6,5] for i in range(len(arr)): min_index = i # 우선 가장 작은 원소의 인덱스로 맨 앞의 원소를 지정 for j in range(i+1, len(arr)): # 맨 앞 원소 제외 if arr[min_index] > arr[j]: # 가장 작은 ..
→2021.07.27
🖥 CS/Algorithm
[Algorithm] 동적 프로그래밍 | Dynamic Programming (DP)
큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법 다이나믹 프로그래밍을 사용하는 이유 1. 메모리 공간을 더 사용하더라도, 연산 속도를 증가시키기 위해 2. 중복되는 연산을 줄이기 위해 다이나믹 프로그래밍의 사용 조건 1. 최적 부분 구조 (Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때 2. 중복되는 부분 문제 - 동일한 작은 문제를 반복적으로 해결할 수 있을 때 다이나믹 프로그래밍 문제 접근 방법 - 그리디, 구현, 완전 탐색 등으로 문제를 해결할 수 있는 지 검토한 후 떠오르지 않는다면 다이나믹 프로그래밍을 고려해본다. - 재귀 함수로 작성해본 후, 작은 문제에서 ..
→2021.07.11

• 이전
• 1
• 다음