목록알고리즘 (2)
good.rivening
버블 정렬 (Bubble Sort) 순서대로 근접한 두 수(연속된 두개 인덱스)를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 방법 오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장됨 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복 기본 로직 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과 바로 이전의 인덱스 값을 비교한다. 만약 이전 인덱스가 더 크면 현재 인덱스와 바꿔준다. 현재 인덱스가 더 크면 교환하지 않고 다음 두 연속된 배열 값을 비교한다. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복한다. 장점 구현이 매우 간단하다. 단점 순..
Dynamic Programming (동적 계획법) 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로, 복잡한 문제를 간단한 하위 문제로 나누어 푸는 방법이다. 동적 계획법 특징 DP는 메모리를 사용해서 실행 시간을 줄여야 하는 알고리즘으로 이전에 계산한 값을 저장하고 재활용함으로써 중복 계산을 줄이는 특징이 있다. 이 방법은 피보나치 수열 계산뿐만 아니라, 최단 경로, 최장 공통부분 문자열 등 다양한 분야에서 사용된다. 동적 계획법 방법 모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 하위 문제의 답은 어딘가에 메모해놓는다. 다시 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용하는 것이 DP 이다..