Algorithm/Algorithm-Java

Java - 알고리즘 ( quick sort )

1. 퀵 정렬이란? 퀵 정렬 ( quick sort )이란 ? 정렬 알고리즘의 꽃 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성함 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함 함수는 왼쪽 + 기준점( pivot ) + 오른쪽을 리턴함 2. 퀵 정렬의 구현 // src/com.company/QuickSort.java package com.company; import java.util.ArrayList; import java.util.Arrays; public class QuckSort { public ArrayList splitFunc(ArrayList dataList) { if(dataList...

Java - 알고리즘 ( merge sort )

1. 병합정렬 재귀용법을 활용한 정렬 알고리즘 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 알고리즘 이해 데이터가 네 개 일떄(데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해 보자) 두 단계로 분리해서 이해할 수 있음 1단계: 정렬되지 않은 배열을 끝까지 분리하는 단계 2단계: 분리한 데이터를 단계별로 합치는 단계 예: dataList = [1, 9, 3, 2] 먼저 [1, 9], [3, 2]로 나누고 다시 앞 부분은 [1], [9]로 나누고 ( 여기까지 1단계 ) 다시 정렬해서 합친다. [1, 9] ( 이 부분부터 2단계 ) 다음..

Java-알고리즘 ( Recursive, Dynamic Programming )

재귀 고급 정렬 알고리즘에서 재귀 용법을 사용하므로, 고급 정렬 알고리즘을 익히기 전에 재귀 용법을 먼저 익혀야 한다. 함수 안에서 동일한 함수를 호출하는 형태 여러 알고리즘 작성시 사용되므로, 익숙해져야함. 간단한 예제 // src/com.company/Main.java package com.company; import java.util.ArrayList; import java.util.List; public class Main { public static Integer[] dp = new Integer[100]; static Integer recursiveFunction(Integer targetNumber) { if(targetNumber < 0) { return 0; } if(targetNumbe..

Java-알고리즘 ( insertion sort )

1. 삽입 정렬 (insertion sort)란? 삽입 정렬은 두 번쨰 인덱스부터 시작 해당 인덱스(key 값)앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B 값을 뒤 인덱스로 복사 이를 key값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동 2. 어떻게 코드로 만들까? 알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다. 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 비교 로직을 이해해보자) 예: dataList: [9, 3, 2, 5] 처음 한번 실행하면, key값은 9, 인덱스(0) - 1 은 0보다 작으므로 끝: [9, 3, 2, 5] 두 번째 실행하면, key값은 3 9보다 3이 작으므로 자..