$$config title: ? 자바 - 알고리즘 초중급 keywords: - IT - 멋쟁이 사자처럼 자바 백엔드스쿨 3기 $$ ![img](https://i.postimg.cc/dQRWQsYw/Combination-vertical-backendschool-1.png) --- --- # 부모수업 - 부모수업 : 멋쟁이 사자처럼 자바 백엔드스쿨 3기 수업페이지 - [주소 : https://slog.gg/p/2372](https://slog.gg/p/2372) # 수업 - [주소 : https://slog.gg/p/12268](https://slog.gg/p/12268) # 관련링크 - [프로그래머스 레벨 0, 자바, 쉬운순정렬](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=0&languages=java) - [프로그래머스 레벨 1, 자바, 쉬운순정렬](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=1&languages=java) - [프로그래머스 레벨 2, 자바, 쉬운순정렬](https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&levels=2&languages=java) - [리포지터리](https://github.com/jhs512/programmers_ct_23_04_17) # 1강 - [23 04 17, ken 12268, 1강, 시작합니다.](https://youtu.be/ZQhslRWGgKg) - [리포지터리](https://github.com/jhs512/programmers_ct_23_04_17) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/59d426c) # 2강 - [23 04 17, ken 12268, 2강, TDD 방식으로 교점에 별 만들기, 시작, 설명](https://youtu.be/18t9imokIAc) - [문제 - 교점에 별 만들기](https://school.programmers.co.kr/learn/courses/30/lessons/87377?language=java) # 3강 - [23 04 17, ken 12268, 3강, 교점, 테스트케이스 {{1, -1, 0}, {2, -1, 0}}, 추가](https://youtu.be/FYKpRQw1Xug) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/9c7d933) # 4강 - [23 04 17, ken 12268, 4강, Java Visualizer 플러그인 사용법](https://youtu.be/b9IRukom9SM) # 5강 - [23 04 17, ken 12268, 5강, 교점, 구현, 테스트케이스 추가](https://youtu.be/77Pj5zTfikk) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/88b60db) # 6강 - [23 04 17, ken 12268, 6강, 교점, 리팩토링, A, B, E, C, D, F 변수를 double 타입으로, Point 클래스 도입](https://youtu.be/HXhFDZYTXKo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/5d16890) # 7강 - [23 04 17, ken 12268, 7강, 교점, 리팩토링, 테스트케이스 추가](https://youtu.be/MJA0w5JQ-PA) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/d1af57b) # 8강 - [23 04 17, ken 12268, 8강, 교점들, 구현](https://youtu.be/cp6KKwN9_B4) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/fcdd7c9) # 9강 - [23 04 17, ken 12268, 9강, 교점들, 테스트케이스 추가](https://youtu.be/7goAhtpJQII) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/e425c1d) # 10강 - [23 04 17, ken 12268, 10강, Set와 List의 비교 및 다양한 생성방식 비교](https://youtu.be/OknVRK_p5RQ) ## HashSet과 List의 비교 | 특징 | List | Set | | -- | -- | -- | | 중복가능 | 가능 | 불가능
add 할 때 마다 엘리먼트의 hashCode 함수가 실행됨(고유값(int) 리턴)
hashCode값이 겹치는 엘리먼트가 이미 등록되어 있다면
추가적인 검증(equals)을 해보고 그래도 겹치면 등록불가
풀스캔이 아닌 이진탐색으로 처리되기 때문에 중복여부 판단이 빠름 | | 순서 | 순서있음
엘리먼트마다 index가 있어서 기억함 | 순서없음
객체가 저장된 순서를 기억하고 있지 않음 | ## new ArrayList 와 List.of 의 차이점 ### 이 코드와 ```java // 뮤터블 버전(수정가능한 버전)의 리스트 List aList = new ArrayList<>(); aList.add(Point.of(1, 1)); aList.add(Point.of(2, 2)); // aList.add(Point.of(3, 3)); // 가능 ``` ### 이 코드는 둘다 엘리먼트 2개를 가지는 List를 생성한다. ```java // 이뮤터블(수정이 불가능한 버전)의 리스트 List aList = List.of(Point.of(1, 1), Point.of(2, 2)); // aList.add(Point.of(3, 3)); // 불가능 ``` ## new HashSet 과 List.of 의 차이점 ### 이 코드와 ```java // 뮤터블 버전(수정가능한 버전)의 Set Set aSet = new HashSet<>(); aSet.add(Point.of(1, 1)); aSet.add(Point.of(2, 2)); // aSet.add(Point.of(3, 3)); // 가능 ``` ### 이 코드는 둘다 엘리먼트 2개를 가지는 Set을 생성한다. ```java // 이뮤터블(수정이 불가능한 버전)의 Set Set aSet = Set.of(Point.of(1, 1), Point.of(2, 2)); // aSet.add(Point.of(3, 3)); // 불가능 ``` # 11강 - [23 04 17, ken 12268, 11강, getMinPoint, getMaxPoint, 구현, 테스트케이스 추가](https://youtu.be/397gg01ISpo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/a56b48e) # 12강 - [23 04 17, ken 12268, 12강, emptyMatrix, 구현, 테스트케이스 추가](https://youtu.be/eykJlHBZuBA) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/537c36c) # 13강 - [23 04 17, ken 12268, 13강, positivePoints, 구현, 테스트케이스 추가](https://youtu.be/BE7ydGxNgeo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/24171a4) # 14강 - [23 04 17, ken 12268, 14강, transformToMatrix, 구현, 테스트케이스 추가](https://youtu.be/1sslz-QKgk0) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/d769a87) # 15강 - [23 04 17, ken 12268, 15강, drawOnCoordinate](https://youtu.be/QCMY99PcSv8) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/2e45e3c) # 16강 - [23 04 18, ken 12268, 16강, 테스트실행순서 지정, 인텔리제이에서 스트림 디버깅 사용하는 방법, reformat code, optimize code](https://youtu.be/DH2CFRHKGNQ) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/0e094f9) # 17강 - [23 04 18, ken 12268, 17강, Set이 특정 객체가 기존 요소들과 중복되는지를 각 요소의 hashCode를 기반으로 계산한다, 이진탐색이 사용되기에 빠르게 계산됨](https://youtu.be/OaNp2W1i-0c) # 18강 - [23 04 18, ken 12268, 18강, hashCode는 사실상 객체의 고유키 역할을 하지만 해시충돌이 발생할 수 있다. 그럴 때는 equals 가 사용된다.](https://youtu.be/VfRhAnPpmpU) ## 소스코드 ```java import java.util.Set; import java.util.HashSet; class Main { public static void main(String[] args) { Long d = 10l; System.out.println(d.hashCode()); // 10, 기본타임의 hashCode는 그 자신이다. String str = "DDD"; System.out.println(str.hashCode()); // 67524, String 객체의 고유코드는 자바에서 알아서 잘 정해주니 걱정안해도 된다. Person person1 = new Person(); // 사용자 정의 객체는, 사용자(개발자)가 직접 해시코드 함수를 잘 작성해줘야 한다. person1.no = 1; person1.age = 22; System.out.println(person1.hashCode()); // 53 Person person2 = new Person(); person2.no = 1; person2.age = 22; System.out.println(person2.hashCode()); // 53 Set peopleSet = new HashSet<>(); peopleSet.add(person1); // 들어감 peopleSet.add(person2); // 들어가지 못함 System.out.println(peopleSet.size()); // 1 Person person3 = new Person(); person3.no = 2; person3.age = -9; System.out.println(person2.hashCode()); // 53, 해시충돌발생(이 person3 객체는 기존 객체들과 내용이 다르지만 해시코드가 같아지게 되었다.) peopleSet.add(person3); // 하지만 들어가진다. 왜냐하면 hashCode가 중복되는경우에 Set은 equals 를 사용해서 최종판단을 하기 때문이다. System.out.println(peopleSet.size()); // 2 } } class Person { int no; int age; // Set 에서 특정객체와 중복되는지 검사할 때 쓰이지 않는다. 해시충돌이 일어나는 경우에는 사용된다. @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Person person)) return false; if (no != person.no) return false; return age == person.age; } // Set 에서 특정객체와 중복되는지 검사할 때 쓰인다. @Override public int hashCode() { int result = no; result = 31 * result + age; return result; } } ``` # 19강 - [23 04 18, ken 12268, 19강, 정답, 구현, 테스트케이스 추가, JDK 14버전에 맞춤](https://youtu.be/xDUrVmHOseo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/0245fa5) # 20강 - [23 04 18, ken 12268, 20강, 일급 콜렉션 설명](https://youtu.be/iDNVGkHtkGw) - [글 - 일급 콜렉션 (First Class Collection)의 소개와 써야할 이유 - https://jojoldu.tistory.com/412](https://jojoldu.tistory.com/412) ## 일급 콜렉션을 사용하는 이유 1. 비지니스에 종속적인 자료구조 1. Collection의 불변성을 보장 1. 상태와 행위를 한 곳에서 관리 1. 이름이 있는 컬렉션 ## 소스코드 ```java // 콜렉션 List people1 = new ArrayList<>(); people1.add(new Person(1, 23, "홍길동")); people1.add(new Person(2, 21, "홍길순")); people1.add(new Person(3, 25, "홍길례")); // 일급 콜렉션 People people2 = People.of( new Person(1, 23, "홍길동")), new Person(2, 21, "홍길순")), new Person(3, 25, "홍길례") ); ``` # 21강 - [23 04 18, ken 12268, 21강, Points 일급 콜렉션 도입, 실패하는 테스트케이스 발생](https://youtu.be/VC1TogB3az0) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/dc07f5d) # 22강 - [23 04 18, ken 12268, 22강, Points 일급 콜렉션 도입으로 인해 실패한 테스트케이스가 통과하도록 리팩토링](https://youtu.be/5wVVfx6cgnM) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/58c69ff) # 23강 - [23 04 18, ken 12268, 23강, 남은 부분에서 Set 을 전부 Points 로 변경](https://youtu.be/OpMPf30AvDM) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/f8f5b4e) # 24강 - [23 04 18, ken 12268, 24강, Points 를 도입하고 나서 Solution 입장에서 큰 효능감을 못 느끼고 있습니다.](https://youtu.be/GU0PeWOWDto) # 25강 - [23 04 18, ken 12268, 25강, getMinPoint, getMaxPoint 를 Points 로 옮김](https://youtu.be/Ak1I4Zg4HDc) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/8034c3a) # 26강 - [23 04 18, ken 12268, 26강, positivePoints 를 Points 로 옮김](https://youtu.be/ViXOfmL1bz4) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/c0b51e3) # 27강 - [23 04 18, ken 12268, 27강, toMatrix emptyMatrix 를 Points 로 옮김](https://youtu.be/F1JojBkegpI) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/522adfd) # 28강 - [23 04 18, ken 12268, 28강, 외부에 오픈하기는 싫지만, 테스트한테만큼은 오픈하고 싶다면 디폴트 접근제어자 사용](https://youtu.be/VFZJIrQUQb8) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/03577c6) | 종류 | public | protected | default | private | | -- | -- | -- | -- | -- | | 외부호출 | 어디서나 가능 | 같은 패키지 이거나 후손이면 가능 | 같은 패키지 이면 가능 | 불가능 | | 하위 클래스에서 오버라이드 | 가능 | 가능 | 가능 | 불가능 | # 29강 - [23 04 18, ken 12268, 29강, private 메서드 호출기능 TestUt.call 구현, GPT 에게 문의 1](https://youtu.be/PHZYbCeM6R4) ## ChatGPT 질문 1 ```` 내가 자바 17 클래스를 하나 줄게 ```java class Person { private int age = 10; private int getAge() { return age; } } ``` 이해했니? ```` ## ChatGPT 질문 2 ```` ```java int age = TestUt.call(new Person(), "getAge"); // 10 리턴 ``` 위와 같이 작동하도록 TestUt 클래스를 만들어줄래? ```` ## ChatGPT 질문 2 응답 ```java import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; public class TestUt { public static int call(Object obj, String methodName) { try { Method method = obj.getClass().getDeclaredMethod(methodName); method.setAccessible(true); return (int) method.invoke(obj); } catch (NoSuchMethodException | IllegalAccessException | InvocationTargetException e) { e.printStackTrace(); } return -1; } public static void main(String[] args) { Person person = new Person(); int age = TestUt.call(person, "getAge"); System.out.println("Age: " + age); // 10 출력 } } ``` # 30강 - [23 04 18, ken 12268, 30강, private 메서드 호출기능 TestUt.call 구현, GPT 에게 문의 2, 다양한 매개변수 지원하도록](https://youtu.be/qruehGUoP_U) ## ChatGPT 질문 1 ```` 아까 Person 클래스를 다시 알려줄게 ```java class Person { private int age = 10; private int getAge() { return age; } private int getAge(Integer no1) { return age + no1; } private int getAge(Integer no1, Integer no2) { return age + no1 + no2; } private int getAge(String no1) { return age + Integer.parseInt(no1); } } ``` 이해했니? ```` ## ChatGPT 질문 2 ```` ```java int age1 = TestUt.call(new Person(), "getAge"); // 10 리턴 int age2 = TestUt.call(new Person(), "getAge", 10); // 20 리턴 int age3 = TestUt.call(new Person(), "getAge", 10, 20); // 40 리턴 int age4 = TestUt.call(new Person(), "getAge", "100"); // 110 리턴 ``` 위와 같이 작동하도록 TestUt 클래스를 다시 만들어줄래? ```` ## ChatGPT 질문 2 응답 ```java import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; public class TestUt { public static int call(Object obj, String methodName, Object... args) { try { Class[] argTypes = new Class[args.length]; for (int i = 0; i < args.length; i++) { argTypes[i] = args[i].getClass(); } Method method = obj.getClass().getDeclaredMethod(methodName, argTypes); method.setAccessible(true); return (int) method.invoke(obj, args); } catch (NoSuchMethodException | IllegalAccessException | InvocationTargetException e) { e.printStackTrace(); } return -1; } public static void main(String[] args) { Person person = new Person(); int age1 = TestUt.call(person, "getAge"); int age2 = TestUt.call(person, "getAge", 10); int age3 = TestUt.call(person, "getAge", 10, 20); int age4 = TestUt.call(person, "getAge", "100"); System.out.println("Age1: " + age1); // 10 출력 System.out.println("Age2: " + age2); // 20 출력 System.out.println("Age3: " + age3); // 40 출력 System.out.println("Age4: " + age4); // 110 출력 } } ``` # 31강 - [23 04 18, ken 12268, 31강, private 메서드 호출기능 TestUt.call 구현, GPT 에게 문의 3, 다양한 리턴타입 지원하도록](https://youtu.be/f1w6c16QXJU) ## ChatGPT 질문 1 ```` 아까 Person 클래스를 다시 알려줄게 ```java class Person { private int age = 10; private String name = "폴"; private int getAge() { return age; } private int getAge(Integer no1) { return age + no1; } private int getAge(Integer no1, Integer no2) { return age + no1 + no2; } private int getAge(String no1) { return age + Integer.parseInt(no1); } private String getName() { return name; } private String getName(String subfix) { return name + subfix; } private Person getMe() { return this; } } ``` 이해했니? "예" 혹은 "아니오" 로만 대답해줘. ```` ## ChatGPT 질문 2 ```` ```java int age1 = TestUt.call(new Person(), "getAge"); // 10 리턴 int age2 = TestUt.call(new Person(), "getAge", 10); // 20 리턴 int age3 = TestUt.call(new Person(), "getAge", 10, 20); // 40 리턴 int age4 = TestUt.call(new Person(), "getAge", "100"); // 110 리턴 String name1 = TestUt.call(new Person(), "getName"); // "폴" 리턴 String name2 = TestUt.call(new Person(), "getName", "님"); // "폴님" 리턴 Person me = TestUt.call(new Person(), "getMe"); // person 객체가 리턴 ``` 위와 같이 작동하도록 TestUt 클래스를 다시 만들어줄래? ```` ## ChatGPT 질문 2 응답 ```java import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; public class TestUt { public static Object call(Object obj, String methodName, Object... args) { try { Class[] argTypes = new Class[args.length]; for (int i = 0; i < args.length; i++) { argTypes[i] = args[i].getClass(); } Method method = obj.getClass().getDeclaredMethod(methodName, argTypes); method.setAccessible(true); return method.invoke(obj, args); } catch (NoSuchMethodException | IllegalAccessException | InvocationTargetException e) { e.printStackTrace(); } return null; } public static void main(String[] args) { Person person = new Person(); int age1 = (int) TestUt.call(person, "getAge"); int age2 = (int) TestUt.call(person, "getAge", 10); int age3 = (int) TestUt.call(person, "getAge", 10, 20); int age4 = (int) TestUt.call(person, "getAge", "100"); String name1 = (String) TestUt.call(person, "getName"); String name2 = (String) TestUt.call(person, "getName", "님"); Person me = (Person) TestUt.call(person, "getMe"); System.out.println("Age1: " + age1); // 10 출력 System.out.println("Age2: " + age2); // 20 출력 System.out.println("Age3: " + age3); // 40 출력 System.out.println("Age4: " + age4); // 110 출력 System.out.println("Name1: " + name1); // 폴 출력 System.out.println("Name2: " + name2); // 폴님 출력 System.out.println("Me: " + me); // person 객체 정보 출력 } } ``` # 32강 - [23 04 18, ken 12268, 32강, TestUt 테스트, getAge](https://youtu.be/6SU-OQQ5umU) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/d8c6493) # 33강 - [23 04 18, ken 12268, 33강, ChatGPT 가 만든 TestUt 적용, 테스트케이스 추가](https://youtu.be/6fBiQnIIxcI) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/b7aaea1) # 34강 - [23 04 18, ken 12268, 34강, 스트림 적용, 리턴타입에 제너릭처리 하여 이 함수의 리턴값 받을 때 자동형변환이 되도록 처리](https://youtu.be/S3Fc7t5K7ks) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/a4642ae) ## TestUt ```java import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; import java.util.Arrays; public class TestUt { public static T call(Object obj, String methodName, Object... args) { try { Class[] argTypes = Arrays.stream(args) .map(Object::getClass) .toArray(Class[]::new); Method method = obj.getClass().getDeclaredMethod(methodName, argTypes); method.setAccessible(true); return (T) method.invoke(obj, args); } catch (InvocationTargetException e) { throw new RuntimeException(e); } catch (NoSuchMethodException e) { throw new RuntimeException(e); } catch (IllegalAccessException e) { throw new RuntimeException(e); } } } ``` # 35강 - [23 04 18, ken 12268, 35강, intersection 메서드를 private 로 설정, 테스트 할 때 TestUt 사용](https://youtu.be/zXrgxA7__Bw) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/d5bc6f0) # 36강 - [23 04 18, ken 12268, 36강, getMinPoint 외 3개 메서드를 private 로 설정, 테스트 할 때 TestUt 사용](https://youtu.be/90TtfEr-IIo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/c50c14e) ## TestUt 최종 ```java import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; import java.util.Arrays; public class TestUt { public static T call(Object obj, String methodName, Object... args) { try { Class[] argTypes = Arrays.stream(args) .map(Object::getClass) .toArray(Class[]::new); Method method = obj.getClass().getDeclaredMethod(methodName, argTypes); method.setAccessible(true); return (T) method.invoke(obj, args); } catch (InvocationTargetException e) { throw new RuntimeException(e); } catch (NoSuchMethodException e) { throw new RuntimeException(e); } catch (IllegalAccessException e) { throw new RuntimeException(e); } } // 함수 호출 시 인자의 개수가 정확히 3개이고, 마지막 인자가 배열인 경우에는 call 이 아니라, callArr 을 호출해주세요. public static T callArr(Object obj, String methodName, Object... args) { return call(obj, methodName, new Object[]{args}); } } ``` ## 작업 메서드 - getMinPoint - getMaxPoint - positivePoints - emptyMatrix ## 미 작업 메서드 - intersections - drawOnCoordinate ## 미 작업 사유 - 위 2개의 메서드는 아직 지금 버전의 TestUt.call 함수로 호출할 수 없습니다. - 호출을 하려면 call 메서드를 조금 더 보강해야 합니다. # 37강 - [23 04 18, ken 12268, 37강, intersections, drawOnCoordinate 메서드를 private 로 설정, 테스트 할 때 TestUt 사용](https://youtu.be/90TtfEr-IIo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/da0d1f1) # 38강 - [23 04 19, ken 12268, 38강, TDD 방식으로 하노이의 탑, 시작, 설명](https://youtu.be/hFvNNRwUeBU) - [문제 - 하노이의 탑](https://school.programmers.co.kr/learn/courses/30/lessons/12946?language=java) # 39강 - [23 04 19, ken 12268, 39강, 재귀를 이용하면 복잡해보이지만 그것이 단순한 문제들의 조합으로 이루어진 문제를 쉽게 풀 수 있다, 문제에 적용](https://youtu.be/mS6czVuWXJ0) ## 반복문, 혹은 재귀로 풀수 있는 문제의 특징 - 비슷한 로직이 반복적으로 연산되어야 한다. - 복잡해 보이지만, 작게 보면 로직이 단순하다.(경우의 수가 적다) - 분할정복이 가능하다. ## 재귀함수의 3요소 - 상태 - 종료 조건 - 점화식 ## 재귀함수 형태 ```java void 재귀함수명(상태) { if ( 종료조건 ) 마무리; 점화식(상태 + a); 점화식(상태 + a); 점화식(상태 + a); } ``` ## 하노이의 탑 문제 이해하기 ### 규칙 - 기둥이 3개 있다. - 기둥위에 원판이 쌓여져 있다. - 원판은 한번에 하나만 옮기는게 가능 - 원판이 쌓여있다면, 가장 위에 있는 원판만 옮기는게 가능하다. - 원판위에 오직 그것보다 작은 원판만 둘 수 있다. ### 용어 - (1) : 1번기둥 - (2) : 2번기둥 - (3) : 3번기둥 - from : 어디에서 - to : 어디로 - n : 몇개를 이동시킬 것인지(원판의 개수) - empty : (1), (2), (3) 중에서 from 도 아니고, to 도 아닌 기둥 ### 옮길 원판의 개수가 1개 이고, from이 (1) 이고, to가 (3) 인 경우 - 이 경우 비어있는 경유지(empty)는 (2) 이다. - (1) => (3), 1개 이동 ### 옮길 원판의 개수가 1개 이고, from이 (3) 이고, to가 (2) 인 경우 - 이 경우 비어있는 경유지(empty)는 (1) 이다. - (3) => (2), 1개 이동 ### 옮길 원판의 개수가 2개 이고, from이 (1) 이고, to가 (3) 인 경우 - 이 경우 비어있는 경유지(empty)는 (2) 이다. - (1) => (2), 1개 이동 - (1) => (3), 1개 이동 - (2) => (3), 1개 이동 ### 옮길 원판의 개수가 2개 이고, from이 (1) 이고, to가 (2) 인 경우 - 이 경우 비어있는 경유지(empty)는 (3) 이다. - (1) => (3), 1개 이동 - (1) => (2), 1개 이동 - (3) => (2), 1개 이동 ### 옮길 원판의 개수가 3개 이고, from이 (1) 이고, to가 (3) 인 경우 - 이 경우 비어있는 경유지(empty)는 (2) 이다. - (1) => (2), 2개 이동 - (1) => (3), 1개 이동 - (2) => (3), 2개 이동 ### 원판의 개수가 3개 이고, from이 (1) 이고, to가 (2) 인 경우 - 이 경우 비어있는 경유지(empty)는 (3) 이다. - (1) => (3), 2개 이동 - (1) => (2), 1개 이동 - (3) => (2), 2개 이동 ### 옮길 원판의 개수가 n개 이고, from이 (1) 이고, to가 (3) 인 경우 - 이 경우 비어있는 경유지(empty)는 (2) 이다. - (1) => (2), n-1개 이동 - (1) => (3), 1개 이동 - (2) => (3), n-1개 이동 ### 옮길 원판의 개수가 n개 이고, from이 (3) 이고, to가 (1) 인 경우 - 이 경우 비어있는 경유지(empty)는 (2) 이다. - (3) => (2), n-1개 이동 - (3) => (1), 1개 이동 - (2) => (1), n-1개 이동 ### 옮길 원판의 개수가 n개 이고, 일반식으로 표현한 경우 - 이 경우 비어있는 경유지는 empty로 표기한다. - from => empty, n-1개 이동 - from => to, 1개 이동 - empty => to, n-1개 이동 # 40강 - [23 04 19, ken 12268, 40강, 테스트케이스 추가](https://youtu.be/AiY-r_xnNeg) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/636d0e8) # 41강 - [23 04 19, ken 12268, 41강, Hanoi 클래스 도입, N=2 인 경우의 테스트케이스 추가](https://youtu.be/DUOwhQ1rtvA) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/3201981) # 42강 - [23 04 19, ken 12268, 42강, calculate 메서드로 계산, addPath 메서드로 경로 추가 하도록 리팩토링](https://youtu.be/XYCIV3aGn3A) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/379dd1f) # 43강 - [23 04 19, ken 12268, 43강, FROM, TO, N 없애고, calculate 를 재귀호출 구조로 바꿔서 구현, 정답](https://youtu.be/mH_heNN1roo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/e772729) ## 재귀함수 형태 ```java // 재귀함수의 상태 : int from, int to, int n // 재귀함수의 상태는 곧 매개변수의 구성이다. private void calculate(int from, int to, int n) { if (n == 1) { // 재귀함수의 종료 조건, 종료조건은 보통 점화식 앞에 온다. addPath(from, to); // 기록 return; // 함수 종료, 이게 실행되면 연쇄적으로 함수가 종료된다. } int empty = 6 - from - to; // 점화식 시작 calculate(from, empty, n - 1); // n-1개를 일단 치워 놓고 calculate(from, to, 1); // 밑장을 to 로 옮긴다. calculate(empty, to, n - 1); // 치워놨던 n-1개를 to 로 옮긴다. // 점화식 끝 } ``` # 44강 - [23 04 19, ken 12268, 44강, calculate 함수 호출구조를 디버깅](https://youtu.be/FAUGx18Z9TY) # 45강 - [23 04 19, ken 12268, 45강, depth 변수를 통해서 재귀호출 구조를 보여주는 디버깅 기능 구현](https://youtu.be/wAuIvc-eS8U) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/642caa7) # 46강 - [23 04 19, ken 12268, 46강, formatted 를 String.format 으로 변경, 디버깅 기능 강화](https://youtu.be/b0eTeUa1wsM) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/0f30560) # 47강 - [23 04 21, ken 12268, 47강, 탐욕법은 현재 상황에서 가장 좋은 것을 고르는 알고리즘이다.](https://youtu.be/TtDTnUMbLcQ) # 48강 - [23 04 21, ken 12268, 48강, TDD 방식으로 조이스틱, 시작, 설명](https://youtu.be/c7RIglAONRw) - [문제 - 조이스틱](https://school.programmers.co.kr/learn/courses/30/lessons/42860?language=java) # 49강 - [23 04 21, ken 12268, 49강, BAA → 1](https://youtu.be/TYcBaM-Rejg) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/d8a796f) # 50강 - [23 04 21, ken 12268, 50강, CAA → 2](https://youtu.be/jHbSER2Ov-A) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/5dd649c) # 51강 - [23 04 21, ken 12268, 51강, BBA → 3, 꼼수](https://youtu.be/r7IEomMc9VI) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/1c10d7f) # 52강 - [23 04 21, ken 12268, 52강, BBA → 3](https://youtu.be/xf0fMynOXe4) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/a76d449) # 53강 - [23 04 24, ken 12268, 53강, nameCost와 moveCost로 알고리즘 분리, 가독성도 좋아지고, 난이도도 쉬워짐](https://youtu.be/jn2l1aYXTCg) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/13383ad) # 54강 - [23 04 24, ken 12268, 54강, ZBA → 3, 실패](https://youtu.be/x70VN6Ixn1U) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/3c9bae4) # 55강 - [23 04 24, ken 12268, 55강, ZBA → 3, 성공, 이제 좌우이동만 신경쓰면 됩니다.](https://youtu.be/Kd76aDZzW8c) ## nameCost ```java private int nameCost(String name) { int nameCost = 0; for (int i = 0; i < name.length(); i++) { char c = name.charAt(i); int diff = Math.min(c - 'A', 'Z' - c + 1); nameCost += diff; } return nameCost; } ``` ## nameCost 목표 | 목표 | 이동거리 | | -- | -- | | A | 0 | | B | 1 | | C | 2 | | D | 3 | | Z | 1 | | Y | 2 | | X | 3 | ## nameCost 알고리즘 별 이동거리 | 목표 | 정방향 이동거리 | 역방향 이동거리 | | -- | -- | -- | | A | 0 | 26 | | B | 1 | 25 | | C | 2 | 24 | | D | 3 | 23 | | E | 4 | 22 | | F | 5 | 21 | | G | 6 | 20 | | H | 7 | 19 | | I | 8 | 18 | | J | 9 | 17 | | K | 10 | 16 | | L | 11 | 15 | | M | 12 | 14 | | N | 13 | 13 | | O | 14 | 12 | | P | 15 | 11 | | Q | 16 | 10 | | R | 17 | 9 | | S | 18 | 8 | | T | 19 | 7 | | U | 20 | 6 | | V | 21 | 5 | | W | 22 | 4 | | X | 23 | 3 | | Y | 24 | 2 | | Z | 25 | 1 | # 56강 - [23 04 24, ken 12268, 56강, KAABCAAA, moveCostBy1 → 4](https://youtu.be/URQiJVbemPk) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/31992bd) # 57강 - [23 04 24, ken 12268, 57강, KAABC, moveCostBy2 → 2](https://youtu.be/E0bXce5-cs8) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/dea0394) # 58강 - [23 04 24, ken 12268, 58강, 사막의 위치와 길이를 구하는 함수를 구현](https://youtu.be/krHejP1Uk-0) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/a722dc0) ## ChatGPT 질문 1 ```` 자바 17 기준 입력된 문자열에서 특정 문자가 연속해서 나온다면 그 연속체의 시작점과 길이를 리턴해주는 함수를 구현해줘 만약에 특정 문자의 연속체가 2개 이상이라면 이왕이면 길이가 길고 이왕이면 앞에 위치하는 것 하나만 골라서 리턴해줘 존재하지 않는다면 리턴 객체에 length 에는 0, index 에는 -1 을 넣어줘 이왕이면 정규식으로 구현해줘 완성된 코드는 아래와 같이 작동해야 돼 ```java LongestCharContinuumIndexAndLength rs = Ut.getLongestCharContinuumIndexAndLength("KBAAAATK", 'A'); rs.length == 4; rs.index == 2; ``` ```` ## ChatGPT 질문 1 응답 ```java class Ut { public static class LongestCharContinuumIndexAndLength { public int index; public int length; public LongestCharContinuumIndexAndLength(int index, int length) { this.index = index; this.length = length; } } public static LongestCharContinuumIndexAndLength getLongestCharContinuumIndexAndLength(String str, char c) { String regex = c + "+"; Pattern pattern = Pattern.compile(regex); Matcher matcher = pattern.matcher(str); int maxLength = 0; int maxIndex = -1; while (matcher.find()) { int startIndex = matcher.start(); int length = matcher.end() - startIndex; if (length > maxLength) { maxLength = length; maxIndex = startIndex; } } return new LongestCharContinuumIndexAndLength(maxIndex, maxLength); } } ``` # 59강 - [23 04 24, ken 12268, 59강, ADAAAABCDKK, moveCostBy3 → 11](https://youtu.be/qBltYtoujWU) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/8f2b3d6) # 60강 - [23 04 24, ken 12268, 60강, ADAAAABCDKK, moveCostBy4 → 7](https://youtu.be/gxda9sdKTIY) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/bbab62b) # 61강 - [23 04 24, ken 12268, 61강, 완성 및 제출, 1부 작업](https://youtu.be/i7FAbSh5S4k) - [23 04 24, ken 12268, 61강, 완성 및 제출, 2부 예외처리](https://youtu.be/yWy1cNmyeio) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/6ea2043) # 62강 - [23 04 24, ken 12268, 62강, 정답코드가 긴건 문제가 안됩니다. 중요한 것은 가독성입니다.](https://youtu.be/fyoSCBeaHts) # 63강 - [23 04 25, ken 12268, 63강, TDD 방식으로 체육복, 시작, 설명](https://youtu.be/qa6EMKTP33M) - [문제 - 체육복](https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=java) # 64강 - [23 04 25, ken 12268, 64강, n=5, lost=[2, 4], reserve=[1, 3, 5] → 5, 1부, 작업](https://youtu.be/TyjjQIGiYUQ) - [23 04 25, ken 12268, 64강, n=5, lost=[2, 4], reserve=[1, 3, 5] → 5, 2부, 오류수정](https://youtu.be/FCNtIbU-v8A) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/95728ce) # 65강 - [23 04 25, ken 12268, 65강, borrowSelf 작업을 통한 전처리](https://youtu.be/vz9e690nyQg) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/1a7a522) # 66강 - [23 04 26, ken 12268, 66강, 모의고사, 시작, 설명](https://youtu.be/UrkzEz2a9Gw) - [문제 - 모의고사](https://school.programmers.co.kr/learn/courses/30/lessons/42840?language=java) # 67강 - [23 04 26, ken 12268, 67강, 점수 구하는 함수 레이아웃](https://youtu.be/qMCPdsYI1F8) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/2d7981d) # 68강 - [23 04 26, ken 12268, 68강, 각 수포자가 몇점을 받았는지 검사하는 함수](https://youtu.be/3CuqMeTFNdA) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/482e7e9) # 69강 - [23 04 26, ken 12268, 69강, 함수의 중복제거](https://youtu.be/3fPxk22AIRE) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/1f48d51) # 70강 - [23 04 26, ken 12268, 70강, 수포자들이 받은 점수 중 최고점수 구하기](https://youtu.be/iqNWfWmU81E) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/0e468c4) # 71강 - [23 04 26, ken 12268, 71강, 수포자들이 받은 점수가 최고점수와 돌일한 수포자들의 번호만 추려서 배열에 담기](https://youtu.be/oHTjtse2vaA) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/f515e32) # 72강 - [23 04 26, ken 12268, 72강, 수포자의 점수를 계산하는 함수에 캐시기능 장착, 이 캐시 스킬은 알고리즘에 풀이에 필수](https://youtu.be/vL9rD7VmsP4) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/fbaaf9b) # 73강 - [23 04 26, ken 12268, 73강, 스트림을 이용해서 푸는 방법, flatMap, groupBy 스킬을 사용](https://youtu.be/V7ytnST5fEo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/6d8e6be) ## Solution2 ```java class Solution2 { public int[] solution(int[] answers) { Map rightAnswerCountsByStyleNo = IntStream.range(0, answers.length) .mapToObj(i -> { List l = new ArrayList<>(); if (answers[i] == answerOfSt1(i)) l.add(1); if (answers[i] == answerOfSt2(i)) l.add(2); if (answers[i] == answerOfSt3(i)) l.add(3); return l; }) .flatMap(List::stream) .collect(Collectors.groupingBy(Function.identity(), Collectors.counting())); long max = rightAnswerCountsByStyleNo .values() .stream() .max(Long::compareTo) .get(); return rightAnswerCountsByStyleNo .entrySet() .stream() .filter(e -> e.getValue() == max) .mapToInt(Map.Entry::getKey) .sorted() .toArray(); } int answerOfSt1(int i) { int[] answers = new int[]{1, 2, 3, 4, 5}; return answers[i % answers.length]; } int answerOfSt2(int i) { int[] answers = new int[]{2, 1, 2, 3, 2, 4, 2, 5}; return answers[i % answers.length]; } int answerOfSt3(int i) { int[] answers = new int[]{3, 3, 1, 1, 2, 2, 4, 4, 5, 5}; return answers[i % answers.length]; } } ``` # 74강 - [23 04 27, ken 12268, 74강, 기능개발, 시작, 설명](https://youtu.be/Xj3S249S3Ns) - [문제 - 기능개발](https://school.programmers.co.kr/learn/courses/30/lessons/42586?language=java) # 75강 - [23 04 27, ken 12268, 75강, Queue를 이용하여 해결, 1부](https://youtu.be/-C5qpv_LSKk) - [23 04 27, ken 12268, 76강, Queue를 이용하여 해결, 2부](https://youtu.be/DuJpUCsvAXc) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/ec878c9) ```java import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.stream.Collectors; import java.util.stream.IntStream; class Solution { public int[] solution(int[] progresses, int[] speeds) { Queue queue = IntStream .range(0, progresses.length) .mapToObj(i -> (int) Math.ceil((100.0 - progresses[i]) / speeds[i])) .collect(Collectors.toCollection(LinkedList::new)); List result = new ArrayList<>(); while (!queue.isEmpty()) { int remains = queue.poll(); // 큐의 가장 끝에 있는 엘리먼트 하나의 값을 리턴 후 그 엘리먼트를 큐에서 제거 int count = 1; // 일단 배포할 기능의 개수로 1개를 설정 // queue.peek() // 큐의 가장 끝에 있는 엘리먼트 하나의 값을 리턴 // 이번 기능과 같이 배포해도 되는 기능들의 개수를 카운팅 - 시작 while (!queue.isEmpty() && remains >= queue.peek()) { queue.poll(); count++; // 이번 기능이 같이 배포되는 기능이니 카운팅 증가 } // 이번 기능과 같이 배포해도 되는 기능들의 개수를 카운팅 - 끝 result.add(count); } return result.stream().mapToInt(Integer::intValue).toArray(); } } ``` # 76강 - [23 04 27, ken 12268, 76강, 배열과 Stream을 이용하여 해결](https://youtu.be/tl8Xz6kdH84) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/31fd0ab) ```java import java.util.*; import java.util.stream.Collectors; import java.util.stream.IntStream; class Solution2 { public int[] solution(int[] progresses, int[] speeds) { IntStream.range(0, progresses.length) .forEach(i -> { int day = (int) Math.ceil((100.0 - progresses[i]) / speeds[i]); progresses[i] = day; if (i > 0) progresses[i] = Math.max(progresses[i - 1], progresses[i]); }); return Arrays .stream(progresses) .boxed() .collect(Collectors.groupingBy(e -> e, LinkedHashMap::new, Collectors.counting())) .values() .stream() .mapToInt(Long::intValue) .toArray(); } } ``` # 77강 - [23 05 02, ken 12268, 77강, 피보나치 수열, 시작, 설명](https://youtu.be/ieDZ0TIhEl0) - [문제 - 기능개발](https://school.programmers.co.kr/learn/courses/30/lessons/12945?language=java) ## 자바 소스코드 ```java public class Main { public static void main(String[] args) { System.out.printf("fibonacci Of 5 : %d\n", new Fibonacci().calc(5)); // 5 출력 System.out.printf("fibonacci Of 10 : %d\n", new Fibonacci().calc(10)); // 55 출력 } } class Fibonacci { int calc(int n) { if ( n <= 1 ) return n; return calc(n - 2) + calc(n - 1); } } ``` # 78강 - [23 05 02, ken 12268, 78강, 지금의 구조는 너무나 느리고 비효율적이다. DP를 왜 적용해야하는지 파악](https://youtu.be/u1n_gSBTfWQ) ## 자바 소스코드 ```java public class Main { public static void main(String[] args) { System.out.printf("fibonacci Of 4 : %d\n", new Fibonacci().calc(4, 1)); // 3 출력 } } class Fibonacci { int calcCallCount; int calc(int n, int depth) { calcCallCount++; printDebug(n, depth); if (n <= 1) { return n; } return calc(n - 2, depth + 1) + calc(n - 1, depth + 1); } void printDebug(int n, int depth) { System.out.print(" ".repeat(depth - 1)); System.out.printf("calcCallCount(%d), depth(%d), calc(%d)\n", calcCallCount, depth, n); } } ``` # 79강 - [23 05 02, ken 12268, 79강, DP적용하여 비효율적인 재연산을 제거](https://youtu.be/5E3H3zSDtaM) ## 자바 소스코드 ```java import java.util.Map; import java.util.HashMap; public class Main { public static void main(String[] args) { System.out.printf("fibonacci Of 10 : %d\n", new Fibonacci().calc(10, 1)); // 55 출력 } } class Fibonacci { int calcCallCount; Map cache = new HashMap<>(); int calc(int n, int depth) { if ( cache.containsKey(n) ) return cache.get(n); calcCallCount++; printDebug(n, depth); int rs; if (n <= 1) { rs = n; } else { rs = calc(n - 2, depth + 1) + calc(n - 1, depth + 1); } cache.put(n, rs); return rs; } void printDebug(int n, int depth) { System.out.print(" ".repeat(depth - 1)); System.out.printf("calcCallCount(%d), depth(%d), calc(%d)\n", calcCallCount, depth, n); } } ``` # 80강 - [23 05 02, ken 12268, 80강, int 로는 안될것 같아서 long 으로 변경, 하지만 아직 부족하다.](https://youtu.be/-VoqRh_TwLk) ## 자바 소스코드 ```java import java.util.Map; import java.util.HashMap; public class Main { public static void main(String[] args) { System.out.printf("fibonacci Of 10 : %d\n", new Fibonacci().calc(1000)); // 55 출력 } } class Fibonacci { Map cache = new HashMap<>(); long calc(int n) { if ( cache.containsKey(n) ) return cache.get(n); long rs; if (n <= 1) { rs = n; } else { rs = calc(n - 2) + calc(n - 1); } cache.put(n, rs); return rs; } } ``` # 81강 - [23 05 02, ken 12268, 81강, long 으로는 안될것 같아서 BigInteger 로 변경](https://youtu.be/1dRdmfsvcQg) ## ChatGPT 질문 1 ```` 자바 17 기준으로 ```java import java.util.Map; import java.util.HashMap; public class Main { public static void main(String[] args) { System.out.printf("fibonacci Of 10 : %d\n", new Fibonacci().calc(1000)); // 55 출력 } } class Fibonacci { Map cache = new HashMap<>(); long calc(int n) { if ( cache.containsKey(n) ) return cache.get(n); long rs; if (n <= 1) { rs = n; } else { rs = calc(n - 2) + calc(n - 1); } cache.put(n, rs); return rs; } } ``` 위 자바 소스코드에서 calc 함수가 BigInteger 를 리턴하도록 고쳐줘 ```` ```java import java.util.Map; import java.util.HashMap; import java.math.BigInteger; public class Main { public static void main(String[] args) { System.out.printf("fibonacci Of 1000 : %d\n", new Fibonacci().calc(1000).longValue()); // 817770325994397771 출력 } } class Fibonacci { Map cache = new HashMap<>(); BigInteger calc(int n) { if ( cache.containsKey(n) ) return cache.get(n); BigInteger rs; if (n <= 1) { rs = BigInteger.valueOf(n); } else { BigInteger calcOfNMinus2 = calc(n - 2); BigInteger calcOfNMinus1 = calc(n - 1); rs = calcOfNMinus2.add(calcOfNMinus1); } cache.put(n, rs); return rs; } } ``` # 82강 - [23 05 02, ken 12268, 82강, 정답제출](https://youtu.be/LG7QOi9jr4M) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/f35b80a) # 83강 - [23 05 02, ken 12268, 83강, calc 메서드에서 리턴하기 전에 mod 연산을 하여, BigInteger 를 필요가 없도록](https://youtu.be/FFjwmDq9seo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/ac47f51) - 82강 방법으로 푸는게 정상적입니다. - 83강의 내용은 수학을 이용한 꼼수입니다. # 84강 - [23 05 10, ken 12268, 84강, TDD 방식으로 순위 검색, 시작, 설명](https://youtu.be/V-8vhTOgd3k) - [문제 - 순위 검색](https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=java) # 85강 - [23 05 10, ken 12268, 85강, python frontend senior chicken → 150, 210, 시작](https://youtu.be/VE-jZnIqST0) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/27c75ff) # 86강 - [23 05 10, ken 12268, 86강, python frontend senior chicken → 150, 210, 와 비슷한 테스트케이스 추가](https://youtu.be/xA6dTQWNYGM) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/b64a65b) # 87강 - [23 05 10, ken 12268, 87강. buildScoresMap 완성](https://youtu.be/_8uQo3Tjcek) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/182ff15) # 88강 - [23 05 10, ken 12268, 88강, 무식한 탐색](https://youtu.be/18opo3g5ojI) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/d94f39d) # 89강 - [23 05 10, ken 12268, 89강, 무식한 탐색을 기반으로 solution 함수 구현](https://youtu.be/fGGa3m6TeKQ) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/3cbdad3) # 90강 - [23 05 10, ken 12268, 90강, 이진탐색적용](https://youtu.be/Ir2dzN9vbQ0) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/fbdfb66) # 91강 - [23 05 10, ken 12268, 91강, ChatGPT를 활용해서 이진탐색을 공부하는 방법](https://youtu.be/ZO8m-bYYcVQ) ## ChatGPT 질문 1 ```` 내가 이진탐색을 공부하고 싶어. 자바 코드 기준으로 설명좀 해줘. 아주 쉽게 그리고 직관적으로 이해하는데 도움이 되는 유튜브 영상도 추천해줘 ```` ## ChatGPT 응답 1 이진 탐색(binary search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 검색 알고리즘입니다. 이진 탐색은 배열을 반으로 나누어 가며 원하는 값을 찾기 때문에, 시간복잡도가 O(log n)으로 매우 빠릅니다. 자바 코드로 아주 간단하게 이진 탐색을 구현해볼게요: ```java public int binarySearch(int[] arr, int target) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; } ``` 이진 탐색 알고리즘은 다음과 같이 동작합니다: 1. 배열의 중간 인덱스를 찾습니다. 1. 찾고자 하는 값과 중간 인덱스의 값을 비교합니다. 1. 값이 같다면, 찾은 인덱스를 반환합니다. 1. 찾고자 하는 값이 중간 인덱스의 값보다 크다면, 왼쪽 범위를 중간 인덱스+1로 변경합니다. 1. 찾고자 하는 값이 중간 인덱스의 값보다 작다면, 오른쪽 범위를 중간 인덱스-1로 변경합니다. 1. 왼쪽 범위가 오른쪽 범위보다 작거나 같을 때까지 1~5 단계를 반복합니다. 1. 찾고자 하는 값이 배열에 없다면 -1을 반환합니다. 직관적인 이해를 돕기 위한 유튜브 영상 추천은 다음과 같습니다: - 데이브 라프캠프(Dave Raffcamp)의 "이진 탐색(Binary Search) 알고리즘 설명" 영상 - [링크: https://www.youtube.com/watch?v=P3YID7liBug](https://www.youtube.com/watch?v=P3YID7liBug) - 프로그래머스(Programmers)의 "이진 탐색 알고리즘과 자바로 구현하기" 영상 - [링크: https://www.youtube.com/watch?v=94RC-DsGMLo](https://www.youtube.com/watch?v=94RC-DsGMLo) 영상을 통해 이진 탐색에 대한 더 깊은 이해를 얻으시길 바랍니다! # 92강 - [23 05 11, ken 12268, 92강, TDD 방식으로 타겟 넘버, 시작, 설명](https://youtu.be/Zq-SfTQ039s) - [문제 - 타겟 넘버](https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java) # 93강 - [23 05 11, ken 12268, 93강, {1, 1, 1, 1, 1}, 3 → 5, 시작](https://youtu.be/WM56zPKwAv4) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/002a733) # 94강 - [23 05 11, ken 12268, 94강, {1, 1, 1, 1, 1}, 3 → 5, 해결](https://youtu.be/mZ5LQISyJLM) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/6de4bba) # 95강 - [23 05 11, ken 12268, 95강, {1, 1, 1, 1, 1}, 3 → 5, 디버깅용 history 만들기](https://youtu.be/TVQ2gQB_7p0) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/f222f4c) # 96강 - [23 05 11, ken 12268, 96강, ChatGPT 이용해서 해당 소스코드를 다른형식으로 변경해보기](https://youtu.be/AbLhax0ZOeM) ## 프롬프트 생성 로봇 선입력 - ChatGPT에 뭔가를 물어보기 전에 아래 명령을 우선적으로 선입력 해주세요. 답변의 퀄리티가 높아집니다. ``` 당신은 프롬프트 생성 로봇입니다. 당신은 사용자의 목표, 목적, 원하는 결과의 예제, 맥락에 맞는 기타 정보들을 수집해야 합니다. 프롬프트에는 당신이 제공받은 모든 정보가 모두 포함되어야 합니다. 당신은 완벽한 프롬프트를 생성할 수 있다는 확신이 들 때까지 사용자에게 질문을 해야 합니다. 당신의 답변은 명확한 형식을 갖추고 ChatGPT 상호작용에 최적화되어야 합니다. 당신의 답변은 사용자에게 목표, 원하는 출력 형식, 필요한 추가 정보를 묻는 것으로 시작합니다. ``` ## ChatGPT 질문 1(이미 프롬프트 생성 로봇 선입력이 된 상태) ```` 자바 17 소스코드 ```java class NumberOfCases { private final int[] numbers; private final int target; public NumberOfCases(int[] numbers, int target) { this.numbers = numbers; this.target = target; } int calc() { return calc(0, 0, "0"); } private int calc(int depth, int sum, String history) { // 내가 끝방에 있을 때 if (depth == numbers.length) { System.out.println("history : " + history + " = " + sum); return sum == target ? 1 : 0; } // 그렇지 않을 때는 탐색을 이어 간다. // 각 방마다 통로가 위쪽(+), 아래쪽(-)이 있다. return calc(depth + 1, sum + numbers[depth], history + " + " + numbers[depth]) + calc(depth + 1, sum - numbers[depth], history + " - " + numbers[depth]); } } ``` 위 코드를 재귀가 아닌 반복문과 Stack 자료구조를 사용하는 방식으로 고쳐줘 ```` ## ChatGPT 응답 1 재귀에서 반복문과 스택을 사용하는 방식으로 변경하려면, 스택을 이용하여 탐색을 구현하면 됩니다. 스택에는 계산 과정을 저장할 Pair 클래스를 사용합니다. 계산 과정을 저장할 문자열, 현재 깊이, 현재까지의 합을 저장합니다. 탐색은 다음과 같이 구현할 수 있습니다. 1. 스택에 시작 노드를 추가한다. 1. 스택이 빌 때까지 반복한다. 1. 스택에서 노드를 꺼낸다. 1. 노드의 깊이가 배열의 길이와 같으면, 계산 과정을 출력하고 타겟 값과 일치하는지 확인한다. 일치하면 결과 값을 증가시킨다. 1. 노드의 깊이가 배열의 길이와 같지 않으면, 노드의 자식 노드를 생성하고 스택에 추가한다. 다음은 반복문과 스택을 사용한 코드입니다. ```java import java.util.Stack; class NumberOfCases { private final int[] numbers; private final int target; public NumberOfCases(int[] numbers, int target) { this.numbers = numbers; this.target = target; } int calc() { int count = 0; // 결과 값(타겟 값을 만들 수 있는 경우의 수) Stack stack = new Stack<>(); // 스택 생성 stack.push(new Pair(0, 0, "")); // 스택에 시작 노드 추가 while (!stack.isEmpty()) { // 스택이 비어있지 않은 동안 반복 Pair pair = stack.pop(); // 스택에서 노드 꺼내기 int depth = pair.depth; // 현재 탐색 깊이 int sum = pair.sum; // 현재까지 계산된 합 String history = pair.history; // 계산 과정을 기록한 문자열 if (depth == numbers.length) { // 깊이가 숫자 배열의 길이와 같으면 System.out.println("history : " + history + " = " + sum); // 계산 과정 출력 if (sum == target) { // 합이 타겟 값과 같으면 count++; // 결과 값 증가 } } else { // 깊이가 숫자 배열의 길이와 같지 않으면 stack.push(new Pair(depth + 1, sum - numbers[depth], history + " - " + numbers[depth])); // 노드 추가(연산자 : -) stack.push(new Pair(depth + 1, sum + numbers[depth], history + " + " + numbers[depth])); // 노드 추가(연산자 : +) } } return count; // 결과 값 반환 } // 노드(숫자)를 표현하는 클래스 private static class Pair { final int depth; // 탐색 깊이(배열 인덱스) final int sum; // 현재까지의 합 final String history; // 계산 과정을 기록한 문자열 Pair(int depth, int sum, String history) { this.depth = depth; this.sum = sum; this.history = history; } } } ``` 기존의 재귀 방식에서는 함수를 호출하여 계산 과정을 구현했지만, 스택을 이용한 반복문 방식에서는 계산 과정을 `Pair` 클래스에 저장하고, 스택에 `Pair` 객체를 추가하여 탐색을 구현합니다. `Pair` 클래스는 현재까지의 합, 탐색 깊이, 계산 과정을 기록한 문자열을 필드로 가지며, 스택에 추가하여 탐색을 진행합니다. 탐색이 종료되면 결과 값(타겟 값을 만들 수 있는 경우의 수)을 반환합니다. # 97강 - [23 05 12, ken 12268, 97강, 튜플, 시작, 설명](https://youtu.be/bJfEurL01ng) - [문제 - 튜플](https://school.programmers.co.kr/learn/courses/30/lessons/64065?language=java) # 98강 - [23 05 12, ken 12268, 98강, 문장을 자르고 쪼개서 각 원소(배열)와 그것의 길이를 키로 하는 맵으로 변환](https://youtu.be/qZdjVTdeFgs) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/83ea796) # 99강 - [23 05 12, ken 12268, 99강, IntStream 을 통해서 맵의 원소에 순차적으로 접근하여, set 에 담는다.](https://youtu.be/AEPjn1g8eV0) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/3d4c908) # 100강 - [23 05 12, ken 12268, 100강, 단어 변환, 시작, 설명](https://youtu.be/8YdaRj2278M) - [문제 - 단어 변환](https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=java) # 101강 - [23 05 12, ken 12268, 101강, 테스트케이스 등록](https://youtu.be/VccbGeORPRE) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/5594775) # 102강 - [23 05 12, ken 12268, 102강, isConvertible](https://youtu.be/4Iqig5SQvYY) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/44d08e9) # 103강 - [23 05 12, ken 12268, 103강, 무식하고 엉성한 접근으로 시도, 실패](https://youtu.be/aVbpjlcFF1k) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/55c143e) # 104강 - [23 05 12, ken 12268, 104강, 끝까지 가보는 방식이 아닌, 찔끔찔금 움직이는 방식으로 해야겠구나, 큐를 사용해서 탐색할 곳의 우선순위 를 정함](https://youtu.be/PqUIVcELd8s) # 105강 - [23 05 12, ken 12268, 105강, 발견된 경로를 나중에 탐색할 곳으로 큐에 등록, 큐의 요소(탐색할 곳)가 남아있지 않거나, 오아시스를 찾을 때 까지 반복](https://youtu.be/0NV_xzXEXOo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/a7b01b6) # 106강 - [23 05 12, ken 12268, 106강, 이미 큐에 탐색할 곳으로 지정된 경로는 무시하기, 그래야 무한 루프에 빠지지 않을 수 있다.](https://youtu.be/o2cv-Q_Kp2E) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/b07f241) # 107강 - [23 05 15, ken 12268, 107강, TDD 방식으로 다리를 지나는 트럭, 시작, 설명](https://youtu.be/YZkDEOYyM48) - [문제 - 다리를 지나는 트럭](https://school.programmers.co.kr/learn/courses/30/lessons/42583?language=java) # 108강 - [23 05 15, ken 12268, 108강, 100, 100, {10} → 101](https://youtu.be/1llwu9qBAL4) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/5cba4ed) # 109강 - [23 05 15, ken 12268, 109강, 100, 100, {10, 10} → 102](https://youtu.be/QMZ9Ze2MGOo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/3d2f379) # 110강 - [23 05 15, ken 12268, 110강, 객체지향 설계](https://youtu.be/YBXzdZneNnc) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/f478019) # 111강 - [23 05 15, ken 12268, 111강, 버그수정](https://youtu.be/VG1D9GUXPBA) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/7507992) # 112강 - [23 05 15, ken 12268, 112강, 리팩토링](https://youtu.be/OVxxJj3Acyk) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/277702f) # 113강 - [23 05 16, ken 12268, 113강, 큐를 이용한 방식, 1단계, 다리의 상태를 큐로 구현](https://youtu.be/gUEzAdDgk1U) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/1c0ab94) # 114강 - [23 05 16, ken 12268, 114강, 큐를 이용한 방식, 2단계, 모든 트럭이 다리에 진입할 때까지 반복](https://youtu.be/zRzo8IA5Fto) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/5203359) # 115강 - [23 05 16, ken 12268, 115강, 큐를 이용한 방식, 3단계, 모든 다리위의 트럭이 빠져나갈 때까지 반복](https://youtu.be/WwldXBcY7pU) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/211a7b3) ## 큐를 이용한 정답 ```java import java.util.LinkedList; import java.util.Queue; import java.util.stream.IntStream; class Solution { public int solution(int bridge_length, int weight, int[] truck_weights) { // 다리를 만든다. Queue bridge = new LinkedList<>(); // 큐의 길이를 늘린다. // 엘리먼트 0은 해당칸이 비어있음을 의미 IntStream.range(0, bridge_length).forEach(i -> bridge.add(0)); int seconds = 0; // 다리에 올려져 있는 무게 int onBridgeWeight = 0; int truckIndex = 0; // 트럭이 모두 다 진입할 때 까지 반복 while (truckIndex < truck_weights.length) { onBridgeWeight -= bridge.poll(); // 다리 끝에 있는 녀석을 꺼낸다. // 이번에 진입시켜야 하는 트럭의 무게 int truckWeight = truck_weights[truckIndex]; // 진입시킬 수 있는지 확인 if (onBridgeWeight + truckWeight <= weight) { bridge.add(truckWeight); onBridgeWeight += truckWeight; truckIndex++; } else { bridge.add(0); } seconds++; } // 아직 다리위에 남아 있는 트럭이 있다면, 그것이 다리를 지날 때 까지 기다림 while (onBridgeWeight > 0) { seconds++; onBridgeWeight -= bridge.poll(); } return seconds; } } ``` # 116강 - [23 05 16, ken 12268, 116강, TDD 방식으로 양과 늑대, 시작, 설명](https://youtu.be/XYAGEQaHvHQ) - [문제 - 양과 늑대](https://school.programmers.co.kr/learn/courses/30/lessons/92343?language=java) # 117강 - [23 05 16, ken 12268, 117강, 특정 노드에서 이동 할 수 있는 노드들의 후보를 얻는것이 중요하다.](https://youtu.be/UJhs0ltPSpc) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/578170e) # 118강 - [23 05 16, ken 12268, 118강, 이미 방문한 곳은 지나쳐서 탐색한다.](https://youtu.be/k6hjt0pD9Qg) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/bf52d3f) # 119강 - [23 05 16, ken 12268, 119강, Path 라는 자료구조를 정의해서 전체경로를 저장](https://youtu.be/2PbtURp10iw) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/d97207e) ## Path 클래스 ```java class Path { private final int depth; private final int node; private final Path parentPath; private final List childPaths; Path(Path parentPath, int node) { this.parentPath = parentPath; this.depth = parentPath == null ? 0 : parentPath.depth + 1; this.node = node; this.childPaths = new ArrayList<>(); } public Path addChildPath(int nextNode) { Path path = new Path(this, nextNode); childPaths.add(path); return path; } public List history() { List history = new ArrayList<>(); Path path = this; while (path != null) { history.add(path.node); path = path.parentPath; } return history; } @Override public String toString() { return " ".repeat(depth) + node + "\n" + childPaths.stream().map(Path::toString).collect(Collectors.joining("\n")); } } ``` # 120강 - [23 05 17, ken 12268, 120강, 각 Path에 양의 수와 늑대의 수 표기, 그것을 기반으로 양이 가장 많은 Path를 찾음](https://youtu.be/x_4959aFuX8) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/72d2822) # 121강 - [23 05 17, ken 12268, 121강, Path를 기반으로 solution 구현](https://youtu.be/IkKS8iAqi6M) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/f0c469c) # 122강 - [23 05 17, ken 12268, 122강, 늑대가 양을 잡아먹는 Path가 발견되면, 그 이후 Path는 탐색하지 않도록 최적화](https://youtu.be/xvFMQNE8Ues) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/e3e43c5) # 123강 - [23 05 17, ken 12268, 123강, 리팩토링, history 최적화](https://youtu.be/IgWLa0AgxCo) - [GIT](https://github.com/jhs512/programmers_ct_23_04_17/commit/b4d9083) # 124강 - [23 05 17, ken 12268, 124강, TDD 방식으로 신입사원 교육, 시작, 설명]() - [문제 - 신입사원 교육](https://school.programmers.co.kr/learn/courses/15009/lessons/121688?language=java) # 125강 - [23 07 03, ken 12268, 125강, 외톨이 알파벳](https://youtu.be/N6enwxxnk18) - [문제 - [PCCP 모의고사 #1] 외톨이 알파벳](https://school.programmers.co.kr/learn/courses/15008/lessons/121683?language=java) ## 정답 ```java public class Main { public static void main(String[] args) { System.out.println(new Solution().solution("edeaaabbccd")); // 출력: de } } // 전략 // - 특정 문자가 외툴이 문자인지 아는 방법은 해당 문자를 기준으로 문잘을 split 했을 때 3 이상인지 확인하면 된다. class Solution { public String solution(String inputString) { // `ABA` 에서 A 는 외톨이 문자열이지만 가장 자리에 있어서 우리의 전략이 먹히지 않는다. // 그래서 이러한 케이스에 대비해 문자열 양옆에 `.`을 붙힌다. inputString = "." + inputString + "."; String rs = ""; // 디버그를 위해서 StringBuilder 대신 String 사용 for (char c = 'a'; c <= 'z'; c++) { if (inputString.split(c + "").length < 3) continue; rs += c; } if (rs.length() == 0) return "N"; return rs; } } ``` # 126강 - [23 07 04, ken 12268, 126강, 체육대회, 영상없음]() - [문제 - [PCCP 모의고사 #1] 체육대회](https://school.programmers.co.kr/learn/courses/15008/lessons/121684?language=java) ## 정답 ```java import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Main { public static void main(String[] args) { System.out.println(new Solution().solution(new int[][]{{20, 30}, {30, 20}, {10, 50}})); // 출력: 80 } } // 전략 // - 각 학생들을 순차적으로 방문한다. // - 방문한 학생은 항상 종목의 개수 + 1 의 선택권을 가진다. // - 여기서 1은 참여하지 않는 경우이다. // - 이런식으로 마지막 학생까지 방문한다. // - 계산할 때 이미 누군가가 선택한 종목은 경우의 수에서 제외 한다. class Solution { public int solution(int[][] ability) { return new MaxCalculator(ability).run(); } } class MaxCalculator { // max 함수의 계산결과 캐시 private final Map maxCache = new HashMap<>(); // 각 학생별 능력들 private final int[][] ability; // 특정 종목이 이미 선택되었는지 정보 private final boolean[] isChosen; public MaxCalculator(int[][] ability) { this.ability = ability; this.isChosen = new boolean[sportsSize()]; } // 학생수 int studentsSize() { return ability.length; } // 종목수 int sportsSize() { return ability[0].length; } public int run() { // 계산시작 // // 전략대로 가장 첫번째 학생(studentIndex = 0)의 선택할 수 있는 경우의 수를 모두 방문하기 시작한다. return max(0); } private String cacheKey(int student, boolean[] isChosen) { return student + Arrays.toString(isChosen); } private int max(int studentIndex) { // 만약에 studentIndex 가 범위를 벗어났다면 0 리턴 if (studentIndex >= studentsSize()) return 0; // 캐시 키 String cacheKey = cacheKey(studentIndex, isChosen); // 캐시 결과가 있다면 바로 리턴 if (maxCache.containsKey(cacheKey)) return maxCache.get(cacheKey); // 현재 학생이 아무런 종목도 선택하지 않았을 경우에 나올 수 있는 시나리오 중 최고점을 일단 구한다. int max = max(studentIndex + 1); for (int i = 0; i < sportsSize(); i++) { // 해당 종목을 이미 다른 누군가가 선점했다면 패스 if (isChosen[i]) continue; // 해당 종목이 선택되었다고 표시 isChosen[i] = true; // 기존 최고 점수와, 이번 학생(studentIndex)이 // 이번 종목을 수행한다고 가정 했을 때 // 나올 수 있는 시나리오의 최고점 중 더 큰 값 max = Math.max(max, ability[studentIndex][i] + max(studentIndex + 1)); // 해당 종목이 선택되었다고 표시, 취소 isChosen[i] = false; } maxCache.put(cacheKey, max); return max; } } ``` ```java // v2 import java.util.Arrays; import java.util.Map; import java.util.HashMap; class Solution { public int solution(int[][] ability) { return new MaxCalculator(ability).run(); } } class MaxCalculator { private final Map maxOfCache = new HashMap<>(); private final int[][] ability; private final boolean[] isChosen; private final int studentsSize; private final int sportsSize; public MaxCalculator(int[][] ability) { this.ability = ability; this.studentsSize = ability.length; this.sportsSize = ability[0].length; this.isChosen = new boolean[sportsSize]; } public int run() { return maxOf(0); } private boolean isStudentIndexOutOfBounds(int index) { return index >= studentsSize; } private String genCacheKey(int studentIndex, boolean[] isChosen) { return studentIndex + Arrays.toString(isChosen); } private int maxOf(int studentIndex) { String cacheKey = genCacheKey(studentIndex, isChosen); if ( !maxOfCache.containsKey(cacheKey) ) maxOfCache.put(cacheKey, _maxOf(studentIndex)); return maxOfCache.get(cacheKey); } private int _maxOf(int studentIndex) { if ( isStudentIndexOutOfBounds(studentIndex) ) return 0; int max = maxOf(studentIndex + 1); for ( int sportIndex = 0; sportIndex < sportsSize; sportIndex++ ) { if ( isChosen[sportIndex] ) continue; int abilityOfSport = ability[studentIndex][sportIndex]; isChosen[sportIndex] = true; max = Math.max(max, abilityOfSport + maxOf(studentIndex + 1)); isChosen[sportIndex] = false; } return max; } } ``` # 127강 - [23 07 06, ken 12268, 127강, 유전법칙, 영상없음]() - [문제 - [PCCP 모의고사 #1] 유전법칙](https://school.programmers.co.kr/learn/courses/15008/lessons/121685?language=java) ## 정답 ```java import java.util.Arrays; public class Main { public static void main(String[] args) { System.out.println(Arrays.toString(new Solution().solution(new int[][]{{3, 1}, {2, 3}, {3, 9}}))); // 출력: [RR, Rr, RR] } } // 전략 // - 어짜피 정답은 rr, RR, Rr 중 하나이다. // - rr, RR 이 아니면 Rr 이다. // - Rr 인지는 계산하기 어렵다. // - 반면에 rr, RR 인지는 계산하기 쉽다. // - rr 이나 RR 에 속하는지 계산해보고, 아니라면 Rr 이라고 가정하는 방식으로 접근한다. // - 각 세대가 펼쳐지는 방식에는 규칙성이 있는데 그 규칙성 부터 파악해야 문제를 풀 수 있다. class Solution { public String find(int n, int p) { // 1세대는 무조건 Pr 이다. // 여기까지 왔다는 뜻은 경우의 수가 Pr 밖에 없다는 뜻 if (n == 1) return "Rr"; // 이전 세대의 개체 수 int slice = (int) Math.pow(4, n - 2); // 현재 세대를 4그룹(0, 1, 2, 3)으로 나누었을 때 p 가 어느 그룹에 들어가는지 계산 int group = p / slice; // 그룹 0 이면 무조건 RR if (group == 0) return "RR"; // 그룹 3 이면 무조건 rr if (group == 3) return "rr"; // 세대를 축소해서 계산한다. return find(n - 1, p % slice); } public String[] solution(int[][] queries) { return Arrays.stream(queries) .map(query -> find(query[0], query[1] - 1)) .toArray(String[]::new); } } ``` # 128강 - [23 07 06, ken 12268, 128강, 운영체제, 영상없음]() - [문제 - [PCCP 모의고사 #1] 운영체제](https://school.programmers.co.kr/learn/courses/15008/lessons/121686?language=java) ## 정답 ```java import java.util.*; import java.util.stream.Collectors; public class Main { public static void main(String[] args) { System.out.println(Arrays.toString(new Solution().solution(new int[][]{{2, 0, 10}, {1, 5, 5}, {3, 5, 3}, {3, 12, 2}}))); // 출력: [20, 5, 0, 16, 0, 0, 0, 0, 0, 0, 0] } } // 전략 // - class Solution { private static class Program { public final int priority; public final int calledAt; public final int executionTime; private Program(int priority, int calledAt, int executionTime) { this.priority = priority; this.calledAt = calledAt; this.executionTime = executionTime; } } public long[] solution(int[][] program) { // 시작시간 순으로 정렬 Queue programs = Arrays.stream(program) .map(p -> new Program(p[0], p[1], p[2])) .sorted(Comparator.comparingInt(p -> p.calledAt)) .collect(Collectors.toCollection(LinkedList::new)); // 우선순위 위주로 정렬, 그것으로 우열을 가릴 수 없다면 시작시간으로 가른다. PriorityQueue pq = new PriorityQueue<>((a, b) -> { if (a.priority != b.priority) return a.priority - b.priority; return a.calledAt - b.calledAt; }); long[] waitTimes = new long[11]; int time = 0; // 2개의 큐가 모두 빌 때까지 반복 while (!programs.isEmpty() || !pq.isEmpty()) { // 시작할 시간이 된 프로그램을 pq 로 옮긴다. // 그 조건을 만족하는 프로그램이 1개 이상일 수 있으니 반복문 사용 while (!programs.isEmpty() && time >= programs.peek().calledAt) { pq.add(programs.poll()); } // 현재 pq 가 비어있다면 시간(time)을 증가시킨다. // 그 다음 실행대기 중인 프로그램이 실행되는 시간으로 세팅한다. // 그래야 그 다음 반복에서 pq 에 옮겨지면서 진행된다. if (pq.isEmpty()) { time = programs.peek().calledAt; continue; } // 실행할 프로그램을 꺼낸다. Program p = pq.poll(); // 프로그램이 원래 실행되어야 하는 시간보다 얼마나 더 지체되었는지 합산한다. waitTimes[p.priority] += time - p.calledAt; // 어짜피 이 프로그램이 실행중이면 다른 프로그램은 실행되지 못하니 time 을 이 프로그램이 끝나는 시간으로 돌린다. time += p.executionTime; } waitTimes[0] = time; return waitTimes; } } ``` # 129강 - [23 07 11, ken 12268, 129강, 실습용 로봇, 영상없음]() - [문제 - [PCCP 모의고사 #2] 실습용 로봇](https://school.programmers.co.kr/learn/courses/15009/lessons/121687?language=java) ## 정답 ```java public class Solution { private static final int[] dx = {0, 1, 0, -1}; private static final int[] dy = {1, 0, -1, 0}; public int[] solution(String command) { int x = 0; int y = 0; int d = 0; for ( char c : command.toCharArray() ) { switch ( c ) { case 'R' -> d = (d + 1) % 4; case 'L' -> d = (d + 3) % 4; case 'G' -> { x += dx[d]; y += dy[d]; } case 'B' -> { x -= dx[d]; y -= dy[d]; } } } return new int[] {x, y}; } } ``` # 130강 - [23 07 14, ken 12268, 130강, 신입사원 교육, 영상없음]() - [문제 - [PCCP 모의고사 #2] 신입사원 교육](https://school.programmers.co.kr/learn/courses/15009/lessons/121688?language=java) ## 정답 ```java ```