본문 바로가기

분류 전체보기

 (225)
[백준] 5014. 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 평소 많이 풀던 BFS 문제에서 4방향 탐색을 2방향 탐색으로 바꾸기만 하면 된다. 그런데 다음과 같은 치명적인 실수를 해서 틀렸다. BFS를 풀 때 다음과 같이 그래프 범위 밖을 벗어나거나 이미 방문했으면 continue해버렸다. while (!que.isEmpty()) { Integer num = que.poll(); // 도착한 경우 if (num == G) { System.out.println(map[..
준영속 상태에서의 지연 로딩 문제와 그 해결법인 OSIV 트랜잭션 범위의 영속성 컨텍스트 전략 스프링 컨테이너는 트랜잭션 범위의 영속성 컨텍스트 전략을 기본으로 사용한다. 이름 그대로 트랜잭션의 범위와 영속성 컨텍스트의 생존 범위가 같다는 뜻이다. 즉, 트랜잭션을 시작할 때 영속성 컨텍스트를 생성하고 트랜잭션이 끝날 때 영속성 컨텍스트를 종료한다. 그리고 같은 트랜잭션 안에서는 항상 같은 영속성 컨텍스트에 접근한다. 스프링 프레임워크를 사용하면 보통 비즈니스 로직을 시작하는 서비스 계층에서 @Transactional 어노테이션을 선언해서 트랜잭션을 시작한다. @Transactional 어노테이션이 있으면 해당 클래스의 메소드 호출시 메소드 실행 직전에 스프링의 트랜잭션 AOP가 먼저 동작한다. 트랜잭션 AOP는 대상 메소드를 호출하기 직전에 트랜잭션을 시작한다..
엔티티 조회 성능 최적화 xToOne 관계의 엔티티 조회 성능 최적화Order를 조회할 때 연관된 Member와 Delivery를 함께 조회한다고 가정하자. 이때 Order와 Member는 다대일 관계이고, Order와 Delivery는 일대일 관계이다.지연 로딩 사용으로 인한 N+1 문제지연 로딩으로 설정해두면, Order를 조회할 때 Member와 Delivery 테이블에는 조회 쿼리가 나가지 않고, 연관된 엔티티인 Member와 Delivery는 프록시 객체가 된다. 그리고 member.getUsername()과 같이 엔티티에 접근할 때, Member 테이블에 조회 쿼리가 나가게 되고, 해당 프록시 객체가 초기화된다.  따라서 만약 주문 정보(Order)를 조회하면서 회원 정보(Member)와 배송 정보(Delivery)를..
[백준] 1987. 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 www.acmicpc.net 처음에는 set을 사용해서 매 경우마다 set을 clone하고 새로운 알파벳을 넣어주는 식으로 풀었다. 그런데 시간초과가 났다. 아무래도 매번 컬렉션을 복제하는 것이 시간이 많이 소요되는 거 같다. 따라서 set이 아니라, 알파벳을 담는 일차원 배열을 두면 된다. 즉, visited[] 배열을 두어서 A를 방문했으면 visited[0] = true로 값을 넣어주는 식으로 하면 된다. ..
[백준] 11403. 경로 찾기 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 DFS와 플로이드 두 가지 방법으로 풀 수 있다. DFS로 푸는 방법은 다음과 같다. 각 정점을 시작으로 이동할 수 있는 다른 정점을 구한다. 이때 dfs를 사용한다. dfs의 결과로 visited[] 배열에 값이 채워지는데, 이때 true이면 이동할 수 있는 것이고, false이면 이동할 수 없는 것이다. 시간 복잡도는 각 정점을 시작으로 dfs를 시작하므로, O(N * (V + E))이다. import java..
[백준] 11724. 연결 요소의 개수 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 처음에는 dfs 부분을 다음과 같이 작성했다. private static void dfs(int start) { for (int i = start + 1; i
[백준] 2206. 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 도착점에 가장 빠르게 도착할 수 있는 최단 거리를 구하면 되므로, bfs를 사용하면 된다. 그런데 벽을 한 번 부술 수 있다는 것이 관건이다. 처음에는 다음과 같이 풀었다. Point에 x, y 위치와 지금까지 벽을 부순 적이 있는지 없는지를 의미하는 boolean destroy 변수를 정의했다. 그래프를 탐색하며 벽이 아니면 이동하고, 벽이면 지금까지 벽을 부순 적이 없..
Redis에 토큰 저장하기 Redis Redis는 디스크가 아닌 메모리에 데이터를 저장하는 인메모리 방식의 데이터베이스이다. * 메모리(RAM, Random Access Memory): 빠른 액세스를 위해 데이터를 임시로 저장하는 저장소이다. 메모리에 올라간 데이터는 컴퓨터 전원이 꺼지면 휘발된다. * 디스크(HDD, SSD): 데이터를 영구적으로 저장하는 저장소이다. 디스크에 저장되어 있는 데이터는 CPU가 처리하는 속도가 메모리보다 느리다. 그러나 저장할 수 있는 용량이 메모리보다 훨씬 크고, 전원이 꺼지더라도 저장된 데이터가 휘발되지 않는다. * 인메모리 데이터베이스: 디스크가 아닌 메모리에 데이터를 저장하는 데이터베이스이다. IMDB(In-Memory Database) 또는 MMDB(Main Memory DBMS)라고 한다..

티스토리툴바