일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 구현
- BFS
- 백트래킹
- union-find
- disjoint set
- 누적 합
- tarjan
- 그래프
- Java
- Meet in the middle
- 위상 정렬
- DFS
- 분리 집합
- 투 포인터
- MST
- 위상정렬
- kruskal
- kapt
- BindingAdapter
- 이분 탐색
- Linux
- concurreny
- miller-rabin
- MySQL
- DP
- 알고리즘
- spring boot
- 페르마 소정리
- springdoc
- SCC
- Today
- Total
목록전체 글 (52)
기맹기 개발 블로그
BOJ 2150 Strongly Connected Component 난이도 : 플래 5 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 전략 SCC를 공부하면서 종만북의 타잔 알고리즘으로 구현해보았다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..
BOJ 2473 세 용액 난이도 : 골드 3 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 전략 생각할 수 있는 가장 간단한 방법은 세 용액의 모든 조합을 찾는 것이다. 3중 for문으로 세 용액의 조합을 만든다면 O(N^3)이다. N의 범위는 [3, 5000] 이므로 N^3은 5^3 * 10억이다. 따라서 다른 방법을 찾아야 한다. 만약 두 개의 용액 조합을 찾는다면 나머지 하나의 용액은 모두 찾을 필요 없이 이진 탐색..
BOJ 12100 2028 (Easy) 난이도 : 골드 2 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 전략 각 라운드마다 위 / 아래 / 왼쪽 / 오른쪽 4방향으로 이동시킬 수 있다. 문제에서 최대 5번으로 제한을 뒀으므로 모든 경우의 수는 4^5 = 1024이다. 브루트포스로 가능하기 때문에 구현에 초점을 둬서 진행한다. 시행착오 셀 충돌하고 병합하는 과정을 구현하면서 루프의 범위가 잘못된 경우가 있었다. 이..
BOJ 2623 음악프로그램 난이도 : 골드 3 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 전략 위상정렬을 사용하여 풀 수 있는 문제임을 알 수 있다. 2252 줄세우기 문제와 비슷하지만 다른 점이 있다. 예제의 입력을 보면 이렇게 각 PD별로 가수의 순서를 정할 수 있는데, 1:1이 아니라 여러명의 가수의 순서를 정하는 것이다. 이로 인해 하나의 노드에서 여러 개의 링크를 가질 수 있다. 따라서 링크를 배열로 저장하여..
캡스톤 프로젝트를 진행하면서 다음과 같은 다대다 관계를 나타내었다. 사용자와 스터디 그룹은 다대다 관계이므로, ERD에서 중간 테이블로 표현하였다. 그런데 JPA에서 구현하다보니 다음과 같은 기존 코드에서는 1+N 문제가 발생하였다. (N+1 문제라고 보통 불리는데, 나는 1+N이 더 직관적으로 표현한다고 생각해서 앞으로 1+N이라고 표시하고자 한다.) 사용자, 그룹 엔티티 역시 다대다 관계를 표현하기 위해서 User StudyGroup으로 일대다-다대일로 연결하였다. 정상적으로 조회 결과는 반환하지만, join으로 한 번의 쿼리를 받는 의도와는 다르게 1+N 번의 쿼리가 발생한다. 1+N 문제를 해결하기 위해서 fetch 조인을 해야하는데, 이를 위해 꼭 필요하지 않은 쿼리를 작성하는게 조금 꺼려졌다...
위와 같은 형식으로 AdviceDetailEntity의 필드로 List를 가지는 쿼리를 MyBatis에서 작성하였다. 그런데 이러한 오류가 발생하였다. Cause: java.lang.IndexOutOfBoundsException 처음에는 MyBatis가 잘못된줄 알고 열심히 찾아봤는데 문제는 AdviceDetailEntity에 있었다. 기존에는 위와 같이 롬복의 Getter, Setter, AllArgsConstructor만 존재했다. 하지만 MyBatis에서 resultMap으로 매핑하는 과정에서 comments 매개변수가 없는 상태로 객체를 생성하려고 하면서 생기는 오류였다. 이렇게 @NoArgsConstructor 어노테이션을 추가하여 오류를 해결할 수 있었다.
로컬의 인텔리제이에서 실행할 때는 문제가 없었는데, jar로 배포한 이후에 다음과 같은 오류가 발생하였다. org.springframework.beans.factory.UnsatisfiedDependencyException: Error creating bean with name 'topicController': Unsatisfied dependency expressed through field 'topicService'; nested exception is org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'topicServiceImpl': Lookup method resolution failed; ..
BOJ 14238 출근 기록 난이도 : 골드 3 https://www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 전략 S의 길이가 최대 50이므로, 모든 경우의 수를 다 탐색하면 안된다. 메모이제이션을 사용해서 중복된 연산을 제거해야 한다. 불가능한 것이 계산된 (방문된) 상태는 bool 타입의 dp 배열을 통해 검사하여 제거할 수 있다. 경우의 수 탐색은 재귀 호출로 구현된 dfs로 이루어진다. 시행착오 처음에는 dp의 기준을 dp[현재 idx]..