전체 글236 버블 정렬(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. 시간복잡도(Time Complexity) 란? 시간 복잡도란? 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 가져오는 프로그램도 어떻게 작성하느냐에 따라 걸리는 시간이 달라집니다. 같은 결과를 나타내는 소스라면 최대한 시간이 적게 걸리는 소스가 좋은 소스입니다. 그렇기에 더 효율적인 알고리즘을 구성하기 위해서 시간 복잡도의 측면을 고려하고 중요하게 봅니다. 빅 - 오 표기법이란? 시간 복잡도에는 여러 개념이 있지만, 그 중 '아무리 많이 걸려도 이 시간 안에는 끝날 것'의 개념이 제일 중요하다. 최악의 경우를 발생을 예측하고, 이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라고 부른다. O(1) (constant time) : 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다... 2022. 3. 8. 완전탐색이란? 완전탐색이란? 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 일컫는다. 그리고 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다. 알고리즘이라고 부르기보단, 문제 푸는 방법이라고 이해하면 좋을 거다. Ex. 알고리즘을 모르는 상태에서, 문제를 풀 때, 가능한 모든 경우의 수를 확인해서 답을 찾아낸다. 이 과정이 완전 탐색이다. -> 이럴 경우, 수열의 수가 적을 경우에는 충분히 빠르게 해결하겠지만, 수열의 수가 억 단위일 경우에는 시간복잡도 문제가 생긴다. 따라서, 가능한 경우의 수가 많은 경우에는 이용하기 어려우므로 완전 탐색을 이용할 수 있는지 ? 잘 파악하는게 중요하다. 탐색해야 할 개수가 100만 개.. 2022. 3. 8. 이전 1 ··· 36 37 38 39 40 다음
