📌 문제 https://www.acmicpc.net/problem/9466 📌 설명 DFS 를 통해 사이클을 찾는 방법을 사용하는 문제이다. 위 그림에서 A, B, C는 팀 생성이 불가능하며, 나머지는 팀 생성이 가능하다. DFS의 시작 노드를 start, DFS 수행 중 이미 방문한 노드를 처음 만났을 때 해당 노드를 cur 이라고 한다면...

📌 Flyway란? Flyway 는 데이터베이스 형상 관리 도구로, 데이터베이스 스키마의 변경사항을 추적 및 관리할 수 있도록 한다. Git이 소스 코드를 관리하는 것을 생각하면 된다. 가장 큰 장점은 SQL마저 버전 관리가 가능해진다는 점이다. 또한 flyway_schema_history 테이블에서 스키마 변경 이력을 확인할 수 있어 문제 추적...

📌 문제 https://www.acmicpc.net/problem/2110 📌 설명 이분 탐색으로 최적의 인접 공유기 사이 거리를 구해야 하며, 이를 parametric search 라고 한다. 공유기 사이 거리로 가능한 값 중, 가장 작은 값은 1이고, 가장 큰 값은 가장 멀리 떨어진 두 집 간 거리일 것이다. 첫 번째 공유기는 첫 번째 집에...

📌 문제 https://www.acmicpc.net/problem/1621 📌 설명  원숭이가 N개의 바나나를 가져간다. 두 가지 선택지가 있는데, 바나나 하나만 가져가거나 K개를 한꺼번에 가져가는 방법이 있다. 하나만 가져가는 경우 바나의 무게만큼 시간이 걸리며 K개를 한꺼번에 가져가면 C의 시간이 걸린다. 원숭이가 바나나를 모두 옮기는 데 걸...

📌 문제 https://www.acmicpc.net/problem/17387 📌 설명 CCW 알고리즘을 통해 해결했다. 네 점 A, B, C, D가 있고 선분 AB, 선분 CD의 교차 여부를 판단한다고 할 때, 선분 위의 두 점과 다른 선분의 나머지 한 점의 외적 값을 사용했다. 구체적으로 설명하자면 다음과 같다. ccw()는 세 점의 외적을...

📌 개요 JPQL 은 일반적으로 영속성 컨텍스트를 고려하지 않고 데이터베이스에 접근하여 작업을 수행한다. 영속성 컨텍스트와 어떠한 상호작용을 하는지는 JPQL이 어떤 쿼리인지에 따라 다르다. 📌 JPQL - SELECT 쿼리 만약 JPQL이 SELECT 쿼리였다면 실행하기 전 flush() 를 수행하여 데이터 일관성을 맞춘다. SELECT 쿼리...

📌 개요 백엔드 엔지니어라면 한 번 쯤 서비스를 배포한 경험이 있을 것이다. 배포에 필요한 AWS EC2와 RDS 등을 생성하기 위해 AWS 콘솔에 접속하여 관리하는 것은 정말 귀찮다. 리소스를 사용하지 않는다면 반드시 해제해야 과금이 발생하지 않는데, 자꾸 까먹어서 날린 돈만 얼마인지 모르겠다. 콘솔에 매번 접속해서 리소스를 관리하지 않고 AWS ...

📌 문제 https://www.acmicpc.net/problem/1103 📌 설명  전형적인 그래프 탐색 문제이지만, 사이클이 발생한 경우를 탐지해야 하므로 BFS 대신 DFS를 사용하는 것이 효율적이다. 그러나 단순히 DFS를 수행하며 동전이 움직일 수 있는 최대 횟수를 구하려고 하면 시간 초과가 발생하게 된다. 이미 방문한 지점인 경우, 추...

📌 문제 https://www.acmicpc.net/problem/10800 📌 설명   공이 다른 공을 사로잡을 수 있다. 사로잡기 위한 조건은 색이 다르거나, 크기가 더 작을때이다. 공에 대한 정보를 배열에 저장하고 브루트포스로 일일히 계산하게 되면 $O(N^2)$로 시간 초과가 발생하게 된다. 정렬과 누적 합 개념을 사용해야 한다.  공에...

📌 문제 https://www.acmicpc.net/problem/7453 📌 설명 이분 탐색을 통해 해결하였다. 주어진 네 배열을 두 배열 간 합을 통해 두 개의 배열로 축소시킨다. 정렬 후 이분탐색을 진행하면 된다. 주의해야 할 점은 가능한 답의 가짓수가 4000^4이라는 점이다. 따라서 long long 자료형을 사용해야 한다. 또한 중복...