알고리 즘알 고리즘 (3) 썸네일형 리스트형 [세번째 공부] 분할 정복을 이용한 거듭제곱 거듭제곱을 할 때 분할 정복을 이용하는 방법이다. 간단하게 x를 n번 곱하라고 하면 x * x * x ... * x 이렇게 하나씩 곱해서 시간복잡도가 O(n)이 되지만 분할정복을 이용하면 시간복잡도가 O(log n)이 된다. 이 개념과 행렬의 거듭제곱을 이용하면 피보나치 수열을 빠르게 구할 수 있다. 예제는 다음과 같다. 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net [두번째 공부] 최장 증가 부분 수열 최장 증가 부분 수열은 LIS라고도 부른다. (LIS: Longest Increasing Subsequence) 어떤 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수들을 제거하여 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 일부 혹은 전체가 오름차순으로 정렬된 수열을 '증가 부분 수열'이라 하며 이 중 가장 긴 수열을 최장 증가 부분 수열이라고 한다. LIS의 길이 구하는 문제를 해결하기 위한 알고리즘으로 2가지가 존재한다. 1. 첫번째 알고리즘(시간복잡도 O(N^2)) 새로운 배열 D를 정의하자. D[i]: A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이 A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작.. [첫번째 공부] 최단 경로 알고리즘 [출처] https://roytravel.tistory.com/340 [자료 구조] 최단 거리 알고리즘 정리 (다익스트라, 벨만 포드, 플로이드 워셜) 최단 거리 알고리즘이란 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다. 일반적으로 네비게이션과 같은 길찾기에 적용된다. 최단 거리 알고리즘 종류는 크게 3가지가 있다. 1. roytravel.tistory.com V: 정점(Vertex) E: 간선(Edge) 각 알고리즘의 시간복잡도는 다 알고 있어야지. 알고리즘명 다익스트라 알고리즘 벨만-포드 알고리즘 플로이드-워셜 알고리즘 시간복잡도 다익스트라 알고리즘이란 무엇인가. 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색알고리즘이다. 흔히 인공지능 G.. 이전 1 다음
