CS/Datastructure & Algorithm30 버블 정렬(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. 완전탐색이란? 완전탐색이란? 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 일컫는다. 그리고 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다. 알고리즘이라고 부르기보단, 문제 푸는 방법이라고 이해하면 좋을 거다. Ex. 알고리즘을 모르는 상태에서, 문제를 풀 때, 가능한 모든 경우의 수를 확인해서 답을 찾아낸다. 이 과정이 완전 탐색이다. -> 이럴 경우, 수열의 수가 적을 경우에는 충분히 빠르게 해결하겠지만, 수열의 수가 억 단위일 경우에는 시간복잡도 문제가 생긴다. 따라서, 가능한 경우의 수가 많은 경우에는 이용하기 어려우므로 완전 탐색을 이용할 수 있는지 ? 잘 파악하는게 중요하다. 탐색해야 할 개수가 100만 개.. 2022. 3. 8. 큐(Queue) 란? 큐란 ? 먼저 넣은 데이터가 먼저나오는 FIFO 구조로 저장하는 형식을 말한다. 큐의 종류? 선형 큐는 막대모양으로 된 큐이다. 크기가 제한되어있고, 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸씩 옮겨야한다는 단점이있다. 환형 큐는 선형큐의 문제점(배열로 큐를 선언할 시, 큐의 삭제와 생성이 계속 일어났을 때, 마지막 배열에 도달한 후 실제로는 데이터 공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형큐이다. front가 큐 끝에 닳으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식이다. 우선순위 큐는 우선순위를 이용하여 우선순위가 높은 순서대로 나게 된다. 실생활 예시를 들자면, 병원에서 기존 환자들을 진료보다가, 응급환자가 오게되면 먼저 진료하게 되는 경우로 이해하면 된다. 큐.. 2022. 3. 6. 스택(Stack) 이란? 스택이란? 자료구조 중, 선형구조에 해당하는 자료구조이다. 제한적으로 접근할 수 있는 나열구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록이라고 한다. (Pushdown list) 또한, 컴퓨터에는 참조지역성이라는 것이 있습니다. 간략히 설명하자면 참조지역성은 한 번 참조된 곳은 또 참조될 확률이 굉장히 높다는 것입니다. 그 참조지역성의 원리 중에서 시간지역성의 원리라는 것이 있는데 시간지역성은 '최근' 참조된 데이터가 다시 참조될 확률이 높다는 겁니다. 스택은 그 시간지역성을 최고로 활용할 수 있는 자료구조입니다. 스택의 특징? - 제일 위의 데이터만 알 수 있다. - 쌓여가는 와중에도 스택에 쌓인 데이터 갯수는 알 수 있다. - 중간의 데이터 절대 알 수 없다. 만약 알고 .. 2022. 3. 6. 이전 1 2 3 4 다음
