백준 17835번 면접보는 승범이네
백준 17835번 면접보는 승범이네 풀이. 가상 정점에서 면접장들을 0거리로 연결해 역방향 다익스트라 한 번으로 각 도시의 최단 거리를 구한다.
모든 태그
주제
#boj
18편의 기록
-
-
백준 2261번 가장 가까운 두 점
백준 2261번 가장 가까운 두 점 풀이. x좌표 스위핑과 y좌표 기준 set을 이용해 후보 점만 검사하며 최단 거리를 갱신한다.
-
백준 1062번 가르침
백준 1062번 가르침 풀이. 배운 알파벳과 단어 구성을 비트마스크로 표현해 읽을 수 있는 단어 수를 최대화한다.
-
백준 10986번 나머지 합
백준 10986번 나머지 합 풀이. 누적합의 나머지가 같은 두 지점을 고르면 구간 합이 M으로 나누어떨어진다는 성질을 이용한다.
-
백준 11444번 피보나치 수 6
백준 11444번 피보나치 수 6 풀이. 행렬 거듭제곱을 분할 정복으로 계산해 매우 큰 n번째 피보나치 수를 빠르게 구한다.
-
백준 13489번 Vještica
백준 13489번 Vještica 풀이. 단어 집합을 비트마스크로 나누고 공통 prefix를 공유하는 Trie 최소 노드 수를 DP로 계산한다.
-
백준 13711번 LCS 4
백준 13711번 LCS 4 풀이. 한 수열의 위치 정보를 기준으로 다른 수열을 인덱스 배열로 바꾸고 LIS로 LCS 길이를 구한다.
-
백준 1588번 수열
백준 1588번 수열 풀이. 3분할 재귀 구조를 이용해 큰 수열을 직접 만들지 않고 특정 구간의 1, 2, 3 개수를 계산한다.
-
백준 17297번 Messi Gimossi
백준 17297번 Messi Gimossi 풀이. 피보나치처럼 이어지는 문자열 길이를 이용해 M번째 문자가 어느 이전 문자열에 속하는지 줄여 간다.
-
백준 23741번 야바위 게임
백준 23741번 야바위 게임 풀이. 정점에 홀수 번 또는 짝수 번 이동해 도착했는지만 구분해 여러 번 간선을 타는 상태를 압축한다.
-
백준 24229번 모두싸인 출근길
백준 24229번 모두싸인 출근길 풀이. 겹치는 판자를 정렬 후 병합하고, 이어진 구간을 이용해 갈 수 있는 최종 위치를 계산한다.
-
백준 25949번 Jar Game
백준 25949번 Jar Game 풀이. 세 항아리의 남은 조약돌과 현재 턴을 상태로 정의해 게임 DP로 승패를 판정한다.
-
백준 25953번 템포럴 그래프
백준 25953번 템포럴 그래프 풀이. 시간 T마다 가능한 간선 완화를 한 번씩만 적용하도록 시간별 dist 배열을 분리해 관리한다.
-
백준 2629번 양팔저울
백준 2629번 양팔저울 풀이. 추를 왼쪽과 오른쪽에 놓는 경우를 모두 고려해 음수와 양수 무게 상태를 DP로 만든다.
-
백준 27066번 나무 블럭 게임
백준 27066번 나무 블럭 게임 풀이. 정렬 후 가장 큰 블록을 포함하는 경우와 나머지를 합치는 경우를 비교해 최대 점수를 구한다.
-
백준 27068번 이미지 보정 작업
백준 27068번 이미지 보정 작업 풀이. 선명도 차이의 허용값을 이분 탐색하고 BFS로 보정해야 하는 구역을 판정한다.
-
백준 9370번 미확인 도착지
백준 9370번 미확인 도착지 풀이. 다익스트라로 특정 간선을 지나는 최단 경로가 존재하는 후보 목적지만 걸러낸다.
-
백준 9694번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다
백준 9694번 풀이. 최단거리 갱신 시 이전 노드를 함께 저장해 목적지까지의 최단 경로를 복원한다.