백준 17835번 면접보는 승범이네
면접장들을 거리 0으로 잇는 가상 정점에서 역방향 다익스트라 한 번 돌리기, long long 필요
모든 태그
주제
#boj
글 18개
-
-
백준 2261번 가장 가까운 두 점
x좌표로 정렬해 스위핑하며, y좌표 기준 set에서 현재 최단 거리 안에 드는 후보 점만 비교하는 방법
-
백준 1062번 가르침
배운 글자와 단어를 비트마스크로 표현해 읽을 수 있는 단어 수를 최대로 만드는 조합 탐색
-
백준 10986번 나머지 합
누적합을 M으로 나눈 나머지가 같은 두 지점을 고르면 구간 합이 나누어떨어진다는 성질, 오버플로 주의
-
백준 11444번 피보나치 수 6
피보나치 점화식을 행렬 곱으로 바꾸고 분할 정복 거듭제곱으로 O(log n)에 구하기
-
백준 13489번 Vještica
단어 집합을 비트마스크로 나누고 공통 prefix를 최대한 겹쳐 Trie 노드 수를 최소로 만드는 DP
-
백준 13711번 LCS 4
첫 수열의 위치로 두 번째 수열을 바꿔 쓰면 LCS가 O(N log N) LIS로 바뀌는 원리
-
백준 1588번 수열
3분할 재귀 구조로 수열을 만들지 않고 특정 구간의 1, 2, 3 개수를 계산하는 분할 정복
-
백준 17297번 Messi Gimossi
messi(N-1)과 messi(N-2)를 이어 붙인 길이를 이용해 M번째 글자가 속한 쪽으로 범위 좁히기
-
백준 23741번 야바위 게임
정점에 홀수 번 이동해 왔는지 짝수 번 이동해 왔는지만 구분해 반복 이동을 압축하는 BFS
-
백준 24229번 모두싸인 출근길
판자를 정렬하고 겹치는 판자를 이어 붙인 구간으로 갈 수 있는 최종 위치 계산하기
-
백준 25949번 Jar Game
세 항아리에 남은 조약돌 수와 현재 턴을 상태로 둔 게임 DP로 승패 판정하기
-
백준 25953번 템포럴 그래프
시각 T마다 간선 완화를 한 번만 하도록 시각별 dist 배열을 따로 두는 벨만 포드 변형
-
백준 2629번 양팔저울
추를 구슬 쪽과 반대쪽에 놓는 경우를 모두 고려해 음수 무게까지 상태로 두는 DP
-
백준 27066번 나무 블럭 게임
정렬 뒤 가장 큰 블럭을 남기는 경우와 나머지를 합치는 경우를 비교해 최대 점수 구하기
-
백준 27068번 이미지 보정 작업
허용할 선명도 차이를 이분 탐색하고 BFS로 보정할 구역을 판정하는 매개 변수 탐색
-
백준 9370번 미확인 도착지
s-g-h-e 경로 길이가 s-e 최단 거리와 같은지로 특정 간선을 지나는 목적지만 거르기
-
백준 9694번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다
최단 거리가 갱신될 때 이전 노드를 기록해 목적지까지의 경로를 복원하는 다익스트라