극꼼이 이야기 (GG_Tales)

1. 삽입 정렬이란? : 두번째 인덱스부터 시작해서, 앞으로 이동하면서 다른 인덱스들과 값을 비교해서 자신의 위치에 맞는 곳에 삽입하는 방식의 정렬 알고리즘. 2. 삽입 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다. * 버블정렬, 선택정렬, 삽입 정렬 모두 동일한 시간복잡도를 가집니다.

1. 선택 정렬이란? : 데이터에서 최소값을 찾아 맨 앞으로 가져오고, 옮겨둔 데이터를 제외한 나머지 리스트를 같은 방법으로 교체하는 방식의 정렬 알고리즘. 2. 선택 정렬 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다.

버블 정렬에 들어가기에 앞서, 정렬이 무엇인지 알아보겠습니다. * 정렬(sorting) : 데이터를 정해진 순서대로 나열하는 것. 1. 버블 정렬(Bubble sort) : 인접한 두개의 데이터를 비교해서 앞의 데이터가 더 작게 두 데이터의 자리를 바꾸는 정렬 알고리즘. 2. 버블 정렬 코드 구현 GitHub for문을 2번 사용했으므로 시간복잡도는 O(𝑛2)입니다. 최악의 경우에는 𝑛∗(𝑛−1)/2 번 반복해서 코드를 읽습니다.

* 시간 복잡도 : 알고리즘이 실행되는 상대적인 시간 https://geukggom.tistory.com/159 [알고리즘] 점근 표기법(Asymptotic Notation)과 빅 오의 사용 방법 1. 점근 표기법(Asymptotic Notation) : 시간복잡도를 근사치로 표현한 것입니다. 아래에서 빅 오를 예시로 들어 어떤 식으로 시간복잡도를 계산하는지에 대해 알아볼건데, 컴퓨터의 성능과는 관계없 geukggom.tistory.com 1. 공간 복잡도란? : 알고리즘이 실행될 때 필요한 저장 공간. 효율적인 알고리즘은 시작부터 결과가 나올 때까지 실행에 걸리는 시간이 짧고(작은 시간복잡도), 연산하는 컴퓨터 내의 메모리 자원을 덜 사용하는 것(작은 공간 복잡도)입니다. 시간복잡도와 공간복잡도는 반비..

1. 점근 표기법(Asymptotic Notation) : 시간복잡도를 근사치로 표현한 것입니다. 아래에서 빅 오를 예시로 들어 어떤 식으로 시간복잡도를 계산하는지에 대해 알아볼건데, 컴퓨터의 성능과는 관계없이 두 알고리즘을 비교해서 어떤 알고리즘이 더 나은 알고리즘인지, 더 빠른 알고리즘인지를 가늠할 때 사용합니다. 2. 점근 표기법의 종류 1) 빅 오 (Big O : Ο) : 알고리즘이 최악으로 실행될 경우(아무리 늦더라도 이 정도의 성능을 보장한다는 것을 의미)의 성능을 표현할 때 사용. 알고리즘의 성능을 표현하는데 가장 많이 사용. = 최악의 경우의 수에 어떤 성능을 내는지 궁금해하기 때문. 2) 빅 오메가 (Big Omega : Ω) : 알고리즘이 가장 최선으로 실행될 경우의 성능을 표시. 3)..

1. 그래프(Graph)란? 그래프란 정점과 선으로 이루어진 자료구조입니다. 더 자세한 내용은 아래 링크를 클릭해주세요. https://geukggom.tistory.com/8 [자료구조] Graph란? 1. Graph란? 정점(vertex(V))과 그 정점을 연결하는 간선(edge(E)을 하나로 모아 놓은 자료구조. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. G = (V, E) (ex) 지도, 지하철 노선도, 전기 geukggom.tistory.com - 그래프 탐색 : 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 2. BFS, DFS란? BFS : Breadth-First Search = 너비 우선 탐색. 인접한 노드를 먼저 탐색하는 방법. DFS :..