본문 바로가기
728x90

분류 전체보기302

[Algorithm] 5-(2). 정렬 - 퀵 정렬 [Algorithm] 5-(2). 정렬 - 퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다. 일반적 상황에서 가장 많이 사용된다. 병합 정렬과 더불어 대부분 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이며, 가장 기본적 퀵 정렬은 첫 번째 데이터를 기준 데이터(피봇)로 설정한다. 피봇값 설정 -> 정렬 -> 분할 -> 왼쪽 데이터 퀵정렬 -> 오른쪽 데이터 퀵정렬 5 7 9 0 3 1 6 2 4 8 첫번째 원소가 피봇으로 설정된다. 이상적인 경우 시간 복잡도가 O(NlogN)이 될 수 있다. 데이터 확인 개수가 절반씩 줄어들기 때문이다. 그러나, 최악의 경우 O(n2)의 시간 복잡도를 가진다. 2022. 4. 27.
[Algorithm] 5-(1) 정렬 - 선택 정렬, 삽입 정렬 [Algorithm] 5-(1) 정렬 - 선택 정렬, 삽입 정렬 1. 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 선형탐색으로 처리를 한다. 1) 구현 방법 이중 반복문을 통해 선택 정렬을 구현할 수 있다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] #스와프 2) 선택 정.. 2022. 4. 27.
[Algorithm] 4-(4) BFS(Breadth-First Search) [Algorithm] 4-(4) BFS(Breadth-First Search) 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선 탐색하는 알고리즘이다. BFS는 큐 자료구조를 이용한다. 동작 과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다. 더 이상 (2)번 과정을 수행할 수 없을 때 까지 반복한다. 최단 거리 목적을 달성하기 위한 알고리즘으로 사용되기도 한다. 대표 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 .. 2022. 4. 27.
[Algorithm] 4-(3). DFS(Depth-First Search) [Algorithm] 4-(3). DFS(Depth-First Search) 깊이 우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 1. 그래프의 기본구조 노드와 간선으로 표현된다. 노드를 정점이라고도 말한다. 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 두 노드가 간선으로 연결되어 있으면 인접하다고 표현한다. + 인접 행렬과 인접 리스트에 대한 개념을 확실히 해야 한다. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 파이썬에서 리스트로 행렬을 표시할 때에는 graph = [ [0, 7, 5], [7, 0, inf], [5, inf, 0] ] 이런 식으로 표현을 한다.. 2022. 4. 27.
[Algorithm] 4-(2) 재귀함수 [Algorithm] 4-(2) 재귀함수 1. 개념과 특징 자기 자신을 다시 호출하는 함수다. DFS를 실질적으로 구현하고자 할 때 사용하기도 한다. def recursive_function(): print(‘재귀 함수를 호출한다.’) recursive_function() recursive_function() 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 즉, 다시 자기자신을 부르는 return값 이외에 일정 조건(종료조건)이 되면 return 해주는 식이 있어야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. 파이썬은 최대 재귀 깊이 제한이 있다. 조건을 두지 않고 재귀적으로 함수를 호출하면 무한으로 생성되지 않고 오류가 나면서 종료된.. 2022. 4. 27.
[자료구조] 스택, 큐, 덱 [자료구조] 스택, 큐, 덱 들어가며. 스택, 큐, 덱은 알고리즘이라기 보다는 data를 관리하는 구조라고 할 수 있다. 스택, 큐, 덱을 활용한 알고리즘이 BFS, DFS 등등이 되는 것이다. 비유를 하자면, 우리가 운동할 때 힘(input)을 들여 수축과 이완(자료구조)을 통해 어떤 자세(알고리즘)를 반복 수행해서 근육을 얻고 지방을 태우는(Output) 과정을 수행하는 것에 비유를 할 수 있겠다. 운동은 굽히고 펴는 것부터 시작한다. 이처럼 기본적인 것이 자료구조이며, 이를 잘 알고 이에 대한 특성을 잘 활용할 때 좋은 알고리즘을 통해 뛰어난 프로그램을 만들 수 있는 것이다. 1. 기본적인 개념 더보기 배열(Array) vs 리스트(list) 가장 기본이 되는 순차적(sequential) 자료 구조.. 2022. 4. 27.
728x90

티스토리툴바