[Java]Quick Sort
2023. 4. 21. 12:41
Algorithm
merge sort와 마찬가지로 분할 정복 알고리즘(divide and conquer)을 이용한 정렬 방식 divide and conquer 문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결한다. 만약 더이상 나눌 수 없다면 직접 해결한다. 💡퀵정렬 원리 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.(피봇을 선정하는 기준에 따라 다양한 퀵소트 구현 방법이 나올 수 있다.) 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗의 위치는 확정되므로 더 이상 움직이지 않는다. 분할..
[Java]Merge sort
2023. 4. 20. 16:58
Algorithm
divide and conquer 방식으로 정렬! divide and conquer 문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결한다. 만약 더이상 나눌 수 없다면 직접 해결한다 😎병합정렬 원리 예를 들어서 다음과 같은 배열이 있다고 가정하면 이 배열을 계속해서 반으로 나눌 수 있다. 그리곤 각각의 sub 부분들을 비교해서 정렬한다 원소가 하나인 경우는 그 자체로 정렬되어 있으므로 원소 2개의 비교부터 시작한다. [50,100] 배열과 [32,67] 배열을 비교해서 정렬해보자 먼저 각 배열의 첫번째 원소끼리 비교한다. 더 작은 수를 원 배열의 첫번째 인덱스에 넣고 다음 수로 넘어가 비교한다. 1. 50과 32 비교 -> 32가 더 작음 -> 배열에 첫번째 인덱스에 ..
분할 정복 정복하기~
2023. 4. 20. 15:58
Algorithm
1.divide -> 문제를 작은 크기의 서브 문제들로 나눈다. 2.conquer -> 서브 문제(Recursive Case)들을 동일하게 재귀적인 방식으로 해결한다. 만약 문제가 충분히 작아 더이상 나눌 수 없다면(Base Case) 직접 해결한다 3.combine -> sub 문제의 솔루션을 합쳐서 원문제의 솔루션을 만든다 이라는 문제 해결 전략 사용 분할 정복을 이용하는 예시 merge sort, quick sort, binary sort https://develoyummer.tistory.com/75 [Java]Merge sort divide and conquer 방식으로 정렬! divide and conquer 문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결..
[DP]백준 9095 예제 뿌시기
2023. 4. 14. 16:37
Algorithm
알고리즘을 공부하면서 똑같은 문제도 여러 가지로 풀 수 있다는 것을 느꼈다. 그리고 각 문제마다 효율적인 방법이 있다. 그래서 알고리즘 문제를 풀때 다른 풀이와 내 풀이를 비교하며 어떤게 효율적인지 생각해보는 습관이 좋은 것 같다. 다음 문제는 백준의 9095번 분제 1,2,3더하기라는 문제이다. n이 11보다 작다는 제한이 주어져서 뭔가 메모이제이션을 이용해서 풀면 굉장히 효율적일 것 같았다. 근데 어떻게 풀지 감이 안와서 처음에는 DFS를 이용해서 풀었다. 1. DFS 풀이법 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int cou..
DFS / BFS
2023. 4. 14. 14:57
Algorithm
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..
백준 10814 - 나이순 정렬 JAVA
2022. 11. 19. 15:48
Algorithm
StringBuilder객체배열을 생성한 후 카운팅 정렬을 이용하여 풀어주었다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Baek_10814 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); // 입력되는 나이의 범위 : 1 ~ 200 /..
[데일리코딩] 피보나치, 메모이제이션
2022. 11. 7. 00:30
Algorithm
피보나치 수열 중 n번째 항의 수를 리턴하는 간단한 문제였다. 입력 : int n 출력 : int타입 💡주의사항 재귀함수로 풀어야 한다 반복문의 사용이 금지된다. 아 별거아니네~ 하고 처음에는 재귀를 사용해서 룰루랄라 풀어서 제출하려고 했다. 근데 자꾸 시간초과가 뜨는 것이다.. 알고보니 재귀를 이용한 문제는 메모리를 상당히 잡아먹는 비효율적인 방법이고 위 방법대로 푼다면 함수들의 총 호출횟수가 대략 2^n 근처라서 n이 25~30 넘어가면 힘들어진다고 한다. 따라서 메모이제이션을 쓰면 효율적인 알고리즘(O(N))으로 연산을 줄일 수 있다! 🔎메모이제이션이란 이미 계산된 값을 배열에 저장하고 필요시마다 값을 불러와 쓴다. 이렇게 하여 불필요하게 중복되는 계산을 줄이는 것이다! public class fi..
[백준 2609] 최대공약수와 최소공배수, 유클리드 호제법
2022. 11. 7. 00:00
Algorithm
문제 입출력 예시 처음 풀이 처음에는 정말 최대공약수와 최소공배수 구하는 공식 그대로 생각해서 구현해서 풀었다. import java.util.Scanner; //최대공약수와 최소공배수 public class Baek_2609 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num1 = in.nextInt(); int num2 = in.nextInt(); int commonDivisor = 1; //최초 최대공약수 1로 설정 //두 수중 작은 수에서부터 돌면서 공약수를 확인 for (int i = Math.min(num1, num2); i > 1; i--) { /*만약 i가 num1과 num2의 공약수이..