알고리즘

🖥 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. 선택 정렬 📌 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 교환하는 과정을 반복 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
• 다음