merge sort와 마찬가지로 분할 정복 알고리즘(divide and conquer)을 이용한 정렬 방식 divide and conquer 문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결한다. 만약 더이상 나눌 수 없다면 직접 해결한다. 💡퀵정렬 원리 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.(피봇을 선정하는 기준에 따라 다양한 퀵소트 구현 방법이 나올 수 있다.) 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗의 위치는 확정되므로 더 이상 움직이지 않는다. 분할..

DFS/BFS를 한번에 정리해 보려고 한다. DFS/BFS로 풀기 좋은 대표적 문제 유형 1.경로 탐색(최단거리/시간) 2.네트워크 유형(연결) 3.조합 유형(모든 조합 만들기) DFS (깊이 우선 탐색) 한길로 쭉 가는 유형, 재귀로 구현하는 것이 일반적! 재귀를 타고타고 가서 탈출조건에 도달하고 파라미터를 하나씩 바꿔가면서 정점을 찾는 방식 DFS문제 예 프로그래머스-타겟 넘버 class Solution { static int answer; public int solution(int[] numbers, int target) { answer =0; dfs(0,0,numbers,target); return answer; } static void dfs(int index, int sum, int[]numb..