알고리즘/알고리즘&자료구조 (5) 썸네일형 리스트형 [알고리즘] 다이나믹 프로그래밍(Dynamic Programming) - 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말이다. - 부분 문제 반복(Overlapping subproblems)과 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. ➰ 분할정복(Divide and Conquer)과 비슷하지 않나? - 비슷하지만 결정적인 차이점이 있다. - 작은 문제가 중복이 일어나는지 안일어나는지가 분할정복과 동적 계획법의 차이다. - 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어 푸는 방법 -> 작은 문제에서 반복이 일어나지 않는다 - 동적계획법은 작은 부분 문제들이 반복된다!!!! ➰ Dynamic Prog.. [알고리즘] 정렬 알고리즘 ( 버블, 선택, 삽입, 퀵, 계수 ) 1. 버블정렬 가장 쉬운 정렬 알고리즘 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 원소를 비교하여 크기가 순서대로 되어 있지 않으면 교환 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다. 시간복잡도 O(n²) def bubble_sort(array): n = len(array) for i in range(n - 1): for j .. [알고리즘] DFS(깊이 우선 탐색) / BFS(너비 우선 탐색) 그래프를 탐색하는 방법에는 DFS와 BFS가 있는데 그 전에 그래프의 기본 구조를 알아야 한다 ✅ 그래프(Graph) - 그래프는 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종이다. - 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다 - 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다 - 그래프는 크게 2가지 방식으로 표현할 수 있다 1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 - 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비 - 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리.. [알고리즘] 이진 탐색 / 이분 탐색 (Binary Search) 순차탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용 - 시간만 충분하면 항상 원하는 데이터를 찾을 수 있음 - 자주 사용되며 구현도 간단 - 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행 def sequential_searchc(n, target, array): for i in range(n): if array[i] == target: return i + 1 # 현재위치 반환 - 시간 복잡도 O(N) 이진 탐색 / 이분 탐색 (Binary Search) 이란? - 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색.. [알고리즘] 탐욕 알고리즘(Greedy Algorithm) 탐욕 알고리즘(Greedy Algorithm) 이란? 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미한다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 최적해를 구하는 데에 사용되는 근사적인 방법이다. 그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다. (지역적(local)으로는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있음) 탐욕 알고리즘 문제를 해결.. 이전 1 다음
