Algorithm/알고리즘 정리5 [알고리즘 정리] Merge Sort ( 병합정렬 ) - O(NlogN), 추가메모리, Stable 🤔Merge Sort(병합정렬) 이란 ? 병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘 💡 과정 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할) → mergeSort() 메소드 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다. → if (start == end) return; 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복) → merge() 메소드 ⚡ 특징 시간 복잡도 : 최선, 평균, 최악 모두 $O(NlogN)$ 데이터를 “비교”하면서 찾기 때문에 비교정렬 추가 메모리 필요 .. 2024. 1. 20. [알고리즘 정리] Binary Search ( 이분 탐색 ) - O(logN), 탐색알고리즘 Binary Search (이분탐색) 이란? "정렬"되어 있는 배열에서 특정 값의 위치를 찾는 탐색알고리즘이다. 탐색하는 배열을 둘로 나누고 찾고자하는 값이 존재하는 영역만 탐색하기 때문에 전체를 탐색하는 경우보다 당연히 빠르게 찾을 수 있다. 더보기 백준 문제 1. 수 찾기 https://www.acmicpc.net/problem/1920 과정 내가 찾고자하는 값을 '타겟'이라고 하자. 이분탐색은 주로 배열에서 타겟의 위치(인덱스)를 찾고자 할 때 많이 사용된다. 1. 탐색할 배열을 정렬한다. 2. 탐색할 영역의 중앙값( = (시작점 + 끝점)/2)이 타겟과 비교한다. 2-1. 중앙값이 타겟과 같다면 중앙값의 위치를 반환하고 탐색을 종료한다. 2-2. 타겟이 중앙값보다 작다면 다음엔 중앙값을 기준으로 .. 2023. 8. 14. [알고리즘 정리] Topology Sort ( 위상 정렬 ) - O(V+E), 순서가 정해져 있는 작업, 여러 답이 존재 Topology Sort (위상 정렬) 이란? 위상 정렬은 사이클이 없는 방향그래프 (DAG: Directed Acyclic Graph)에서 각 정점의 선후를 위배하지 않고 정렬하는 알고리즘이다. 정해진 선후만 위배하지 않으면 되기 때문에 정렬된 결과가 여러개가 나올 수 있다. 작업의 순서가 정해져 있을때 일직선의 순서를 찾는 알고리즘이라고 생각하면 편하다. ex ) 집도착 → 손발 씻기 → 밥먹기 → 설거지하기 → 과제하기 → 유튜브 보기 → 잠자기 이때 주어진 엣지의 방향만 지키면 된다. 만약 기초수학 → 물리 기초수학 → 화학 이라는 선후가 주어진다면 기초수학→물리 → 화학 도 괜찮고 기초 수학 →화학 →물리 도 괜찮다 같이보면 좋은 백준 문제 더보기 백준 문제 https://www.acmicpc... 2023. 6. 26. [알고리즘 정리] Counting Sort ( 계수 정렬 ) - O(N+k), 추가 메모리, Stable Counting Sort (계수 정렬) 이란? 계수 정렬은 값을 비교하지 않고 각 값들의 개수를 세어서 그 값들이 몇번째 인덱스 부터 몇번째 인덱스까지 위치하는 지를 알아내 정렬하는 알고리즘이다. 더보기 백준 문제 https://www.acmicpc.net/problem/2751 과정 과정은 간단하다. 1. 가장 큰 값 찾기 -> 큰 값까지 인덱스를 가지는 배열 만들기 2. 만든 배열에 인덱스를 값으로 하는 값의 개수 담기 3. 각 값의 개수를 누적으로 바꾸기 4. 뒤에서부터 자리 찾아주기 위 순서에 따라서 위 arr 배열을 정렬해보자 1. 가장 큰 값을 찾는다. ➡️ max = 5 2. 각 값의 개수를 담는다. arr값을 인덱스로 하여 arr의 값의 개수를 담는 count 배열을 만든다. 3. 각 값의.. 2023. 6. 25. 아스키 코드(ASCII) 잘 쓰이는 거 모음 10진 문자 0 NULL 48 0 65 A 97 a 2023. 6. 21. 이전 1 다음 반응형
