본문 바로가기

Python/알고리즘

 (12)
[Python]버블정렬 알고리즘 코드 및 예시로 마스터 하기 이번 포스팅에서는 버블정렬 알고리즘을 파이썬으로 구현하는 것부터 시작하여 실제 예시를 통해 코딩 테스트까지 대비해보는 포스팅을 다루도록 할 것이다. 목차 1. 버블정렬의 기본 개념 2. 버블정렬(Bubble Sort) 알고리즘 원리 이해하기 3. 버블 정렬 Python 코드로 구현하기 4. 버블 정렬 시공간복잡도 계산하기 1. 버블정렬(Bubble Sort)의 기본 개념 버블정렬이란 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘을 말한다. 물론 정렬의 원칙에 따라서는 버블정렬을 내림차순으로 구현할 수도 있고, 오름차순으로 구현할 수도 있다. 이번 포스팅에서는 이 두 방법 모두 알아보고 코드로 구현해보고자 한다. 2. 버블정렬(Bubble Sor..
BFS 완벽 구현하기 - 파이썬 1. BFS 기본 개념 2. BFS 구현 원리 3. BFS 구현 코드 1. BFS 기본 개념 BFS란 그래프 자료 구조에서 원하는 자료를 찾는 탐색 알고리즘 중에 하나입니다. 자료를 찾을 때 "수직" 방향으로 자료를 검색할 수도 있고, "수평" 방향으로 자료를 검색할 수 있는데, BFS는 이름에서 추론할 수 있듯이, "수평방향"으로 원하는 노드를 탐색하는 알고리즘입니다. (DFS는 이 포스팅을 참고해주시기 바랍니다. ) 2. BFS 구현 원리 BFS를 구현하기 위해서는 항상 "방문하고자 하는 노드"와 "방문했던 노드"를 나누어서 알고리즘을 구성하는 것이 핵심 원리입니다. 논리를 3단계로 요약하면 다음과 같습니다. 1단계. 시작 노드를 방문했던 노드에 삽입한다. 2단계. 방문할 노드에 시작노드의 Child..
DFS 완벽 구현하기 [Python] 1. DFS의 기본 개념 2. 스택/큐를 활용한 DFS 구현하기 3. 재귀함수를 이용한 DFS 구현하기 1. DFS의 기본 개념 (1) 기본개념 DFS란 Depth first search의 약자로서 그래프 자료에서 데이터를 탐색하는 알고리즘입니다. 한 번 예시를 들어 보겠습니다. 오른쪽에 보이다 싶이 A부터 J까지 노드가 연결되어 있는 그래프 자료를 볼 수 있습니다. 그래프에서 특정 노드를 찾으려고 할 때, 위에서 부터 찾느냐 혹은 옆에서부터 찾느냐 그 차이가 있겠죠. 위에서 아래로 찾는 방식을 바로 DFS(Depth First Search)라고 부르는 것입니다. BFS(Breadth First Search)는 차후 포스팅에서 다루도록 하겠습니다. 참고로 위에서 아래로 탐색할 때 왼쪽으로 가냐 오른쪽으로..
그래프의 이해 - 고도 알고리즘을 위한 기초 개념 1. 그래프(Graph)란? 2. 그래프(Graph)의 관련 개념 및 용어 정리 3. 그래프(Graph)의 종류 4. 그래프(Graph)와 트리(Tree)의 구조적 차이점 1. 그래프(Graph)란? (1) 정의 : 실제 사물이나 현상을 정점(Vertex), 노드(Node), 그리고 간선(Edge)으로 표현하기 위해 사용되는 컴퓨터 프로그래밍 개념입니다. 1) 예시 - 집에서 회사로 갈 수 있는 가능한 모든 경로를 그래프로 표현한 것 (출처: www.fun-coding.org) 2. 그래프(Graph)의 관련 개념 및 용어 정리 (1) 노드(Node) : 위치를 말합니다. 원으로 표현되며, 정점(Vertex)라고 표현하기도 합니다. (2) 간선(Edge) : 위치 간 관계를 표시한 선으로, 노드 간 연결..
탐색 알고리즘 - 이진 탐색 1. 이진 탐색(Binary Search)의 기본 개념 2. 이진 탐색의 손코드 구현 3. 이진 탐색의 코드 구현 4. 문제 풀이 해답 1. 이진 탐색(Binary Search)의 기본 개념 (1) 이진 탐색의 개념 이진 탐색은 쉽게 말해서 원하는 데이터를 찾을 때 "중간을 기준으로 찾는 것"입니다. 중간에 없으면 다시 왼쪽 오른쪽을 나누어서, 거기서 또 중간 지점을 들여다 보는 방법입니다. 그냥 개념적으로 보면 이게 무슨 뻘짓인가 싶기도 하지만, 탐색 문제에서 시공간 복잡도를 굉장히 절약해줄 수 있는 강력한 Tool될 수도 있습니다. (2) 예시를 통한 코테 대비 - 병뚜껑 찾기 - 출처: www.fun-coding.org 잔재미코딩 온라인 강의 사이트입니다 잔재미코딩에서 만든 온라인 강의 리스트를 공..
탐색 알고리즘 - 순차 탐색(Sequential Search) 1. 순차 탐색(Sequential Search) 알고리즘이란? 2. 순차 탐색 구현 1. 순차 탐색(Sequential Search) 알고리즘이란? 탐색 알고리즘에서 가장 쉬운 알고리즘이라고 할 수 있는데요, 개념 자체가 정말 직관적입니다. 순차적으로 모든 인자들을 검색하다가, 원하는 데이터가 있으면 그 값을 반환하는 것입니다. 그래서 논리와 코드 구성도 굉장히 단조로운 편이죠. 2. 순차 탐색의 구현 (1) 손코딩을 통한 논리 구성 첫 번째. 원하는 데이터가 있는 경우 for i in range(데이터의 길이) if 데이터[ i ] == 원하는 데이터 값: return 인덱스, 원하는 값 두 번째. 원하는 데이터가 없는 경우 return "원하는 값이 없습니다." (2) 실제 코드 구현 1 2 3 4..
고급정렬2. 퀵정렬(Quick Sort) 완벽 마스터하기 1. 퀵정렬(Quick Sort)의 기본 개념 2. 예시를 통한 퀵정렬의 이해 3. 퀵정렬 구현하기 1. 퀵정렬(Quick Sort)의 기본 개념 (1) 퀵정렬의 기본 개념 퀵정렬은 하나의 기준점(pivot)을 정해서, 이보다 작은 것은 왼쪽으로 담고, 큰 것을 오른쪽으로 담는 함수입니다. 이 정렬이 재미있는 이유는 재귀함수를 통해서 구현한다는 점과 향후 학습할 이진트리함수나 다른 내용에서도 이해하는데 도움이 된다는 거에요. 이거는 나중에 다루기로 하겠습니다. 2. 예시를 통한 퀵정렬의 이해 (1) 예시 - [3, 9, 4, 2] 예시 데이터는 [3, 9, 4, 2]로 해보도록 하겠습니다. 기준점은 3으로 잡고, 이제 순차적으로 [9, 4, 2]를 비교해보죠. 첫 번째. 9의 경우 3보다 크기 때문에 오..
고급정렬1. 병합정렬(Merge Sort) 완벽 마스터하기 1. 병합 정렬(Merge Sort)이란? 2. 병합정렬의 예시 및 원리 이해 3. 병합 정렬의 코드 구현 1. 병합 정렬(Merge Sort)이란? (1) 병합 정렬의 개념 1) 병합 정렬은 "재귀함수"를 이용한 정렬 알고리즘입니다. 2) 병합 정렬의 순서 - 데이터를 반으로 분리한다. - 데이터의 길이가 1이 될 때까지 계속 반복적으로 분리하다. (재귀함수를 이용) - 갈라진 리스트를 병합할 때, 순서에 맞게 정렬하여 병합한다. 이 원리를 이미지로 쉽게 이해해보면 아래의 그림과 같습니다. 이미지 원본 링크 설명만으로는 바로 이해하기 쉽지 않기 때문에 한 번 예시를 통해서 원리를 다시 한 번 이해해보도록 하겠습니다. 2. 병합정렬의 예시 및 원리 이해 (1) 예시 데이터: [1, 9, 3, 2] 1) ..
728x90
반응형

티스토리툴바