제익

11. 그리디 알고리즘(Greedy algorithm)그리디 알고리즘 이란?현재 가능한 최선의 선택으로 문제를 해결하는 접근 방식여러 경우 중 결정의 순간이 올 때마다 최적이라고 생각되는 것을 선택해 나가는 것-> 최종적으로 봤을 대 최적의 결과를 낼 수 있다는 보장이 없음e.g.) 그리디 알고리즘을 통한 최대값 찾기 예시근노드(20)에서 시작해서 길을 찾을 때 최대값이 되는 경우를 찾을때: 그리디 알고리즘에 의하면 2, 3 중 3을 선택하게 됨: 즉, 20 -> 3 -> 1 = 24가 나옴그러나 최적의 수는 20 -> 2 -> 10 = 32[ 장점 ]계산 속도는 굉장히 빠르기 때문에 실용적임[ 단점 ]최적의 수를 구한다는 보장이 없음

10. 이진 탐색(Binary Search)이미지 출처 : https://velog.io/@blueshj610/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89Binary-Search이진탐색이란?정렬된 배열(무조건)에서 요소의 위치를 찾는 검색 알고리즘 e.g.) 이진탐색 예시(데이터 4 탐색하기)각 데이터 값이 [3, 4, 5, 6, 7, 8, 9] 인 배열중간 요소 탐색 (3+9) / 2 = 6원하는 값이 6 이하이므로 그 미만 범위의 중간 값 탐색 (3+5) / 2 = 4반복[ 장점 ]검색 속도가 빠름(최선 O(1), 평균, 최악 O(log n) )대량의 데이터를 다룰 때 유리[ 단점 ]반드시 정렬이 되어 있어야하는..

9. 선형 탐색(Linear Search)이미지 출처 : https://sustainable-dev.tistory.com/34선형 탐색이란?한쪽 끝에서 시작하여 원하는 요소를 찾을 때까지모든 요소를 확인하는 순차 검색 알고리즘.(가장 간단한 검색 알고리즘)e.g.) 선형검색 예시(데이터 1 탐색하기)각 데이터 값이 [2, 4, 0, 1, 9] 인 배열0번 인덱스부터 탐색하며 1인값 찾기데이터 값이 1인 경우 완료찾는 데이터 없을 경우 -1 반환[ 장점 ]구현이 굉장히 쉬움정렬이 필요없음[ 단점 ]배열의 길이가 길수록 시간 복잡도 증가

8. 너비 우선 탐색(BFS - Breadth-First Search)이미지 출처 : https://commons.wikimedia.org/w/index.php?curid=1864649너비 우선 탐색 (BFS - Breadth-First Search) 이란?그래프 혹은 트리 데이터 구조의 모든 정점(노드)를 검색하기 위한 재귀 알고리즘.알고리즘의 작동 순서그래프의 정점 중 하나를 대기열 뒤쪽에 배치.대기열 맨 앞 항목을 가져와 방문 목록에 추가해당 정점의 인접 노드 목록 생성방문 목록에 없는 항목을 대기열의 뒤에 추가스택이 빌 때까지 2~3 반복e.g.) BFS 예시5개의 노드를 가진 무방향 그래프'0' 부터 시작했을 때 -> 방문 목록에 0 입력 && 인접 노드를 큐에 저장큐 맨앞 요소(1) 방문 &&..

7. 깊이 우선 탐색(DFS - Depth-First Search)By Mre - 자작, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=6342841깊이 우선 탐색(DFS - Depth-First Search) 이란?그래프 혹은 트리 데이터 구조의 모든 정점(노드)를 검색하기 위한 재귀 알고리즘.알고리즘의 작동 순서그래프의 정점 중 하나를 스택 위에 놓는다.스택의 맨 위 항목을 가져와 방문 목록에 추가한다.해당 정점의 인접 노드 목록을 만든다.방문 목록에 없는 항목을 스택의 맨 위에 추가스택이 빌 때까지 2~3 반복e.g.) DFS 예시5개의 노드를 가진 무방향 그래프'0' 부터 시작했을 때 -> 방문 목록에 0 입력 && 인접 노드를 스택..

