오답 노트 & 새로 알게 된 점 MST 응용 문제인 것 같다. 항상 부모 배열을 -1로 초기화하고 부모는 하나 뿐인 MST 문제로 무지성으로 풀었는데, 해당 문제를 이렇게 풀면 바로 틀리게 된다. 여기서는 부모 배열 초기화부터 다르게 한다. 문제에서 발전소가 여러 개 있고, 발전소끼리 연결할 필요가 없다. 따라서 발전소를 각각 부모라고 생각하면 된다. 부모 배열을 모두 0으로 초기화 한 다음에, 발전소 위치 idx에 부모를 나타내기 위해 -1을 넣는다. 그렇다면 당연히 find와 union 메서드가 달라져야한다. 뜻이 달라진 것은 아니지만 안의 기능이 바뀌어야 한다. find 메서드는 부모가 같은지 찾는 메서드로 parent[v] 음수일 경우 발전소와 연결됐으므로 -1 반환 0 아무것도 연결되지 않음. ..

오답 노트 & 새로 알게 된 점 도시를 두 개로 분할해야한다. 다만, 도시 안에 마을끼리는 무조건 연결되어야 한다. 그렇다면 MST를 사용하여 모든 노드들을 연결해준다. 이 때, 가장 큰 가중치 하나를 빼주면 된다. 어차피 MST이기 때문에 모든 노드들은 연결되어있다. 그래새 분할해서도 최소 값을 구하고 싶다면 제일 큰 가중치를 빼주면 된다. 코드 package bfs_dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import ja..

오답 노트 & 새로 알게 된 점 기본 MST 문제이다. 다만 입력 부분에서 두 노드와 가중치를 주는 것이 아닌, 행렬로 주었다. 또한, 가중치가 최대 1억, N이 1000이므로 결과값이 Long이 나올 수 있다. 입력 부분에서 양방향이기 때문에 대각선을 기준으로 대칭이다. ---- 1 | 2 | ------ 1번이나 2번 구역 중 하나의 구역만 선택하여 기본 MST처럼 풀면 된다. 코드 package bfs_dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util...

오답 노트 & 새로 알게 된 점 해당 문제는 처음에 읽고 어떻게 풀어야할지 감이 안왔다. 1. 처음에는 완탐을 생각하면서 일일이 구할 생각을 했지만, 당연히 TLE다. 2. class마다 포인터를 두어 하나하나 탐색하려고 했다. 하지만 이 방법도 1번 방법과 다른 점이 없고, class의 개수는 항상 달라지는데 이걸 구분할 방법도 생각나지 않았다. 결국 풀이를 보고 문제를 해결했다. 문제 해결을 하기 위해 문제를 바꾸는 것이 중요한 부분이다. 모든 학생들을 능력치 오름차순으로 일렬로 정렬을 한다. 여기서 해당 학생은 어느 class에 속해있는지 알아야한다. 일렬로 정렬하고 두 포인터를 이용하여 N개의 class가 모두 포함되면 그 때 능력 차이를 구하면 된다. 코드 1 2 3 4 5 6 7 8 9 10 ..

오답 노트 & 새로 알게 된 점 문제의 식을 써보면 G + 기억몸무게^2 = 현재몸무게^2 으로 나타낼 수 있다. 따라서 G = (현재몸무게^2) - (기억몸무게^2) = (현재몸무게+기억몸무게) * (현재몸무게 - 기억몸무게) getMul 투포인터를 이용하여 곱이 G가 되는 두 수를 구합니다. get getMul을 통하여 얻은 두 수를 가지고 나눠 떨어지는지 확인합니다. max = (현재 몸무게 + 기억 몸무게) min = (현재 몸무게 - 기억 몸무게) max + min = 2 * 현재 몸무게 max - min = 2 * 기억 몸무게 둘 다 2로 나누어 떨어지지 않으면 자연수 G가 나올 수 없기 때문에, (max + min) % 2 == 0 && (max-min) % 2 == 0 가 필요하다. 현재 ..

JPQL은 왜 사용하나? 우리는 DB에서 데이터를 조회할 때, em.find를 통해 쉽게 조회할 수 있다. 그런데 왜 JPQL을 사용할까? 예를 들어 member가 100명이 있는데 여기서 특정 나이 이상인 member를 조회하고 싶다. 그렇다면 우리가 할 수 있는 일은 모든 member 수 만큼 em.find를 하여, 각 member 객체의 age를 조회해야한다. 데이터의 개수가 더욱 더 늘어난다면 우린 DB에 있는 모든 member들을 모두 객체로 만들어야한다. 이 점이 불가능하기 때문에 검색 조건이 있는 JPQL을 사용하여 쉽게 조회할 수 있다. JPQL의 특징 우리가 흔히 알고 있는 SQL은 DB 테이블을 대상으로 쿼리를 짠다. 하지만 JPQL은 엔티티 객체를 대상으로 쿼리를 작성한다. 또한, 앞..

