PLOD

문제 상황도시들이 도로로 연결되어 있고, 매 도로에서 퍼레이드가 열릴 수 있다. 퍼레이드가 열리면 해당 도로를 사용할 수 없게 되는데, 이 때 최단 경로가 영향을 받는 정점쌍(s, t)의 개수를 각 도로별로 구하는 문제다.단순히 보면, 도로 하나씩 막고 다익스트라를 돌리면 될 것 같지만, 그렇게 하면 시간 초과가 발생할 수 있다.어떤 시도를 했는지첫 시도: 각 도로를 하나씩 제거하고 다익스트라를 수행한 뒤, 원래의 최단 경로보다 멀어진 정점들을 확인해 카운트하는 브루트포스 방식으로 구현했다.성공은 했지만 비효율적: Python에서 다익스트라를 M번 반복하는 방식은 입력 수가 많아질수록 매우 느려졌다.작성 코드# https://www.acmicpc.net/problem/16118import sys, hea..

공부한 내용 본인의 언어로 정리하기오늘은 백준 16118번 달빛 여우 문제를 풀며, 상태를 갖는 다익스트라 알고리즘을 공부했다.기본적인 다익스트라 알고리즘은 하나의 최단 거리만을 저장하지만, 이 문제에서 늑대는 이동 시 두 가지 속도 상태(빠름, 느림)를 반복하므로 각 노드에 대해 두 개의 거리 정보를 저장해야 한다.핵심은 다음과 같다:여우는 평범한 다익스트라를 사용한다.늑대는 "빠름 → 느림 → 빠름…"의 패턴을 따르므로, 각 상태에 따라 비용이 다르다.빠를 때는 거리의 절반(weight // 2)느릴 때는 거리의 두 배(weight * 2)늑대의 다익스트라는 distance[node][0 or 1] 구조를 통해 상태 전환을 관리하며 진행된다.또한, 정수 연산을 위해 모든 간선 거리를 2배 해주는 트릭..

1. 데이터베이스 락에서 비관적 락과 낙관적 락에 대해 설명해주세요.더보기1. 비관적 락 (Pessimistic Lock)개념: 트랜잭션에 의해 데이터 충돌이 발생할 가능성이 높다고 가정하고, 트랜잭션이 데이터를 수정하는 동안 다른 트랜잭션이 해당 데이터에 접근하지 못하게 하는 방식입니다.동작 원리: 트랜잭션이 데이터를 읽거나 수정하려 할 때, 미리 락을 걸어서 다른 트랜잭션이 그 데이터를 수정하지 못하게 합니다. 락이 해제될 때까지 해당 데이터에 대한 접근이 제한됩니다.장점: 충돌을 미리 방지하므로 데이터 무결성이 보장됩니다.단점: 락을 오래 유지하게 되면 성능 저하가 발생하고, 자원 경쟁이 심한 경우 데드락(교착 상태)이 발생할 수 있습니다.사용 예시: 은행 시스템처럼 여러 사용자가 동시에 동일한 데..