LALA's blog

분할 정복 알고리즘은 문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘이다. 분할 정복 알고리즘의 핵심은 '문제를 잘게 쪼개기'라고 할 수 있다. 문제를 쪼개는 방법에 대해서는 정해진 공식이나 규칙은 없다. 이것은 알고리즘을 개발하는 개발자의 창의력에 달려있는 것이다. 다만 분할 정복 알고리즘을 설계하는 대강의 요령은 있다. 그 요령은 다음과 같다. ① 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다. ② 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 ①을 수행한다. 그렇지 않다면 하위 문제를 푼다. ③ 결합(Combine) : ②과정에서 정복된 답을 취합한..

그래프의 정점끼리의 최단 경로를 구하는 문제 1) 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 (1:1) 2) 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (1:N) 3) 하나의 목적지로 가는 모든 최단 경로를 구하는 문제 (N:1) 4) 모든 최단 경로를 구하는 문제 (N:N) 다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘이다. 사이클이 없는 방향성 그 래프에 한해서만 사용할 수 있다. 1. 다익스트라 알고리즘? Dist[] 배열에 시작점으로부터 자신에게 이르는 경로의 길이를 ∞(무한대)로 초기화 시작 정점의 경로 길이를 0으로 초기화하고(시작 정점 -> 시작 정점 거리는 0) + 방문한 정점으로 체크 방문한 정점들과 연결되..

배열 유감 임의의 디렉토리 내에 존재하는 파일의 목록으로 소트웨어가 필요로 한다면 어떻게 해야 할까? 그 디렉토리 내에 존재하는 파일은 0개일 수도, 10개일 수도, 수천, 수만 개일 수도 있다. "아, 제발 파일이 항상 10개 미만으로만 있으면 좋겠다.ㅠㅠ"라는 염원 하나로 다음과 같이 배열을 선언할 수 있을까? char* files[10]; 그렇다고 무작정 크게 선언할 수도 없다. 53365개보다 더 많은 파일이 존재할 수도 있으니 말이다. char* files[53365]; 너무 작게 선언하자니 일을 제대로 할 수가 없고 무작정 크게 선언하자니 메모리가 울 것 같다. 이 문제를 해결하기 위해 필요한 것은 배열처럼 데이터 집합을 보관하는 기능을 가지면서도, 한편으로는 배열과는 달리 유연하게 크기를 바..