김기헌
Algorithm - Quick Sort
퀵 정렬(Quick Sort): 불안정 정렬에 속하며 다른 원소와 비교만으로 정렬하는 비교 정렬이다.
분할 정복 방식으로 작동하며, 일정하게 분할하는 것이 아닌 원소들을 pivot에 따라 비균등하게 분할한다
동작 방식
1.
배열(or리스트)에서 pivot을 결정한다.
2.
pivot을 기준으로 작은 원소는 왼쪽에, 큰 원소는 오른쪽으로 옮긴다
3.
pivot을 기준으로 왼쪽 리스트와 오른쪽 리스트에서도 동일하게 새로운 pivot을 정하고 옮기는 작업을 수행한다
4.
이 동작을 부분리스트의 크기가 0이나 1이 될 때까지 반복한다
public static void quickSort(int[] arr, int start, int end) {
if (start >= end) return;
int pivot = arr[(start+end)/2], left = start, right = end;
while (left <= right) {
while (arr[left] < pivot) left++; //pivot보다 큰 값을 만날 때까지 left에 +1
while (arr[right] > pivot) right--;//pivot보다 작은 값을 만날 때 까까지 right에 +1
if(left<=right){ //left와 right에 위치한 원소 자리 교체
int tmp=arr[left];
arr[left]=arr[right];
arr[right]=tmp;
left++;
right--;
}
}
quickSort(arr, start, right);//pivot기준 왼쪽 리스트(pivot 보다 작은 값들이 있는 리스트)
quickSort(arr, left, end);//pivot기준 오른쪽 리스트
}
Java
복사
분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
분할 정복(divide and conquer) 방법
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
김상호
이가현
알고리즘
•
재귀함수
◦
자기 자신을 호출하는 함수
◦
Base case 간단히 결과를 반환하는 부분
◦
Recursive case 자기 자신을 호출하는 부분
Factorial 수학적 귀납법 정의
- n=0 일 경우, n! =1 → Base case
- n>0 일 경우, n! = n*(n-1) → Recursive case
int factor ial(int n){
if(n==0) return 1; //Base case
return n*factor(n-1); // Recursive case
Java
복사
퀵정렬
Springboot
•
◦
@Controller : 전통적인 Spring MVC 컨트롤러
◦
@RestController : Restful 웹서비스의 컨트롤러
•
배포 후 수정
docker stop <이전 container_id>
cd <project_name>
git pull
docker build -t sb-bbs5 .
docker run ~~~ -e -e
임학준
최아영
알고리즘
퀵 정렬(Quick Sort)
풀이 순서
리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.문제 풀이
리스트 사용public class QuickSort {
public List<Integer> merge(List<Integer> left, List<Integer> mid, List<Integer> right) {
List<Integer> answer = new ArrayList<>();
answer.addAll(left);
answer.addAll(mid);
answer.addAll(right);
return answer;
}
public List<Integer> quickSort(List<Integer> arr) {
if (arr.size() <= 1) return arr;
// 기준값 뽑는 로직 구현
int pivot = arr.get(arr.size() / 2); // 5
// 기준값 기준으로 왼쪽 오른쪽으로 나누어 담는 로직 구현
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
List<Integer> mid = new ArrayList<>();
for (int i = 0; i < arr.size(); i++) {
if(pivot > arr.get(i)) left.add(arr.get(i));
else if (pivot < arr.get(i)) right.add(arr.get(i));
else mid.add(arr.get(i));
}
// 리스트 합치기
return merge(quickSort(left), mid, quickSort(right));
}
public static void main(String[] args) {
var arr = new int[]{20, 18, 5, 19, 5, 25, 40, 50}; // size = 8
List<Integer> al = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
al.add(arr[i]);
}
QuickSort qs = new QuickSort();
System.out.println(qs.quickSort(al));
}
}
Java
복사
Spring Boot API
레이어드 아키텍처
•
비지니스 메소드를 별도의 Service 객체에서 구현하고 컨트롤러는 Service 객체를 사용하도록 한다.
<HospitalRepository.java>
<HospitalRestController.java>
<HospitalService.java>
<HospitalResponse.java>
<Hospital.java>
TDD
<HospitalRestControllerTest.java>
WebMvcTest
•
특정 Controller 클래스만 테스트도 가능하다.@WebMvcTest(Controller.class)
•
@MockBean으로 모의 의존관계 생성 및 주입한다.
•
MockMvc객체를 주입받아 해당 객체를 이용하여 테스트를 진행한다.
MockMvc
perform()
•
요청을 전송하는 역할을 한다.
•
결과로 ResultActions 객체를 받으며, ResultActions 객체는 리턴 값을 검증하고 확인할 수 있는 andExcpect() 메소드를 제공해줍니다.
get("url")
•
HTTP 메소드를 결정할 수 있습니다. ( get(), post(), put(), delete() )
•
인자로는 경로를 보내준다.
andExpect()
•
응답을 검증하는 역할을 한다.
•
상태코드 (status())
◦
isOk(): 200
◦
isNotFound(): 404
◦
isMethodNotAllowed(): 405
◦
isInternalServerError(): 500
◦
is(int status): status 상태 코드
•
뷰(view())
•
리다이렉트(redirect())
•
모델정보(model())
•
응답정보 검증(content())
andDo(print())
•
요청/응답 전체 메세지를 확인할 수 있다.
