내 지식 메모장

Q. 1981 자바 : 배열에서 이동

Q. 1981 자바 : 배열에서 이동 문제 : boj.kr/1981P5 난이도의 문제이다. 문제를 간단히 설명하자면그래프가 주어지고 1,1 ~ n,n까지 이동하려고 할 때, 거쳐간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 문제이다.처음에 이분 탐색과 BFS를 활용한 방식으로 풀었고 아래와 같이 풀었지만 틀렸다.1. 거쳐간 수들의 (최댓값-최솟값) = mid로 정의한다.2. BFS 방식으로 이동하며 mid가 가능한지 조회한다.3. 조건에 따라 이분탐색 방식으로 mid의 범위를 좁혀나간다이 방법은 잘못된 방식이었다.static boolean determination(int mid) { visit = new boolean[n][n]; Queue que = new ArrayDeq..

Q. 16566 자바 : 카드 게임

Q. 16566 자바 : 카드 게임 문제 : boj.kr/16566P5 난이도의 문제이다. 문제를 간단히 설명하자면카드 더미가 주어진다. 이 때 상대는 나와 동일한 카드 더미를 가진다.그리고 상대의 카드가 주어질 때 상대의 카드보다 크면서 이전에 낸 적 없는 가장 작은 카드를 출력하는 문제이다.먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을 것 같다.1. 상대의 카드보다 크면서 이전에 낸 적 없는 카드 중 가장 작은 카드를 카드 더미에서 찾는다.2. 사용한 카드는 사용했다고 처리한다.3. 1~2 과정을 반복한다. 이렇게 푼다면 낼 수 있는 카드를 찾을 때 N^2번의 연산이 생기고, 이전에 낸 적 없는 카드를 찾는데 최악의 경우 N번의 연산이 생기므로 총 N^3 * K의 시간복잡도를 가지게 된..

Q. 3197 자바 : 백조의 호수

Q. 3197 자바 : 백조의 호수 문제 : boj.kr/3197P5 난이도의 문제이다. 문제를 간단히 설명하자면얼음, 물, 백조가 있고, 물과 인접한 얼음은 시간이 지날 때 마다 물로 변한다.백조는 물이 있는 영역으로만 지나다닐 수 있을 때, 두 백조가 만날 수 있는 최소 시간은 몇초인지 구하는 문제이다.먼저 완전 탐색 방식으로 푼다고 가정하면 아래와 같이 풀었을 것 같다.1. 물 근처의 얼음을 완전탐색을 활용해 녹인다.2. 녹인 후 백조가 만날 수 있는지 계산한다.3. 만약 백조가 만날 수 없다면 1, 2번 과정을 반복한다. 이렇게 푼다면 R, C의 범위가 1500이므로 R^2 * C^2의 시간복잡도를 가지고,시간제한은 2초이므로 이 방법은 불가능해 보였다.그래서 완전 탐색이 아닌 다른 방법을 생각해..

DB Lock

최근 간단한 예약 서비스 과제를 진행하면서, JPA의 Lock을 직접 다뤄야 하는 상황이 생겼다. @Transactional만으로는 동시성 문제가 해결되지 않았고 비관적 락(Pessimistic Lock) 을 적용해 해결했다.이후 해당 내용에 대해 좀 더 자세히 알아보고자 글을 작성하게 되었다. 대표적으로 사용하는 DB중 하나인 MySQL 기준으로 작성할 예정이며 아래와 같은 순서로 작성하겠다. 1. DB Lock의 기본 개념2. Read Lock vs Write Lock3. 비관적 락 vs 낙관적 락4. 교착 상태5. ORM과 Lock (JPA)1. DB LockLock은 왜 사용해야 할까? 예를 들어 캐치테이블 같은 예약 앱을 생각해보자.여러 명의 유저가 동시에 예약을 시도했을 때, 누가 예약을 ..

ABOUT ME

내 지식 메모장 내 지식 메모장

최신 글

인기글 + 내용

티스토리툴바