6. 힙 정렬(heap sort)By RolandH, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3330798  힙 정렬이란? 리스트를 이진 트리 구조로 배치한뒤 최대 힙을 구성하면, 근노드가 최댓값을 가지게 되는데이 최댓값을 리스트의 가장 끝으로 이동시킨 뒤 remove시킴.e.g.) 오름차순 힙 정렬 이미지By Swfung8 - 자작, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14957305[ 장점 ]시간복잡도면에서 효율적인 편추가적인 메모리 사용이 없어, 메모리 제약 상황에서도 사용 가능함[ 단점 ]불안정한 정렬(unstable)시간 복잡도 : O(nlogn)공간..

5. 퀵정렬(quick sort)By en:User:RolandH, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1965827 퀵 정렬 이란?배열 중간의 피벗(pivot) 요소를 설정한 뒤, 데이터의 비교를 통해 좌 위에 배치하는 방법e.g.) 오름차순 퀵 정렬[ 5, 3, 8, 4, 9, 1, 6, 2, 7]의 배열이 있을때5를 피벗 요소로 선택 후 작은값과 큰값을 각각 좌우에 배치-> [3, 4, 1, 2, '5(pivot)', 9, 6, 8, 7]5의 좌측 리스트(부분 리스트)에서 3를 피벗으로 설정 후 같은 패턴-> [1, 2, 3(두번째 pivot), 4, 5(첫번째 pivot) ...]5의 우측 리스트(부분 리스트)도 실행부분 ..

4. 병합정렬(merge sort)By Swfung8 - 자작, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14961648 병합 정렬이란?정렬되지 않은 리스트를 균등한 크기로 분할 후, 정복, 결합을 통해 정렬된 상태로 만드는 것  e.g.) 오름차순 병합정렬[ 27, 10, 12, 20, 25, 13, 15, 22]의 배열이 있을때 각 데이터를 분할하여 비교하는 과정을 거치면서 병합[27] vs [10], [12] vs [20], [25] vs [13], [15] vs [22][10, 27] vs [12, 20], [13, 25] vs [15, 22][10, 12, 20, 27] vs [13, 15, 22, 25][10, 12, 13,..

3. 삽입 정렬(insertion sort) 이미지 출처 :By Nuno Nogueira (Nmnogueira) - Self-made using Matlab (Originally from English Wikipedia; description page is/was here.), CC BY-SA 2.5, https://commons.wikimedia.org/w/index.php?curid=1780641삽입 정렬이란? 배열의 모든 요소를 앞에서부터 정렬된 배열 부분과 비교하며, 자신의 위치를 찾아 삽입하는 정렬방법  e.g.) 손안에 들고 있는 카드 정렬e.g.) 오름차순 삽입정렬[8, 5, 6, 2, 4]의 배열이 있을때두번째 값(5)와 첫번째 값(8) 비교 -> 값이 더 큰 8을 뒤로 보냄. [5, 8,..

2. 선택 정렬(selection sort) 이미지 출처:Marco Polo at wikipedia.org, originally uploaded at en.wikipedia.org with same filename (log), https://commons.wikimedia.org/w/index.php?curid=6503932 선택정렬이란?가장 작은 데이터를 찾아 가장 앞으로 교환하는 방식 e.g.) 오름차순 선택 정렬 1. 첫번째 인덱스부터 마지막 인덱스 사이에서 가장 작은 값을 찾아 맨앞으로 보냄. 2. 두번째 인덱스부터 마지막 인덱스 사이에서 가장 작은 값을 찾아 두번째로 보냄. ... 반복[ 장점 ] - 버블정렬과 마찬가지로 메모리 소비가 작음 [ 단점 ]- 버블정렬과 마찬가지로 시간 소비가 비효율..