코테준비 (6) 썸네일형 리스트형 그리디 알고리즘 그리디 알고리즘이란? 탐욕 기법 이라고도 불리며, 현재 상황에서 가장 좋은 해만 선택하는 것 그러므로 한번 선택을 번복하지 않는다(백트래킹 x) 그리디 알고리즘을 적용하기 위해서는 현재의 최선의 선택이 최적 해에 도달한다는 것을 확인해야 함 또한 같은 유형의 문제라도 선택지에 따라 그리디 알고리즘이 최적해를 보장하지 못할 수도 있다. 최적해임을 보장하기 위해 탐욕적 선택 + 하위 문제의 최적해가 전체 문제의 최적해임을 증명해야 한다. -> 탐욕적 선택 속성 + 최적 부분 구조그리디 알고리즘의 타당성 파악 그리디 알고리즘은 주로 귀류법(부정문에서 모순을 찾아내서 원 명제가 참임을 증명)으로 타당성이 증명되는 경우가 많다. 예시) - 회의실 배정문제 - 회의 시간이 겹치지 않으면서 최대한 많은 회의가 배정될.. 자바 - 순열/조합 generator 구현하기 기존 순열/조합 알고리즘의 문제점 기존의 순열 조합을 찾는 알고리즘은 적절한 배열이 아니더라도 끝까지 탐색을 한다는 문제점이 있다. 또한, 모든 경우의 수를 탐색하기 때문에, 경우의 수를 만드는 시간이 오래 걸린다. 예를 들어 bitmask를 이용해 조합을 만들 경우, 2^n가지의 경우를 탐색해봐야 한다. 그러나, next permutation 기법으로 생성할 경우, 함수를 호출할때만 다음 결과를 리턴하므로, 메모리와 시간 복잡도 측면에서 효율적이다. 구현 이론 가장 먼저, 정렬된 배열을 기준으로 bubble sort를 한 단계씩만 진행하는 함수를 만든다고 생각하면 쉽다. 순열 next permutation 구현 public static void main(String[] args) { int[] resu.. 연결리스트 리스트 순서를 가진 데이터의 집합 동일한 데이터를 가지고 있을 수 있다. 연결 리스트란? 메모리의 동적 할당을 기반으로 구현된 리스트 순차 리스트와의 차이 순차리스트 - 순차리스트는 배열을 기반으로 컴파일 타임에 메모리가 할당되어 크기가 변할 수 없음 - 데이터들이 메모리에 순차적으로 저장되어 있기 때문에 인덱스에 대해 바로 접근이 가능 - 마지막 원소가 아닌 임의의 인덱스의 삽입, 삭제 시 데이터를 옮기는 작업이 필요 연결리스트 - 각 원소들이 링크를 통해 연결되어 있음 - 필요에 따라 메모리를 동적할당하여 추가하기 때문에, 가변적인 메모리 사용에 효율적임 - 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 순차적이지 않기 때문에, 임의의 인덱스의 접근이 불가능 구성요소 노드 : 연결 리스트에서 하.. 알고리즘 응용 - 완전 탐색 순열(nPm) - 서로 다른 n개의 원소 중 m개를 순서를 고려하여 중복 없이 골라낸 것 ex) 6P3 #nPm 구현 #used = num이 이미 사용되었는지 확인하는 리스트 #answer = 현재 조합된 원소들을 저장하는 리스트 answer = [0,0,0] #m개의 정답을 저장 used = [False,False,False,False,False,False] #n개의 원소 사용 여부 m=3 n=6 def permutation(idx): global n,m if(idx==m): print(answer[:m]) return for num in range(n): if used[num]: continue answer[idx] = num used[num] = True permutation(idx+1) used[.. [Java_코테] 유용한 함수들 string(char) -> int Charater.getNumericValue(ch); String -> char[] str.toCharArray(); 배열 복사 // src_arr의 start_idx부터 copy_len만큼 dest의 start_idx에 복사한다. // copy_len이 src_arr의 길이를 벗어나면 default로 초기화됨 System.arrayCopy(src, src_start_idx, dest, dest_start_idx, copy_len); // original_arr을 복사하여 new_len만큼 복사한 새로운 배열을 리턴. 벗어나는 범위는 default로 초기화 Arrays.copyOf(original_arr, new_len); 배열 쉽게 출력하기 Arrays.toStrin.. [Java_코테]입출력 자바 입출력 기본 import java.util.Scanner; Scanner scanner = new Scanner(System.in); 파일 입력 Scanner(File_class) 시스템 입력 Scanner(System.in) 메소드 //정수형 scanner.nextByte() scanner.nextShort() scanner.nextInt() scanner.nextLong() //실수형 scanner.nextFloat() scanner.nextDouble() //스트링형 scanner.next() scanner.nextLine() 코테용 자바 입출력 Scanner 클래스는 속도 문제로 BufferedReader를 사용하는 것이 좋다 BufferdReader br = new BufferdReader.. 이전 1 다음