반응형 2017/06100 [알고리즘] 동적 계획법(Dynamic Programming) - 1 동적 계획법(Dynamic Programming) 우리가 전에 피보나치 수를 계산하기 위해 재귀 함수를 사용했었다.이는 같은 연산이 반복되기 때문이다. 그러나 이 함수의 진행 과정을 살펴보면 중복이 심하다는 것을 알수 있다. 위의 그림에서 보면 fib(2)가 여러번 반복되며 오버헤드가 증가함으로 결국 비효율적인 코드가 된다. 따라서 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다.이는 사전에는 나오지 않는 프로그래밍 테크닉이며, 계산된 값을 버리지 말고 저장한다는 뜻이다예를 들어 위의 그림에서 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.이렇게 저장되는 배열을 '캐시'라고 하며, 중간에 저장하는 걸 '캐싱한다'라고 부른다.. 2017. 6. 6. [알고리즘] 최단경로(Shortest Path Problem) - 2 최단경로(Shortest Path Problem) - 2 위의 그림은 Bellman-ford 알고리즘의 예이다.첫번째 라운드에서 모든 엣지들에 대해서 relax 한다.relax연산이 끝나면 초기 시작점과 인접한 엣지들의 ∂값이 세팅된다.이렇게 순차작으로 relax 연산을 실행한다.위 그림은 한가지 실행 가능한 예이며, 어떠한 엣지를 선택하느냐에 따라서 다른 순서를 가진다. 이 Bellman-ford는 시간 복잡도에서 그리 좋은 알고리즘은 아니다.위의 그림은 왜 Bellman-ford의 시간 복잡도가 비효율적인지 알려준다.Bellman-ford 의 최악의 상황이 표현되었고, d[v]가 한번 갱신될때 마다 우측의 노드들의 값이 바뀐다.이는 불필요한 계산이 증가한다는 것이고, 그에따른 오버 헤드도 증가한다. .. 2017. 6. 3. [Backjoon] 11653번 문제 - 소인수분해 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 풀이 우선 2개의 반복문을 사용한다.외부에 while은 입력 받은 수가 나눗셈 연산을 거듭하면서 마지막에 1로 수렴하는 것을 판단한다.for는 나눠지는 수를 찾기 위해 i가 2부터 증가하며 만약 입력 받은 값이 i로 나눠진다면 나눈후 i값을 출력한다. 123456789101112131415161718192021import java.util.Scanner; /** * Created by homr on 2017. 6. 3.. */public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int num = sc.nextInt(); wh.. 2017. 6. 3. [알고리즘] 최단경로(Shortest Path Problem) - 1 최단경로(Shortest Path Problem) - 1 이번시간에는 그래프 알고리즘 중에서 가장중요하고 유명한 최단 경로에 대해 알아보자최단 경로는 이름 그대로 가장 짧은 경로를 찾는 것이다.먼저 최단경로 문제에서는 가중치를 가진 그래프가 주어진다.사실 최단 경로에서는 방향/무방향이 무의미하다. 따라서 방향 그래프를 예시로 설명을 진행한다. 경로의 길이를 정의해야하는데, 길이는 그 경로상에 있는 모든 가중치들의 합이다.따라서 최단 경로는 U에서 V로가는 가장 짧은 길이를 말한다.그러므로 이렇게 U에서 V까지의 최단 경로를 ∂(U,V)라고 정의한다.최단 경로 문제의 목적은 ∂(U,V)를 구하는 것이다. 최단 경로의 문제의 유형에 따라 구분을 할수 있다.먼저 하나의 출발 노드로부터 모든 노드의 최단 경로를.. 2017. 6. 2. 이전 1 ··· 19 20 21 22 23 24 25 다음 반응형
