알고리즘37 최단 경로 문제 최단 경로 알고리즘 : 가장 짦은 경로를 찾는 알고리즘 다양한 문제 상황 - 한 지점에서 다른 한 지점까지의 최단 경로 - 한 지점에서 다른 모든 지점까지의 최단 경로 - 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 최단 경로 알고리즘의 종류 다익스트라 최단 경로 알고리즘 플로이드 워셜, 벨만 포드 알고리즘 이 중 빨간색이 코딩 테스트에서 가장 많이 등장 다익스트라 최단 경로 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작 - 현실 세계의 도로(간선)은 음의 간선으로 표현 X 다익스트라 최단 경로 알고리즘은 그리디 알고리즘.. 2021. 4. 15. 다이나믹 프로그래밍(Dynamic Programming) - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 - 탑다운(top-down) or 보텀업(bottom-up) 방식 다음 조건을 만족할 때 사용 가능 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결 중복되는 부분 문제 - 동일한 작은 문제를 반복적으로 해결 예시) 피보나치 수 구하기 피보나치는 점화식(인접한 항들 사이의 관계식)으로, 현재의 항을 이전의 항에 대한 식으로 표현 가능 피보나치 수열을 아래와 같은 방법을 활용하여 구할 수 있다. #include using namespace std; // 피보나치 함수(Fibonacci Functio.. 2021. 4. 13. 이진 탐색 (binary search) 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 -이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정 중간점이 두 개라면 소수점 이하를 제거해서 중간점을 설정한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log_2*N에 비례 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장 4를 찾는다고 가정 중간점이랑 비교해서 중간보다 값이 작으면 중간점을 포함해서 오른쪽 범위를 볼 필요가 없다 이번에 보면 중간점이랑 비교해서 값이 작기 때문에 중간점을 포함해서 왼쪽 범위를 볼 필요가 없다. 원하는 값을 찾았기 때문.. 2021. 4. 13. 정렬(sorting) 알고리즘 정렬 1. 선택 정렬 처리되지 않은 데이터 중에서 [가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복] 이중 반복문을 통해 구현 선형 시간 소요 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 시간 복잡도 O(N^2) 과정 처리되지 않은 데이터 중 가장 작은 0을 선택해 가장 앞자리 7과 바꿈 처리되지 않은 데이터 중 가장 작은 1을 선택해 가장 앞자리 5과 바꿈 처리되지 않은 데이터 중 가장 작은 2을 선택해 가장 앞자리 9과 바꿈 이 과정을 반복하면 C++ 코드 #include using namespace std; int main(void) { int n = 10; int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 }; for (int i =.. 2021. 4. 13. 이전 1 2 3 4 ··· 10 다음
