본문 바로가기

전체보기

 (180)
JPA 연관 관계에서 set과 list 차이 문제 제기 인터넷에서 연관 관계에 대한 코드를 찾아보면 List가 아닌 Set을 사용하는 경우가 있어 무슨 차이인지 궁금했다. 이 글은 아래 사항들을 알고 있단 가정 하에 썼다. - List와 Set 연산의 시간 복잡도 - OneToMany 연관관계 mapping 속성들 5.0.8 이전의 hibernate hibernate문서를 보면 연관 관계를 맺을 땐, List가 더 나은 성능을 보인다 했다. 하지만, 이 때 HHH-5855 이슈가 생겼다. CASCADE를 MERGE, PERSIST, ALL 셋 중 하나로 준 경우 연관관계의 주인이 아닌 쪽에 객체를 생성하면, INSERT 쿼리가 두 번 발생해 중복이 생겼다. 예를 들자면, Parent와 Child는 1:N의 관계를 가진다고 하자. 연관관계의 주인인 ..
Serialization (+ JPA) 보호되어 있는 글입니다.
SW 마에스트로 13기 지원 후기 (면접 불합격) 1차 코딩 테스트 대체로 무난한 편이었다. 대부분 구현 문제였다. 다만, 한 문제가 lower bound upper bound 보고 풀어야 했는데 백트래킹으로 풀어 시간 초과가 난 문제가 하나 있었다. sql은 프로그래머스 고득점 kit 을 모두 풀었다면 5분내로 풀 수 있었다. 웹은 css로 클릭할 때 색을 주는 문제였다. 올해는 검색을 막아서 그런지 합격 컷이 되게 낮았던 거 같았다. 2차 코딩 테스트 갠적으로 1차보다 쉬웠다. 알고리즘의 경우 1번은 완전탐색, 2번은 bfs 또는 유니온 파인드 문제였다. 3번같은 경우엔 dp + 비트마스크 문제였다. 1번의 경우 범위도 작아서 그냥 완탐 시뮬레이션으로 하면 됐다. 괜히 욕심부려서 어중간하게 최적화를 했다면 틀렸을 문제 2번 문제의 경우 딱 보고 유니..
백준 [1045] 도로 무난한 최소 스패닝 트리 문제 문제 설명이 좀 난해할 뿐이지, 기본 개념 문제와 별 차이는 없다. https://www.acmicpc.net/problem/1045 1045번: 도로 0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, www.acmicpc.net 문제 요약을 하자면 다음과 같다. i < j 인 간선들 중에서 i가 작은 순으로 나열한다. i 가 같다면, j가 작은 순으로 나열 이 때 모든 도시가 연결되있지 않으면 -1 간선의 수가 M개가 되지 못하면 -1 그 후, 상위 M개의 간선에서 시작점과 끝점의 index 카운팅 후..
백준 [16297] Eating Everything Efficiently DP + 위상 정렬 문제 수학적 센스가 필요한 문제다. DFS로도 풀 수 있다. https://www.acmicpc.net/problem/16297 16297번: Eating Everything Efficiently Margriet A. is in pizza heaven! She has bought a oneday access pass to Pizza World. Pizza World is a food festival, where all stands have their own special type of pizza. Margriet would really like to try many different types of pizza, but she thinks that www.acmicpc.net 문제를 요..
백준 [2637] 장난감 조립(JAVA) 2차원 dp 테이블을 이용했다. 완성품 즉, 엔드 포인트가 N이라고 했으니 이 N을 기준으로 각 부품들의 개수를 구해주면 된다. 각 중간 부품들과 완제부품들에 기본 부품이 몇 개나 필요한지 모두 적어보면 감이 잡힐 것이다. 코드 더보기 import java.io.*; import java.util.*; class Main { static int N, M; static int[] count; static int[][] dp; static ArrayList[] nodes; static StringBuilder answer = new StringBuilder(); public static void main(String[] args) throws Exception { input(); solve(); print(..
위상 정렬(topological sorting) 유향그래프에서 각 정점들이 한 방향으로 나열된 형태 정점 u와 v가 u -> v 순서일 때, 어떠한 경우에도 u -> v 순서가 유지된다. 이러한 특성 때문에 사이클이 존재하지 않는다. 주로 다음과 같은 곳에 사용된다. 1. 소프트웨어 공학에서 일정 계획 방법론인 PERT나 CPM 2. 스킬트리, 선수과목 같은 사전 작업같은 것이 필요한 작업들 물론, BFS/DFS만으로 풀 수 있지만 위상 정렬을 알면 더 쉽게 풀 수 있다. 위상 정렬의 수행 과정 2개 배열이 필요하다. 해당 정점에 연결된 간선의 수를 담는 배열 A 정점별로 간선 자료구조를 담는 배열 먼저, 자신을 가리키는 간선이 없는 정점들을 찾는다. 해당 정점에서 출발하는 간선이 있으면 지움 (배열 A의 카운트를 1 줄인다.) 만약, 해당 간선의 도..
최소 스패닝 트리(MST, Minimum spanning tree) 최소 신장 트리라고도 한다. 그래프에서 최소 스패닝 트리를 만들기 위해선 다음 조건을 만족해야 한다. 1. 모든 정점은 연결돼있다. 2. 사이클이 없어야 한다.(트리 형태이기 때문) 3. 최소 가중치를 가진 무방향 간선들로만 연결돼야 한다. (간선의 개수는 정점의 개수 - 1 개) 즉, 모든 정점을 사이클 없이 최소한의 비용으로 연결해야 한다. 그림으로 올바른 형태와 잘못된 형태를 보면 다음과 같다. 모든 정점을 최소한의 비용으로 연결한단 특성 때문에 통신, 운송 네트워크 등 공급과 관련된 연결망을 구축하는 문제들이 많다. 스패닝 트리를 만드는 알고리즘은 크게 2가지가 있다. 각각 유리한 점이 있고, 특정 풀이를 쓰도록 강요하는 문제는 많이 없기 때문에 편한걸 쓰면 된다. 1. 크루스칼 알고리즘 가중치가..

티스토리툴바