본문 바로가기

Learning-log -CS/Data Structure & Algorithm25

(자료구조 & 알고리즘 정리) 재귀, 완전탐색, 순열, 조합, 부분집합 정리(2023.06.04) 1. 재귀 1) 개념 - 자기 자신을 다시 호출하는 함수 - 스택에 자료구조가 쌓이는 방식과 동일하게 함수가 쌓여 처리됨. 가장 최근에 호출된 함수가 종료조건(return 혹은 함수 흐름 종료)이 충족되면 함수가 종료되며 가장 상단(최근)에 쌓인 함수가 꺼내져 처리되는 방식을 따름. - 종료 조건 명시 필수. 제대로 명시하지 않을 경우, 함수가 무한히 호출되어 스택 오버플로우 발생될 수 있음. 2) 재귀( vs 반복문) 의 장단점 (1) 장점 가시성이 높음 구현이 쉬움 변수를 많이 만들 필요가 없어짐. (2) 단점 지속적으로 함수를 호출하면서 지역변수, 매개변수, 반환값 모두를 stack에 저장함으로써 선언한 변수만 사용하는 반복문에 비해 메모리를 더 많이 사용. 이는 속도저하로 이어짐. 3) 꼬리재귀 .. 2023. 6. 5.
알고리즘 - 이분탐색(Binary Search)과 매개변수 탐색(Parameter Search) (Java, Python) 1. 이분탐색1) 개념 원하는 데이터를  찾기 위해 정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이를 위해 반드시 데이터가 정렬되어 있어야 한다. 2) 알고리즘 단계1. 배열을 정렬한다. ( 기존에 배열이 정렬되어서 주어진다면 이 과정은 생략한다.)<p data-ke-size="s.. 2023. 4. 20.
알고리즘 - 퀵정렬 - 호어 파티션 방식 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.

티스토리툴바