IT 한입 (IT)

동적 계획법(Dynamic Programming) 하나의 큰 문제를 해결하기 위해, 큰 문제를 작은 문제들로 나누어 부분적으로 해결한 후 그로부터 파생된 값인 해를 이용하여 최종적으로 전체 문제를 해결하는 방식의 알고리즘 상향식 접근법 : 가장 최하위 문제의 해답을 구한 후, 이를 이용하여 상위 문제를 풀어나가는 방식 메모이제이션(Memoization)기법 : 프로그램 실행 시 이전에 계산한 값을 저장하여 동일한 연산/계산에 대해서 다시 수행하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술. 메모이제이션 기법을 사용하는 이유는 문제를 쪼개어 최하위 문제를 상향식 접근법으로 풀게 되면 중복되는 부분이 발생하기 때문이다. 분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서..

quick sort quick sort는 분할 정복(Devide and Conquer) 알고리즘의 하나이다. 분할과 병합의 두 단계로 나눌 수 있다. 분할 : 리스트 안에서 pivot(기준)을 잡는다. 지정된 pivot을 기준으로 잡아 pivot보다 작은 요소들은 모두 pivot의 왼쪽 리스트로 옮겨지고 pivot보다 큰 요소들은 모두 pivot의 오른쪽 리스트로 옮긴다. 분할된 왼쪽 리스트와 오른쪽 리스트는 재귀 호출을 통하여 다시 분할 단계를 거친다. 병합 : 분할 과정을 거쳐 더 이상 쪼갤 수 없는 크기까지 분할되었다면 정렬이 완료된 리스트를 차례로 병합을 진행한다. 그리고 최종적으로 정렬된 리스트가 완성된다. 알고리즘 이해하기 [3, 9, 4, 2, 1]라는 데이터를 가진 배열이 병합정렬되는 과정..

merge sort merge sort(병합정렬)는 분할 정복(Devide and Conquer)알고리즘의 하나이다. 분할과 병합의 두 단계로 나눌 수 있다. 분할 : 분할되지 않은 크기까지 분할하기. (리스트의 크기가 1이 될 때까지) 병합 : 분할된 데이터를 단계별로 합치기. 합치는 과정은 이하와 같이 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트로 옮기는 처리를 반복하여 진행된다. 알고리즘 이해하기 [3, 4, 9, 2]라는 데이터를 가진 배열이 병합정렬되는 과정은 이하와 같다. 1. [3, 4, 9, 2] → [3, 4]와 [9, 2]로 분할 2. [3, 4] → [3]과 [4]로 분할 3. [3]과 [4] → [3, 4]로 병합 4. [..

bubble sort bubble sort(버블 정렬)란 매번 연속된 두 개의 인덱스를 비교하여 정렬하는 방법이다. 버블 정렬은 첫 번째 인덱스(기준 인덱스)부터 시작 기준 인덱스 뒤에 있는 데이터와 비교하여 뒤에 있는 데이터가 크면 자리를 교체함 기준 인덱스를 한 칸 뒤 인덱스로 이동시켜 다시 비교를 진행하고 해당 과정을 마지막 인덱스 비교까지 반복함 ※ 과정을 반복할 때마다 가장 마지막에 위치하는 인덱스 값이 비교하는 값들 중에서 가장 큰 값이 위치하게 되므로 매 수열 비교 시마다 가장 마지막 수를 제외하고 진행을 하게 된다. 위와 같은 과정을 정렬이 완료될 때까지 진행을 하게 되면 정렬된 1, 2, 3, 4, 7의 정렬된 값을 가진 ArrayList가 결과로 나오게 된다. 아래 그림은 bubble ..