알고리즘 고수가 되기까지

코테 준비

1. 백준 5021 - 왕위 계승

: 위상 정렬을 이용해서 풀이. 내 피가 계산되려면 내 부모의 피가 모두 결정되어야하므로, 위상정렬을 이용함

2. 백준 14676 - 영우는 사기꾼?

: 건물을 지을 수 있는 경우를 indegree로 판단. 건물이 처음 지어진 경우 자식의 indegree를 줄이고, 마지막 남은 건물이 부서질 경우 자식의 indegree를 올리는 방식으로 풀이. 

오늘 하루도 고생했다!!!

코테 준비

1. 백준 14921 - 용액 합성하기

: 정렬되어있는 수를 양쪽 끝에서부터 투 포인터로 찾아가며, 절댓값이 0이랑 가장 가까운 수를 구하는 문제. 투포인터 기본문제라고 생각함

2. 백준 20366 - 같이 눈사람 만들래?

: 눈덩이를 정렬한 후에, 한 눈사람을 만들 두 개의 눈덩이를 구함. 이 후 그 사이에서 투포인터를 이용해서 그 눈사람과 가장 작은 차이가 나는 눈사람을 구함. 문제를 풀기위한 핵심은 두 눈덩이를 정하고, 거기서 정답이 나올 수 있는 것은 두 눈덩이 사이에서 눈사람을 만들 경우라는 것.

오늘도 고생했다!!!

코테 준비

1. 백준 11723 - 집합

: 집합을 비트로 관리해서 푸는 문제. 비트연산자를 골고루 사용해볼 수 있었던 문제

2. 백준 1194 - 달이 차오른다, 가자

: 가지고 있는 열쇠를 비트 연산으로 푸는 문제. 현재 좌표, 가지고 있던 열쇠 조합으로 방문 처리를 해서 bfs를 이용해 최단 경로를 찾는 문제

오늘 하루도 고생했다!!!

코테 준비

1. 백준 7579 - 앱

: dp에서 cache배열을 이용할 때 메모리나 범위가 넘어선다면, 생각을 전환해서 cache배열을 만들자. 위 문제로 예를 들면, 최소의 cost를 구하는 문제라면 최대의 memory로 바꿔서 생각하자

2. 백준 2629 - 양팔저울

: 어떤 탐색이 중복되는지 확인하자. 결국 knapsack은 dp이다

오늘 하루도 고생했다

부트캠프 강의 - java

1. 문제
   - '다형성'이란?

2. 시도
   - 글을 찾아보자

3. 해결
   - '다형성'이란 말 그대로 '다양한 형태를 가질 수 있음'이란 뜻임
   - 결국 어떤 한 객체가 여러가지 타입이 될 수 있다는 뜻
   - 이 말을 좀 더 java스럽게 풀어보면, 상위클래스 타입의 참조변수로 하위 클래스의 객체를 참조할 수 있도록 하는 것임
   - 이 상위타입 참조변수는 생성된 하위클래스가 무엇인지에 따라서 같은 메소드를 실행하더라도, 오버라이딩된 것에 따라 다른 결과가 나올 수 있음

4. 알게된 점
   - 다형성 -> 다양한 형태를 가질 수 있다 -> 상속관계에서 두드러지게 나타남

1. 문제
   - System.identityHashCode()가 반환하는 값은 뭘까?

2. 시도
   - 직접 출력해보자

3. 해결
   - Object 클래스의 toString은 결국 해당 객체의 hashCode를 hexString(16진수)로 바꾼 값을 출력함
   - 그리고 Object 클래스의 hashCode는 객체의 메모리 주소를 기반으로 생성됨
   - 따라서, System.identityHashCode의 값은 메모리 기반으로 생성된 해시코드의 값을 출력하는 것
   - 실제로 객체를 하나 만들고 그 객치의 System.out.println()과 System.out.println(Integer.hexString(System.identityHashCode))의 값은 같음

4. 알게된 점
   - System.identityHashCode()는 객체의 메모리 주소 기반으로 생성된 hashcode값을 반환함

1. 문제
   - getClass와 instaceof 의 차이

2. 시도
   - 직접 알아보자

3. 해결
   - Parent p = new Child()일 때
   - getClass는 객체가 무엇으로 생성되었는지를 나타냄 -> p.getClass() == Child.class임
   - instaceof는 가능한 타입 모두를 나타냄 -> p instaceof Parent 또는 p instaceof Child 모두 가능

4. 알게된 점
   - getClass는 생성된 클래스, instanceof는 타입으로 가능한 클래스라는 차이가 있음

1. 문제
   - @FunctionalInterface의 의미

2. 시도
   - 강의

3. 해결
   - 애너테이션은 컴파일러에게 정보를 줄 때 사용
   - @FunctionalInterface 애너테이션은 해당 interface의 추상메서드는 1개라는 점을 알려주는 애너테이션
   - 그래서 만약 이 애너테이션을 사용하고 추상 메서드를 두 개이상 선언했을 때, 컴파일에서 에러가 남
   - 함수형 인터페이스는 람다를 쓸 수 있다를 알려주는 뜻이기도 함

4. 알게된 점
   - @FunctionalInterface는 추상메서드가 한개인 interface를 알려주는 애너테이션(개발자와 컴파일러 모두에게 알려줌) 

코테 준비

1. 백준 1509 - 팰린드롬 분할

: dp는 완전탐색에서 똑같은 탐색을 두 번다시 안하게 하는 기법. 탑다운 방식으로 재귀함수를 이용해서 먼저 구현하고, 이 후 중복되는 탐색을 dp배열을 이용해서 제거한다.

2. 백준 2482 - 색상환

: 모든 경우는 하나를 선택했을 때와 하나를 선택하지 않았을 때 발생하는 일의 합. 좀 더 쉽게 생각하자

