Velog Velog

알고리즘 문제를 풀다 보면 동적계획법에 관련된 문제들을 많이 볼 수 있다. 옛날에 알고리즘 스터디할 때 하긴 했는데 제대로 이론을 안하고 문제만 풀어서 그런지 오랜만에 코딩을 하니까 기억이 안나서 다시 공부하고 정리를 하려 한다. 다이내믹 프로그래밍, 동적계획법 (Dynamic Programming, DP) 하나의 문제는 한 번만 풀도록 하는 알고리즘, 한번 푼 것을 여러 번 다시 풀지 않는 효율적인 알고리즘 크고 어려운 문제가 있을 때 큰 문제를 잘게 나누어 해결한 뒤에 전체의 답을 구하는 방법 최적화 문제를 해결하는 데 유용함 최적화 문제 : 문제의 답이 여러 개 존재하며 가장 좋은 결과를 찾아야 하는 문제 (ex. 최단경로 문제) 다이내믹 프로그래밍을 사용하는 이유 분할-정복 기법(divide-co..

Procedure - 인접한 두 데이터를 SWAP하는 정렬 - 비교하고 교환하는 과정이 왼쪽에서부터 오른쪽으로 진행된다. - 붙어있는 데이터를 비교하는 게 거품같다고 해서 버블 정렬이라고 한다. - stable sort이다. Example - [ 5, 3, 8, 1, 2, 7] 이라는 배열 A가 있다고 하자. - 첫 번째 반복의 절차는 아래 그림과 같다. - 첫 번째 정렬이 끝나면 가장 오른쪽에 가장 큰 수인 '8'이 위치한다. - 이런 식으로 총 5번을 반복하면 [ 1, 2, 3, 5, 7, 8 ]로 정렬이 된다. 장점 - 구현이 간단하다 단점 - 어떤 데이터가 정렬 후의 위치와 같게 있다 하더라도 근접한 데이터에 따라 이동할 수 있다 (비효율적) - 한 데이터를 오른쪽으로 이동시키기 위해 모든 데이터..