본문 바로가기
728x90
반응형

Java/Java 알고리즘

 (37)
[알고리즘] 2-2. 순열 순열 (Permutation) -> 가능한 열의 순서 (n개면 n!) 첫 번째 원소를 임의로 지정하고, 나머지의 순열을 출력 -> 지정하는 원소의 개수를 하나씩 늘려가면서 순열 출력 즉, 집합 S의 각 원소 x에 대해서 S-{x}의 모든 순열을 생성 후, 각각의 맨 앞에 x를 추가해 출력한다. 순환함수가 데이터 변경시, 호출 전후에 데이터가 변경되지 않고 유지되도록 정의 [데이터의 동일성 유지] -> data [0...k-1]을 prefix로, data[k..n]으로 만들 수 있는 모든 순열을 출력 -> 단, 배열 data에 저장된 값들의 순서는 그대로 유지 char data[] = {'a','b','c','d'}; int n=4; void perm(int k) { if (k==n) { print dat..
[알고리즘] 2-1. 멱집합 멱집합 (Powerset) n개의 원소를 갖는 집합은 2^n개의 부분집합을 갖는다. -> 부분집합에 원소를 추가한 집합들을 나열 [합집합 이용] 즉, S의 멱집합을 구한 후 각각에 집합 P를 합집합해 출력 -> 순환 함수가 두 개의 집합을 매개변수로 받도록 설계 후, 두 번째 집합의 모든 부분집합에 첫 번째 집합을 합집합해 출력 집합 S : k번째부터 n-1번째 원소를 가지는 집합 집합 P : 0번째부터 k-1번째 원소를 가지는 집합 //1. 멱집합 (Powerset) //상태공간트리 이용 private static char data[] = {'a','b','c','d','e','f'}; private static int n = data.length; private static boolean[] incl..
[알고리즘] 1-3. 재귀함수 활용 암시적 매개변수를 명시적 매개변수로 -> //1. 순차 탐색 int search(int [] data, int n, int target) { for (int i=0; i end) return -1; else if (target == data[begin]) return begin; else return search(data, begin + 1, end, target); } //data[begin]에서 data[end]까지 target을 검색 : 검색구간 시작점을 명시적 // search(data, 0, n-1, target)이면 1.과 같은 함수 //end 생략시 int search (int [] data, int begin, int target) { if (begin > data.length-1) ret..
[알고리즘] 1-2. 재귀함수 응용 수학적 계산 외에도 사용하는 재귀함수 모든 순환함수는 반복문으로 변경 가능 -> 성능을 위해 모든 반복문은 순환함수로 변경 가능 -> 단순화를 위해 [함수 호출에 따른 성능 저하 발생 가능하므로] 문자열 길이 계산 문자열 출력 문자열 뒤집어 출력 2진수로 변환 출력 배열의 합 구하기 데이터 파일로부터 n개의 정수 읽어오기 //1. 문자열 길이 계산 //이전 문자열 길이 +1 public static int length(String str) { if (str.equals("")) return 0; else return 1+ length(str.substring(1)); } //2. 문자열 출력 public static void printChars (String str) { if (str.length() =..
[알고리즘] 1-1. 재귀 함수 기본 재귀함수는 다시 반복되는 함수 -> 재귀함수를 쓰기 위해선 무한루프에 안빠지도록 설계 즉, 적어도 재귀함수에 빠지지 않는 한 가지의 경우의 수를 존재하도록 기본 구조 1~n까지의 합 n! X^n 피보나치 수열 최대 공약수 간단한 유클리드 함수 //1. 기본 구조 public static void func(int k){ if (k1인 경우) public int fibonacci (int n) { if (n
[Java 기본 알고리즘] (5) 연결리스트 package LinkedListBasic; class ListNode{ int val; ListNode next; ListNode(int x){ this.val = x; } } public class LinkedList1 { public static void main(String[] args) { ListNode l1=new ListNode(2); l1.next = new ListNode(4); l1.next.next=new ListNode(3); //[2,4,3] ListNode l2=new ListNode(5); l2.next=new ListNode(6); l2.next.next=new ListNode(2); //[5,6,2] ListNode node = solve(l1,l2); while(node..
[Java 기본 알고리즘] (6) 큐&스택 package QueuenStackBasic; import java.util.Stack; public class QueuenStack1 { public static void main(String[] args) { String[] strs = { "5", "-2", "4", "C", "D", "9", "+", "+" }; System.out.println("결과값 : "+points(strs)); } // 야구 게임 // 계산기 -> 점수 저장 및 빼기 // C: 삭제, D : 최상단의 x2 (두배) 더하기, + : 앞의 두 숫자를 이용해 구해서 더한다. public static int points(String[] strs) { // 1. ds Stack stack = new Stack(); // 2. f..
[Java 기본 알고리즘] (4) 투 포인터 package TwoPointerBasic; import java.util.HashMap; import java.util.Map; public class TwoPointer2 { public static void main(String[] args) { String s= "ccaabbb"; System.out.println(solve_map(s)); } //최대 2개의 고유 문자가 있는 가장 긴 부분 문자열 //문제 해결 public static int solve_map(String s) { //1. ds Map map = new HashMap(); int l=0, r=0, counter=0, max=0; //2. for, while -> 이중 while문이 아니라, 2행 while문 -> O(n) whi..
728x90
반응형

티스토리툴바