본문 바로가기
반응형

알고리즘16

[알고리즘] 다이나믹 프로그래밍 (2) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 다이나믹 프로그래밍 VS 분할 정복 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다. 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다. 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다. 분할 정복의 대표적인 예시인 퀵 정렬을 살펴보자. 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않는다. 분.. 2023. 2. 16.
[알고리즘] 다이나믹 프로그래밍 (1) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상하는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운, 보텀업)으로 구성 다이나믹 프로그래밍은 동적 계획법이라고도 부른다. ■ 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다.. 2023. 2. 15.
[알고리즘] 이진 탐색 * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 이진 탐색 ● 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 ● 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀나가며 데이터를 탐색하는 방법 - 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 ■ 이진 탐색 알고리즘 예시 ■ 이진 탐색의 시간 복잡도 ● 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례한다. ● 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남는다. - 2단계를 거치면 8개 가량의 데이터만 남는다. - 3단계를 거치.. 2023. 2. 12.
[알고리즘] 정렬 (2) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 https://kks2140501.tistory.com/37 [알고리즘] 정렬 (1) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 정렬 ● 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 ● 일 kks2140501.tistory.com ■ 퀵 정렬 ● 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 ● 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 ● 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 ● 가장 기본적인.. 2023. 2. 11.
[알고리즘] 정렬 (1) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 정렬 ● 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 ● 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨 정렬의 종류와 예제에 대해서 알아보자! ■ 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 ■ 선택 정렬 소스코드(Python) 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[.. 2023. 2. 11.
[알고리즘] DFS & BFS (2) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ DFS(Depth-First Search) ● 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 ● 스택 자료구조(혹은 재귀 함수)를 이용하여, 구체적인 동작 과정은 다음과 같다 ① 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다 ② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. ③ 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 .. 2023. 2. 8.
반응형

티스토리툴바