오늘 고생했다!!! 

부트캠프 강의 - java

1. 문제
   - override가 동적 바인딩이라고 불리는 이유?

2. 시도
   - Superclass s = new SubClass(); s.f(); 일 때, s.f()가 SubClass의 f함수가 호출됨

3. 해결
   - 컴파일 단계에서는 s.f()는 SuperClass에 f()가 있으므로 문제가 없다고 인식하고 컴파일 완료
   - 이 후 런타임 시점에 s.f()를 실행할 때, 먼저 jvm은 s를 힙에서 찾음
   - s의 타입은 SuperClass이므로 먼저 상위타입에서 해당 메서드를 찾음
   - 그런 후, 이 인스턴스가 상속관계이므로 하위타입에서 f()가 재정의 되어있다는 것을 확인하고 아래 메서드를 찾아서 실행
   - 이렇게 런타임시에 호출하는 메서드를 동적으로 찾아서 결정하는 것을 '동적바인딩'이라고 부름

4. 알게된 점
   - overloading은 컴파일 시점에 호출하는 메서드를 찾아 결정하기 때문에 '정적바인딩'
   - overriding은 런타임 시점에 호출하는 메서드를 찾아 결정하기 때문에 '동적바인딩'

1. 문제
   - 람다 캡처링에 대해 자세히 알아보자

2. 시도
   - 람다 내부에서 지역변수를 사용할 때, 사용하려는 지역변수는 final이거나 effectively final이어야 함(지역변수의 값이 바뀌면 안됨)
   - 이유가 뭘까

3. 해결
   - 가장 먼저 JVM 메모리 구조에서 지역변수는 stack에, 인스턴스는 heap에 생성됨
   - 람다도 결국 인스턴스임. 따라서 heap에 생성됨
   - 따라서, 지역변수와 람다는 생성과 소멸 주기가 다름
   - 지역변수는 stack에서 사라졌지만, 람다는 heap에 여전히 남아있을 수 있음. 그래서 람다에서 사라진 지역변수를 참조하려고 하면 에러가 남
   - 그래서 java에서는 이러한 문제를 해결하기 위해 '람다 캡처링'을 사용함
   - 람다에서 사용하려는 지역변수를 '캡처(복사)'해서 사용함
   - 그리고 람다를 생성하는 시점과 쓰레드에서 실행하는 시점이 다를 수 있는데, 그 사이에 지역변수 값이 바뀌게 되면 문제가 발생할 수 있음
   - 그래서 람다에서 사용하는 지역변수는 final이거나 effectively final이어야 함

4. 알게된 점
   - 람다 캡처링을 알기위해서는 jvm 메모리 구조부터 중요하다
   - 기본기는 배신하지 않는다

코테준비

1. 백준 15683 - 감시

: CCTV를 어떻게 둘러보는지를 표현하는게 관건이었던 문제. 나머지는 편안한 재귀였다

2. 백준 17825 - 주사위 윷놀이

: map자체를 표현하는 게 관건이었던 문제. 나머지는 재귀 후 시뮬레이션하는 문제였다

오늘 하루도 고생했다

부트캠프 강의 - java

1. 문제
   - 메서드 안에 클래스를 정의해서 사용할 경우, 왜 지역 클래스 내부에서 메서드의 지역변수를 바꿀 수 없을까?

2. 시도
   - 강의, 책, 블로그를 통해 확인해보자

3. 해결
   - 지역 클래스와 메서드 내의 지역변수는 생성 및 소멸 시기가 달라서 그렇다
   - 지역 클래스의 instance는 heap에 생성되고 지역변수는 stack에 생성되는데, 만약 생성된 instance가 이미 stack에서 사라진 지역변수를 사용할 수 없기 때문임
   - 또한, 지역 클래스에서는 final로 된 지역변수에만 접근할 수 있다
   - 이유는 지역클래스는 이렇게 생성과 소멸이 다른 지역변수를 사용하기 위해서 지역변수의 복사본을 가져옴
   - 그런데, 만약 지역변수가 final이 아니라 계속 변한다면 여러 Thread들 간의 동기를 맞출 수 없음
   - 그래서 결국 지역클래스에서 지역변수를 사용하려면, 지역변수가 final이어야함(또는 effectively final)

4. 알게된 점
   - 이러한 지역클래스가 나중에 익명클래스, 람다와 연결되는 것 같다. 확실하게 알아두자

코테 준비

1. 백준 4256 - 트리

: preorder와 inorder에서 규칙을 찾고, 이에 따라 재귀함수를 작성. 규칙을 찾는것과 이를 재귀함수로 옮기는 것, 이 두 가지를 모두 숙달시켜야함

2. 백준 17480 - 개구쟁이 준석이

: 일단 해당 문자열에서 알파벳 갯수를 세는 방법으로는 26개의 알파벳 배열을 만들어서 해당 문자열의 index의 값을 증가시키는 것이 있음. 만약 문제에서 재귀함수의 방법이 주어졌다면, 해당 방법을 정확하게 구현하는 것이 핵심

오늘 하루도 고생했다!!!

코테 준비

1. 백준 17472 - 다리 만들기 2

: 풀어본 문제지만 전에는 mst를 이용하지 않고 dfs로 풀었다. input이 작았기에. 이번에는 크루스칼 알고리즘을 이용해서 풀어보았다. 크루스칼 알고리즘의 핵심은 간선들을 비용이 작은 순으로 정렬하고, 하나씩 골라가면서 union-find를 이용해서 연결되어있는지 확인한다.

2. 백준 1774 - 우주신과의 교감

: 크루스칼 알고리즘으로 풀이. mst일시 꼭 기억하자

문시해알 다시 적용시켜서 TIL 살려보자!!!