본문 바로가기

개발/알고리즘9

동적 계획법(DP) 완벽 가이드 DP(Dynamic Programming(동적계획법)이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말 1.1 DC(Divide and Conquer, 분할정복)과의 차이 DP는 작은 문제를 나누었을 때 작은 문제가 중복이 일어나며 단지 작은 문제로 나누어 푸는 방법 DC는 작은 문제를 나누었을 때 작은 문제가 중복이 일어나지 않음 1.2 DP 방법 모든 작은 문제들은 한번만 풀어야 한다. 정답을 구한 작은 문제를 메모해 놓고 다시 그보다 큰 문제를 풀어나갈 때 같은 방법으로 작은 문제를 해결한다. 1.3 DP의 조건 작은 문제가 반복적으로 일어나는 경우 같은 문제는 구할 때마다 정답이 같은 경우 위와 같은 조건을 만족하는 경우에만 동적프로그래밍을 사용할 수 있습니다. 작은 문제의 결과 값이 항상.. 2024. 1. 12.
[알고리즘] 알고리즘 복잡도 표현 방법 1. 알고리즘 복잡도 계산이 필요한 이유 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해 복잡도를 정의하고 계산할 수 있습니다. 하나의 문제를 푸는 알고리즘은 다양할 수 있습니다. - 정수의 절대값 구하기 - 1, -1 -> 1 - 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기 - 방법2: 정수가 음수인지 확인해서 음수일 때만 -1을 곱하기 2. 알고리즘 복잡도 계산 항목 시간 복잡도 알고리즘 실행 속도를 말합니다. 반복문이 가장 큰 영향을 미칩니다. 공간 복잡도 알고리즘이 사용하는 메모리 사이즈를 말합니다. 알고리즘 성능 표기법 Big O(빅-오) 표기법: O(N) 알고리즘 최악의 실행 시간을 표기합니다. 가장 많이/일반적으로 사용합니다. 아무리 최악의 상황이라도 이정도의 성능은 보장.. 2023. 1. 25.
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색(DFS)이란? 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 깊이 우선 탐색(DFS) 특징 Stack을 이용합니다. 자기 자신을 호출하는 순환 알고리즘의 형태이므로 재귀함수를 사용합니다. 탐색 과정에서 어떤 값을 탐색하였는지 여부를 반드시 검사해야 합니다. 깊이 우선 탐색(DFS) 동작 예시 A를 시작 지점이라 하고 A를 꺼내 스택(Stack) 저장소에 저장 합니다. A를 스택(Stack) 저장소에서 꺼낸 후 A와 인접한 B, D를 스택(Stack) 저장소에 저장합니다. D를 스택(Stack) 저장소에서 꺼낸 후 D와 인접한 A,E가 있지만 A는 이전에 탐색한 적이 있으므로 E만 스택(Stack) 저장소에 저장합니다. E를 스택(Stack) 저장소에서 꺼낸 후 E와 인접한 C.. 2023. 1. 14.
[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색(BFS)이란? 시작점으로 부터 인접한 지점을 먼저 탐색하는 방법 노드란 장소, 지점, 위치로 생각해주시면 됩니다. 시작 노드로 부터 가까운 곳을 먼저 방문하고 멀리 있는 곳을 나중에 방문하는 방법입니다. 사용 예시로는 두 장소 사이의 최단 경로, 또는 A가 B 장소에 방문하는지의 여부가 있습니다. 특징 어떤 노드를 방문했었는지의 여부를 반드시 확인해야 합니다. 큐(Queue)를 사용합니다. 너비 우선 탐색(BFS)의 과정 1. 탐색 시작 노드를 큐에 삽입 후 방문 했다는 표시를 합니다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다. 3. 2번의 과정을 큐의 크기가 0이 될때까지 반복합니다.예시) 시작 지점은 A 입니다.. 2023. 1. 13.
[알고리즘] 안정 정렬(Stable Sort) vs 불안정 정렬(Unstable Sort) 안정 정렬(Stable Sort) 안정정렬은 중복된 값끼리 정렬시 기존 순서와 동일하게 정렬하는 알고리즘입니다. 불안정 정렬(Unstable Sort) 불안정 정렬은 중복된 값끼리 정렬시 기존 순서와 동일하지 않게 정렬되는 알고리즘입니다. 예시 책 이름, 가격 으로 구성된 값들이 있는 경우 책 이름을 기준으로 정렬하는 경우 기존: (자바, 15000), (자바, 17000), (스프링, 20000), (자바, 12000), (리액트, 23000) 안정 정렬: (리액트, 23000), (스프링, 20000), (자바, 15000), (자바, 17000), (자바, 12000) -> 기존 자바책의 정렬 순서가 그대로 유지됨. 불안정 정렬: (리액트, 23000), (스프링, 20000), (자바, 12000.. 2023. 1. 9.

티스토리툴바