그리디 알고리즘은 특정 알고리즘을 구현하는 틀이나 방식이 정해져있지 않다. 그냥 그 문제를 보고 최선의 해결책을 떠올려서 믿고 가는 것이다. 맞는지 틀린지 검증해볼 방법은 직접 반례를 구성해보는 것이다. 그럼에도 몰랐던 반례가 튀어 나올 수 있고 그래서 생각을 잘해야하는 문제다. 대표적으로 분할가능한 배낭문제, 회의실 배정 문제 등이 있다. 분할가능한 배낭 문제는 배낭을 최대한 비싼 물건들로 가득채우는 문제이다. 하지만 배낭은 넣을 수 있는 무게가 정해져있기때문에 제일 가성비가 좋은 물건들로 채워야한다. 가성비 좋은 물건을 고른다는 행위 자체가 그리디한 접근방식이며 이게 그리디 알고리즘이다. 즉, 그림의 맨 밑줄을 선택해서 배낭을 채워야하는 것이다. 하지만 이런 접근 방법은 0-1배낭 문제에선 통하지 않..
class info2 implements Comparable{ int x, y,dist; public info2(int x, int y ,int dist) { this.x = x; this.y = y; this.dist=dist; } public int compareTo(info2 o) { int compare =Integer.compare(this.dist, o.dist); if(compare ==0) { compare = Integer.compare(this.x, o.x); if(compare ==0) { compare = Integer.compare(this.y, o.y); } } return compare; } } 자바는 이런 정렬이 가능하다. 구조체 정렬은 필 수 템이란 것을 잊지말도록 하자!
List Set Map 복습 List 순서 O, 중복 O set 순서 X, 중복 X Map 순서X, key중복 X, value 중복 O 오늘 Map Map 맵! Map의 특징 key와 value를 하나의 Entry로 묶어서 데이터 관리 엔트리는 "키|값" 으로 구성됌 이게 여러개 모여서 관리 되는 곳이 엔트리 키 값은 중복 허락안함 밸류는 중복이 허락됌 value는 중복이 허락됌 전화번호 값은 유니크하다.(key로 사용해야함) 사용자 이름은 유니크하지못하다.(value로 사용해야함) 맵중 많이 쓰는 맵은 HashMap 추가 put(K key, V value) 제네릭임 어떤 것이든 키 ,밸류로 사용이 가능 조회 containskey(Object key) -안에 있나? 불리언으로 리턴 containsValu..
오후 수업을 해보자! 수업을 가보자! throws 활용(키워드를 통한 처리 위임) 예외가 없어지진 않음 단순전달 전달받은 메서드는 다시 예외처리의 책임이 필요해! 처리하려는 예외의 조상 타입으로 throws처리 가능 오류메세지는 밑에서 위로 읽으면서 확인해야함 파란색 글씨 클릭하면 저절로 표시해줌 try캐치문이 없으면 계속 던지기만 한다. 어디로 던지냐? 호출한 곳으로 던짐 계속 폭탄 돌리기하다가 메인까지갔는데도 보낼 곳이 없으면 JVM한테 던짐 그럼 JVM이 프로그램멈춰버림 사용자 정의 예외 api에 정의된 exception이외에 필요에 따라 사용자 정의 예외 클래스 작성 만들때는 대부분 exception,runtimeException 클래스를 상속받아 작성 장점: 필요한 추가정보와 기능활용이 가능 코..
