본문 바로가기

분류 전체보기236

합병 정렬 (Merge Sort) 란? 합병 정렬이란 ? 합병? 병합? 둘 다 사용해도 되는 정렬 이름이다. - 합병 : A와 B가 합쳐져서 C가 만들어진다. - 병합 : A가 B의 일부가 되거나? B가 A의 일부가 됨. 분할을 이용하는 분할 정복 알고리즘이다. 말 그대로인 배열을 쪼개서 길이가 1인 배열을 만들고, 그 이후 정렬하면서 합치는 정렬이다. 합병은 binary tree 형태로 쪼개지기 때문에 가질 수 있는 최대 깊이는 log N이 된다. 병합 정렬의 단계가 존재하는데, '분할, 정복, 결합' 3가지로 나누어 볼 수가 있다. 분할 단계 : 입력된 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복 단계 : 부분 배열을 정렬한다. (*여기서 부분 배열의 크기가 충분히 작지 않다면? '순환 호출'을 이용하여 다시 분할 정복법을 적용.. 2022. 3. 13.
셸 (Shell Sort) 정렬 란? 셸 정렬이란 ? 삽입 정렬보다 개선된 정렬이라고 생각할 수 있다. 삽입 정렬은 거의 정렬되어 있다면, 좋은 효율을 보여준다는 장점이 있었지만? 그 반대로 역순에 가까운 수열이 주어진다면 그만큼 좋지 않은 효율을 보여주었다. 그래서 "수열을 어느정도 정렬되게 바꾼 다음에 삽입 정렬을 쓰면 좋지 않을까?" 라는 생각으로 만들어 진 게 셸 정렬이다. 삽입과는 다르게 셸은 전체의 리스트를 한 번에 정렬하지 않는다. 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수(gap)의 부분 리스트로 만든 후 이 과정을 반복한다. 셸 정렬 장단점은.. 2022. 3. 13.
삽입 정렬(Insertion Sort) 란? 삽입 정렬이란? 정렬이 되어 있지 않은 '부분'의 데이터를 뽑아 정렬된 '부분'의 적절한 위치에 삽입하는 방법이다. 다시 설명하자면, 자료 배열의 모든 요스를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치에 삽입하는 정렬이다. 삽입정렬 장단점은? 이미 정렬이 되어있는 배열이 주어지면 자리 바꿈이 일어나지 않고, 딱 한 번씩 앞의 숫자와 비교 검사를 하기 때문에 이러한 Best 상황에서는 O(n)의 시간복잡도를 가진다. 거의 정렬이 되어있는 배열이라면 버블, 선택, 삽입 중에선 삽입 정렬이 가장 중요하다. 하지만, 역순으로 되어있는 배열이나, 배열의 수, 즉 길이가 길다면 그만큼 비교와 자리 바꿈 횟수가 많아지므로 삽입 정렬을 사용하기엔 부적합하다. 시간복잡도는 ? - 데이터가 이미 .. 2022. 3. 13.
선택 정렬 (Selection Sort) 란? 선택 정렬이란? 정렬 방법 중, 버블 정렬 다음으로 느린 정렬이다. 버블 정렬과 비슷하게 구현이 되며, 메모리 공간을 추가로 필요로 하지 않는다. 주어진 배열에서 최소값을 찾아 맨 앞 값과 교체를 한다. 선택 정렬 장단점은? 코드 구현이 쉽고 데이터양이 적을 때, 효율이 좋다 하지만, 데이터 양이 많을 때 효율이 떨어진다 즉, 데이터 양이 적을 때 정렬을 사용하면 좋다. 그리고 버블 정렬보다 빠르지만, 퀵, 삽입 정렬에 비해서는 느리다. 시간 복잡도는? 시간복잡도는 O(n²) 이며, 불안정 정렬(Unstable sort) 이다. 비교 시 같은 값으로 처리하지만, 실제 값이 다른 경우 정렬 후 순가 바뀔 수 있는 정렬이다. 2022. 3. 13.
버블 정렬(Bubble sort)이란? 버블 정렬이란? 뽀글뽀글 올라는 것처럼 보인다고 해서 붙여진 이름이다. 인접한 두 항목의 값을 비교해서 일정한 기준을 만족하면 서로의 값을 교환하여 정렬하는 방식이다. 오름차순 정렬은 두 항목의 값을 비교하여 앞 쪽 값이 더 크면 두 항목의 값을 교환하고 내림차순 정렬은 두 항목의 값을 비교하여 앞쪽 값이 더 작으면 두 항목의 값을 교환하는 방식. 버블 정렬의 특징은? 구현이 매우 간단한 장점 선택정렬과 유사함. 시간복잡도는? (n-1) + (n-2) + (n-3) + ... + 2 + 1 이므로, n(n-1)/2 으로 표기할 수 있다. 시간복잡도는 O(n²) 로 , 최선과 최악일 때가 동일하다. 버블정렬은 옆에 있는 숫자와 계속 비교를 해야하기 때문에 굉장히 비효율적이다. 버블 정렬의 성능 개선 방법은.. 2022. 3. 13.
그래프 탐색이란? 그래프 탐색이란? (그래프 순회 방법) 그래프 알고리즘은 여러가지 방법이 존재한다. 1. 그래프 내 모든 정점을 순회하는 방법 2. 작업 사이에 특정 의존(순서)관계가 있을 때 이를 정렬 시키는 방법 3. 루프가 없는 그래프(신장 트리)를 생성 시키는 방법 4. 최소 신장 트리를 작성하는 방법 5. 그래프 상에서 최단 경로를 탐색하는 방법 아래에 그림은 그래프 알고리즘 관련 사진이다. 다음과 같은 지형이 있을 때, 임의의 한 곳 (A,B,C,D) 에서 출발하여 a~f 까지 "모든 다리를 한 번씩 건널 수 있는 가?" 라는 문제이다. 이러한 문제를 컴퓨터에 표현하는 알고리즘이다. 여기서 그래프 탐색은, 1번 그래프 내 모든 정점을 순회하는 방법이다. 하나의 시작점 Node에서 연결된 Node들을 모두 찾는.. 2022. 3. 11.
깊이 우선 탐색(Depth-First-Search) 그래프 & 인접 행렬 & 인접리스트 https://devnuts.tistory.com/69?category=1003685 인접행렬과 인접리스트 그래프 (Graph) 수학적 정의로 그래프는 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 구조를 의미합니다. 쉽게 설명하면? 사물이나 추상적인 개념 간의 연결 관계를 표현한 것이라고 할 devnuts.tistory.com DFS 그래프 탐색의 한 종류로, 트리 순회의 방식입니다. 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색한 후, 돌아와 다른 노드로 탐색하는 방식입니다. 👇 내가 DFS가 헷갈렸던 이유 더보기 dfs 는 그래프 탐색 알고리즘이고, 트리 또는 그래프 둘 다 탐색하기 위한 알고리즘입니다. 깊이라고 생각을해서, 계.. 2022. 3. 11.
공간복잡도(Space Complexity) 란? 공간복잡도란? 프로그램 성능을 분석하는 방법 중 하나로, 프로그램이 얼마나 많은 메모리(공간)를 차지하는 가를 분석하는 방법이다. 최근에는 공간 복잡도의 중요성이 예전보다는 낮아졌다고한다. 그 이유는 반도체 기술향상이다. 메모리의 공간이 충분하기 때문에 그렇다. 공간복잡도는 총 공간요구 = 고정공간 요구 + 가변공간 요구 로 나타낼 수 있다. 수식은 S(P) = c + Sp(n)으로 표기한다. * 고정 공간(알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수 (문제의 인스턴스에 무관, 일정한 양의 메모리공간) * 가변 공간(알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간 (문제의 인스턴스에 따라 가변적인 메모리 공간) 공간복잡도를 줄이는 방법은? 고정공간 보다는 가변공간을.. 2022. 3. 11.

티스토리툴바