본문 바로가기

분류 전체보기176

알고리즘 - 퀵정렬 - 호어 파티션 방식 import java.util.Arrays; public class 퀵정렬_호어파티션 { static int[] arr; static boolean[] flag; public static void main(String[] args) { arr = new int[] {3, 1, 4, 6, 9, 2, 8, 7, 5}; flag = new boolean[arr.length]; hoare(arr, 0, arr.length-1); System.out.println(Arrays.toString(arr)); } public static void hoare(int[]arr, int left, int right) { //피봇 정하기(이 경우 제일 왼쪽값으로 정한 것.) int pivot = arr[.. 2023. 3. 27.
알고리즘 - 병합정렬 - 자바코드로 구현한 병합정렬 package day0322_분할정복; import java.util.Arrays; public class 병합정렬 { static int[] arr; static int[] result; public static void main(String[] args) { arr = new int[] {3, 1, 4, 6, 9, 2, 8, 7, 5}; result = new int[arr.length]; sort(arr, 0, arr.length-1); System.out.println(Arrays.toString(result)); } public static void sort(int[]arr, int left, int right) { if(left>=right) return; //분.. 2023. 3. 27.
알고리즘 - 백트래킹&순열 몇 개의 원소를 뽑을 지에 대해서 고정된 문제라면 for문을 여러번 써서 구현할 수 있으나, 매번 뽑아야 하는 원소의 수가 변경되는 경우라면 이 방법이 불가하다. 순열을 구현할 수 있는 다양한 방법을 고려해보자. - swap 메서드를 활용한 순열 구현 import java.util.Arrays; public class 순열_swap { static int[] nums; //배열 static int N; public static void main(String[] args) { nums = new int[] {1,2,3}; N = nums.length; perm(0); } //idx : 현재 판단 하는 위치 public static void perm(int idx) { //기저조건 //N번째까지 판단을 다 .. 2023. 3. 27.
알고리즘 - 조합 - 재귀를 활용한 조합 구현1 import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class 조합_재귀 { static String[] items = {"A", "B", "C", "D"}; static int N = items.length; static int R = 2; // 몇개의 원소를 고를 것인가 static String[] sel = new String[R]; //내가 선택한 원소 static List list = new ArrayList(); public static void main(String[] args) { combination(0, 0); for(String[] strs : list) { .. 2023. 3. 26.
알고리즘 - 부분집합 - 비트마스킹을 활용한 부분집합 public class 부분집합_비트마스킹{ static String[] items = {"A", "B", "C"}; public static void main(String[] args) { //비트마스킹을 이용해보자 int N = items.length; //i는 모든 부분집합을 의미한다. for(int i = 0 ; i 2023. 3. 26.
(Java)백준 11729. 하노이 탑 이동 순서 1. 문제 조건 어릴 때 많이 해보던 하노이탑!! 내가 정말 좋아하던 놀이였다 ,, 그냥 내가 알고 있던 하노이탑 규칙 그 자체 ! 원판을 옮긴 총 개수와 옮긴 과정(원판이 원래 있던 위치 원판을 옮긴 목적지)를 각각 순차적으로 출력해야 했다. 2. 아이디어 하노이 수열의 점화식을 외워본 적이 없어서 하노이 수열의 규칙부터 찾아봐야 했다. 많은 관찰과 고민을 거듭한 끝에 점화식을 찾았고, 하노이를 옮기는 과정에 전체 솔루션 내에 작은 솔루션들을 구분할 수 있게 됐다. 알고리즘 스터디원들에게 웹엑스로 필기하며 설명해준 과정도 아래 첨부한다. 내가 사고한 과정을 최대한 그대로 설명해주려고 노력했다. 규칙을 찾아간 과정은 우선, 원판 개수에 따라서 이동 과정이나 하노이 수를 관찰하고 그 과정에서 규칙성을 발견.. 2023. 3. 26.

티스토리툴바