전체 글

문제 링크 : https://www.acmicpc.net/problem/1854 이 문제는 시작 정점부터 각각의 정점까지의 최단 거리를 찾는 다익스트라 알고리즘을 변형한 문제이다.단순히 최단 거리가 아닌 k번째 최단 경로를 구해야 한다.일반적으로 다익스트라 알고리즘은 각 정점까지 최단거리만을 저장하는 배열을 가지고 있는데이 문제를 해결하기 위해서는 각 정점까지의 거리 중 k번째로 짧은 거리까지 저장할 수 있는 자료구조가 필요하다. 여기서 PriorityQueue를 사용하면 매번 따로 처리해주지 않아도편하게 k번째 최단거리를 구할 수 있다. 일반적인 다익스트라 알고리즘 문제에서는 인접 리스트를 구현해서 푸는 것이 더 편하지만이 문제를 해결하기 위해서는 이런 인접 행렬을 이용해야 한다.arr[1][2] = ..

데이터베이스를 어떻게 설계하고 쿼리를 어떻게 작성하느냐에 따라병목현상이 발생하여 소프트웨어의 성능이 저하될 수 있다.데이터베이스를 최적화하는 방법을 자세히 소개하는 글이 있어 이 글을 보며 정리해 봤다. 해당 포스트 링크 11 Database Optimization TechniquesDatabase often becomes the bottleneck in software performance. Having an optimized database is essential for high performing systems. Here…danielfoo.medium.com  인덱싱 (Indexing)1. 인덱스 만들기인덱스는 빠른 조회 메커니즘을 제공하는 데이터 구조로, 쿼리 성능을 크게 향상시킨다.인덱스는 DB..

문제 링크 : https://www.acmicpc.net/problem/1753 이 문제는 다익스트라 알고리즘을 사용할 줄 아는지 묻는 문제이다.따라서 다익스트라 알고리즘을 코드로 구현만 해주면 된다. 간단하게 다익스트라 알고리즘을 알아보자. 만약 위와 같은 모양의 그래프가 있다고 가정해 보자.그래프 문제에서 가중치가 있는 간선을 다룰 때는 인접 리스트를 표현할 때클래스를 하나 생성하여 다음 정점과 해당 정점까지의 거리를 표현할 수 있다. 인접 리스트로 가중치가 있는 그래프를 표현한다면위와 같이 표현할 수 있을 것이다. 이제 다익스트라 알고리즘을 시작하기 전에시작 정점에서 각각의 정점까지의 거리를 나타내는 dist 배열과PriorityQueue인 pq를 초기화한다.이때 (정점, 시작정점부터 해당 정점까지..

문제 링크 : https://www.acmicpc.net/problem/1948 이 문제는 2가지를 구해야 하는 문제이다.첫 번째는 단순 위상정렬을 통해 도착지점까지 가장 오래 걸리는 경우가 몇인지를 구하면 되기 때문에비교적 간단하다. 두 번째가 이 문제의 핵심인데 가장 먼 거리를 이동하는 루트에 있는 도로의 개수를 구하는 문제이다.이것은 역방향 인접 그래프를 통해 해결할 수 있다. 우선 가장 기본이 되는 정방향 인접그래프를 구현한다.이때 노드와 노드 사이의 거리도 구해야 하기 때문에 새로운 클래스인Node 클래스를 만들어 목표 노드와 해당 노드까지의 거리를 나타내고이를 2차원 리스트에 저장하면 된다. 위의 정방향 인접 그래프를 위상정렬 알고리즘을 통해 구하면 위와 같이 2번 노드부터 7번 노드까지 임계..