오블완21 [코테연습] 3243. Shortest Distance After Road Addition Queries I https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i/description/?envType=daily-question&envId=2024-11-27 문제 타입:그래프 이론최단 거리 계산쿼리 처리문제 분석:주어진 노드와 간선들로 이루어진 그래프에서 도로를 추가하는 여러 쿼리가 주어집니다.각 쿼리마다 새로운 도로를 추가하고, 노드 0에서부터 다른 모든 노드로의 최단 거리를 계산해야 합니다.쿼리마다 도로 추가 후 그래프의 변화를 반영하여 빠르게 최단 거리를 구하는 것이 핵심입니다.문제의 본질은 도로 추가에 따라 동적으로 변화하는 그래프에서 효율적으로 최단 거리를 업데이트하는 방법을 찾는 것입니다.문제 풀이:그래프 초기화: 각.. 2024. 11. 27. [코테연습] 2924. Find Champion II 문제 타입그래프 탐색 문제**Directed Acyclic Graph (DAG)**를 다루는 문제로, 간선을 따라 각 노드의 관계를 분석해야 함.특정 조건을 만족하는 "유일한 노드(챔피언)"를 판별하는 문제.조건 기반 유일성 판별주어진 그래프에서 노드 간 관계를 통해 조건을 만족하는 유일한 노드를 찾음.문제 분석그래프 특성n개의 팀(노드)과 edges 배열(간선)이 주어짐.간선 [u, v]는 u가 v를 이겼다는 것을 나타냄(방향성 존재).그래프는 사이클이 없는 DAG임.챔피언 조건그래프의 "챔피언"은 패배한 적이 없는 노드여야 함.이 노드는 edges의 loser로 등장하지 않아야 함.그래프에 "유일한 챔피언"이 존재해야 함."무패 상태"인 노드가 여러 개라면 챔피언은 존재하지 않음(-1 반환).결과 반.. 2024. 11. 26. [코테연습] 773. Sliding Puzzle https://leetcode.com/problems/sliding-puzzle/description/?envType=daily-question&envId=2024-11-25문제 타입그래프 탐색 (BFS)상태 공간 탐색퍼즐 문제문제 분석주어진 2x3 슬라이딩 퍼즐에서 숫자 '0'은 빈 칸을 나타내며, 목표는 퍼즐의 초기 상태를 '123450' 형태로 바꾸는 것입니다.BFS를 사용해 최단 경로 탐색 문제로 접근해야 합니다.각 상태에서 이동 가능한 위치로 빈 칸을 이동시키며 목표 상태에 도달하기 위한 최소 이동 횟수를 찾아야 합니다.문제 풀이초기 상태를 문자열로 변환하여 큐에 저장하고, BFS로 탐색을 진행합니다.각 노드에서는 '0'이 이동할 수 있는 위치를 계산하여 새로운 퍼즐 상태를 만듭니다.새로운 상태.. 2024. 11. 25. [코테연습] 1975. Maximum Matrix Sum 문제타입Greedy AlgorithmMatrix ManipulationMathematics문제분석주어진 행렬에서 각 행과 열을 적어도 한 번은 뒤집을 수 있는 조건에서, 행렬의 모든 값을 더한 합을 최대로 만드는 것이 목표.중요한 관찰:행 또는 열을 뒤집으면 그 열 또는 행의 값들이 부호가 바뀐다.뒤집는 횟수는 제한이 없으므로 부호 전환은 자유롭게 이루어질 수 있다.행렬 내 음수의 개수와 최소 절대값 요소가 결과에 영향을 준다.핵심 전략:음수의 개수가 짝수이면 모든 음수를 양수로 바꿀 수 있다.음수의 개수가 홀수이면 최소 절대값을 갖는 요소 하나를 양수로 만들지 못해 음수로 남긴다.문제풀이행렬 절대값의 합 계산:행렬의 모든 값을 양수로 간주하고 합을 계산한다.음수 개수 파악:행렬 내 음수의 개수를 세어 .. 2024. 11. 24. 이전 1 2 3 4 ··· 6 다음