오답 노트 & 알게 된 점 문제를 보면 가중치가 1이라고 했으므로 최단 경로를 구하는 알고리즘 중 BFS를 사용하면 된다고 생각했다. 문제에서 건물이 2개가 지어지고, N이 최대 100이다. 따라서 시간복잡도는 100C2 * 100 * 100으로 1억이 안된다. 즉, N개 중에 2개를 중복X, 순서X인 조합을 구하여, 2개의 노드에서 나머지 노드들 간의 거리를 구하면 된다. static void dfs(int start, int cnt) { if(cnt == 2){ bfs(); return; } for (int i = start; i sum){ ans = sum; build1 = select[0]; build2 = select[1]; } 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

JPA의 데이터 타입 JPA의 데이터 타입은 크게 엔티티 타입과 값 타입으로 나눌 수 있다. 엔티티 타입과 값 타입의 가장 큰 차이는 식별자의 유무이다. 엔티티는 식별자를 통해 구별할 수 있지만 값은 할 수 없다. 기본 값 기본 값은 엔티티에 생명주기를 의존한다. Member가 삭제되면 age나 name이 삭제되기 때문이다. 임베디드(embedded) 임베디드 타입은 사용자가 JPA에서 새로운 값 타입을 직접 정의한 것이다. 임베디드 타입은 여러 곳에 사용할 수 있는 재사용성이 좋다. member도 주소가 필요하고, group도 주소가 필요할 때 member에 주소를 모두 쓰고, group에도 주소를 모두 쓰는 것보다 주소 임베디드 타입을 만든다면 매우 객체지향적이고 깔끔한 코드가 될 것이다. 임베디드 ..

오답 노트 & 새로 알게 된 점 이 문제는 전에 풀었던 불!과 비슷한 단계형 bfs 문제다. 파도가 한 번 칠 때마다 모래성을 부수고 완전히 온전한 상태가 될 떄까지 파도의 횟수를 구하는 것이다. 처음에 문제를 이해하는데 어려움이 있었다. 온전한 상태가 무슨 말일까? 아무리 파도가 쳐도 무너지지 않는 모래성이다. 9는 무조건 온전한 상태이며, 주위에 있는 9의 개수에 따라서 8, 7 등 다른 숫자들도 온전한 상태가 될 수 있다. 처음 문제 풀이 처음 문제를 풀 때는 bfs를 돌릴 때, 9나 . 이 아닌 숫자들을 다 넣어주었다 그리고 각각 위치에서 8방향으로 탐색한 뒤, 부숴질 모래성이면 nonstable 배열에 저장하여 위치를 저장한 뒤에 bfs가 끝나면 그 때 . 을 넣어주었다. 하지만 위와 같이 문제..

오답 노트 & 새로 알게 된 점 이런 유형의 문제를 단계별 bfs문제라고 생각한다. 한 번에 bfs를 돌려서 문제의 답을 구하는 것이 아니라, 한 타임 돌리고, 또 한 타임 돌리면서 답을 구하는 것이다. 이 문제도 보면 불이 이동하고 -> 지훈이가 이동한다. 이게 한 사이클이다. 문제에서 동시에 이동한다고 했으니, 불이 먼저 이동할까 지훈이가 먼저 이동할까를 생각해봤다. 동시에 이동한다고 했을 때, 불이 있는 곳에 지훈이가 가면 어떻게 될까 라는 생각을 했고, 이로 인해 불이 먼저 움직여야겠다는 결론을 내렸다. 불이 이동하는 bfs, 지훈이가 이동하는 bfs를 따로 만들어줬다. 둘의 bfs에는 공통점이 있다. 각각의 큐가 empty 될 때까지 돌리는 것이 아니라, 한 사이클만 돌린다. 즉, 현재 시점에서..

지연 로딩 즉시 로딩과 지연 로딩의 차이는 내 생각엔 필요할 떄 조회하는 것 같다. 지연 로딩은 필요할 때 찾고, 즉시 로딩은 처음부터 다 찾는거다. 그리고 지연 로딩을 하는 LAZY 옵션을 사용하면, 앞에서 배운 프록시 클래스가 생성이 되는 것을 알 수 있다. Member findMember = em.find(Member.class, member1.getId()); System.out.println("findMember.getClass() = " + findMember.getClass()); System.out.println("findMember.Team = " + findMember.getTeam().getClass()); System.out.println("여기 시점에 team을 조회하므로 쿼리가 ..

프록시 프록시를 사용하면 객체를 처음부터 DB에서 조회하는 것이 아니라 실제 사용하는 시점에 DB에서 조회하는 것이다.(= 지연 로딩) 예를 들어 Member와 Team이 연관관계 매핑이 되어있다. 그러면 find를 통하여 Member를 찾을 때, join 쿼리를 이용하여 Team도 당연히 조회가 된다. 이 부분이 효율적이지 못해 프록시를 사용한다면 Member를 찾을 때, DB에서 Member만을 조회하여 조회할 수 있다. getReference & find 우리는 엔티티를 조회할 때 em.find를 사용해왔다. find는 위와 같은 실제 엔티티를 반환하게 된다. 하지만 em.getReference는 프록시 객체를 가져온다. Member findMember = em.getReference(Member...