개발공부/알고리즘 (4) 썸네일형 리스트형 탐색 알고리즘 DFS/BFS : 파이썬(Python) DFS(Depth-First Search) DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 알기 위해 먼저 그래프(Graph)의 기본 구조를 알아야 한다. 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되 있다면 '두 노드는 인접하다' 라고 표현한다. 노드를 도시, 간선을 도로라고 생각해보면, A 라는 도시(노드)에서 B라는 도시(노드)로 이동하기 위해 , A와B를 연결하는 도로(간선)을 거친다고 이해하면 쉽다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다. 인접 행렬(.. 자료구조 기초(파이썬 : Python) 탐색(Search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 뜻한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있다. DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 하므로 사전 학습으로 스택과 큐, 재귀 함수를 알아야 한다. 자료구조(Data Structure) '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미한다. 그중 스택과 큐는 자료구조의 기초 개념으로 삽입과 삭제의 두 핵심함수로 구성된다. 삽입(Push) : 데이터 삽입 삭제(Pop) : 데이터를 삭제한다. 실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야한.. 파이썬(python) : 이진탐색 aka. 이분탐색(binary search) binary search 알고리즘은 번역해서 이진 탐색이라고도 부르고, 이분 탐색이라고도 부른다. 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다. 즉!! 원소가 정렬이 되어 있을 것(오름차순이든 내림차순이든) 원소의 Random Access가 가능해야 한다. 그리고 만약, 중복되는 원소가 있다면, 일반적인 binary search가 아닌, upper_bound와 lower_boun.. 그리디(Greedy) 알고리즘 : 파이썬(Python) https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 ko.wikipedia.org 위키백과, 우리 모두의 백과사전. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지.. 이전 1 다음
