백준 17835번 면접보는 승범이네
면접장들을 거리 0으로 잇는 가상 정점에서 역방향 다익스트라 한 번 돌리기, long long 필요
모든 태그
주제
#ps
글 232개
-
-
2022 SKKU 프로그래밍 대회 in 소프트의 밤
10월 SKKU 대회 4솔 후기와 A~F 문제별 풀이 아이디어, 내년 5솔·10등 안 목표
-
2022 성균관대학교 프로그래밍 경진대회
싸지방에서 치른 첫 프로그래밍 대회, 세그먼트 트리로 짰다가 알고 보니 누적합이었던 문제
-
그래프 최단경로 알고리즘 정리
다익스트라, 벨만 포드, 플로이드 워셜의 사용 조건과 시간 복잡도, 음의 간선과 반복문 순서 같은 주의점
-
백준 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번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다
최단 거리가 갱신될 때 이전 노드를 기록해 목적지까지의 경로를 복원하는 다익스트라
-
비트마스크
AND, OR, XOR, shift와 원소 추가·삭제·토글, 부분집합 순회처럼 PS에서 자주 쓰는 비트 연산
-
백준 25406번 식사 계획 세우기
과반수를 넘는 음식이 있으면 먼저 먹고 아니면 가장 앞 번호를 먹는 규칙을 set과 우선순위 큐로 처리하기
-
백준 25402번 트리와 쿼리
쿼리마다 선택된 노드끼리만 합치고 컴포넌트 크기로 쌍의 수 계산하기, 필요한 곳만 초기화
-
프로그래머스 스킬체크 레벨 4
이미지로 남긴 프로그래머스 스킬체크 레벨 4 응시 결과와 짧은 소감
-
백준 2287번 모노디지털 표현
숫자를 i개, j개 써서 만든 값끼리 사칙연산으로 합쳐 i+j개의 값 집합을 만드는 DP
-
백준 19608번 Searching for Strings
슬라이딩 윈도우의 알파벳 개수를 비교하고 해시로 중복을 걸러 애너그램 부분 문자열 세기
-
백준 17228번 아름다운 만영로
트리를 DFS로 내려가며 경로 문자열의 롤링 해시를 갱신해 패턴과 같은 경로 수 세기
-
백준 3033번 가장 긴 문자열
롤링 해시와 이분 탐색으로 두 번 이상 나오는 부분 문자열의 최대 길이 찾기
-
백준 6206번 Milk Patterns
정수 수열에 롤링 해시를 적용해 K번 이상 나오는 가장 긴 패턴 찾기, 충돌 시 직접 비교
-
백준 24525번 SKK 문자열
S는 2, K는 -1로 바꾼 누적합에서 같은 값이 나오는 가장 먼 두 지점 찾기
-
백준 11585번 속타는 저녁 메뉴
원형 문자열을 두 번 이어 붙인 뒤 KMP로 일치하는 회전 수를 세어 확률로 바꾸기
-
백준 4354번 문자열 제곱
KMP 실패 함수의 마지막 값으로 반복 단위 길이를 구해 문자열이 몇 번 반복되는지 판정하기
-
백준 13504번 XOR 합
누적 XOR 값을 Trie에 넣고 각 값과 XOR이 최대가 되는 짝을 찾아 부분 수열 XOR 최댓값 구하기
-
백준 13710번 XOR 합 3
prefix XOR 성질과 비트별 1의 개수 × 0의 개수로 모든 부분 수열 XOR 합 구하기
-
백준 2830번 행성 X3
비트마다 1의 개수 × 0의 개수를 곱해 모든 쌍의 XOR 합 구하기
-
백준 10464번 XOR
앞에서부터의 XOR 값이 4 주기로 반복되는 성질과 prefix XOR로 구간 XOR을 바로 구하기
-
백준 16903번 수열과 쿼리 20
0과 1만 있는 Trie에 수를 넣고 빼며, 높은 비트부터 반대 비트를 골라 XOR 최댓값 찾기
-
백준 5467번 Type Printer
Trie를 얕은 쪽부터 출력하고 가장 긴 단어를 마지막에 남겨 백스페이스 횟수 줄이기
-
백준 3080번 아름다운 이름
Trie 노드마다 자식 수의 팩토리얼을 곱해 이름 배열 수 구하기, 메모리 초과와 씨름한 기록
-
백준 5446번 용량 부족
지울 파일과 남길 파일을 Trie에 표시해 한 번에 지울 수 있는 가장 높은 경로부터 지우기
-
백준 19585번 전설
색상은 Trie, 닉네임은 set에 넣고 쿼리를 두 부분으로 나눌 수 있는지 판정하기
-
백준 16934번 게임 닉네임
Trie에 닉네임을 넣다가 처음 새로 생기는 접두사까지 출력하고, 같은 닉네임은 번호를 붙이기
-
백준 5670번 휴대폰 자판
단어가 끝나거나 자식이 둘 이상인 Trie 노드에서만 입력이 필요하다는 점으로 평균 입력 수 구하기
-
백준 1086번 박성원
고른 숫자 집합과 현재 나머지를 상태로 두고, 큰 수 대신 나머지만 이어 붙이는 비트마스크 DP
-
백준 2618번 경찰차
두 경찰차가 마지막으로 맡은 사건 번호를 상태로 둔 DP와 어느 차가 맡았는지 역추적하기
-
백준 11689번 GCD(n, k) = 1
소인수분해로 오일러 피 함수를 계산해 n 이하에서 n과 서로소인 수 세기, √n까지만 나누기
-
백준 24524번 아름다운 문자열
목표 문자열의 각 글자가 몇 개 진행됐는지 세며 순서대로 완성할 수 있는 개수 구하기
-
백준 24526번 전화 돌리기
그래프를 뒤집고 진입 차수가 0인 노드를 지워 나가 사이클에 닿지 않는 노드 세기
-
백준 24527번 이상한 나라의 갈톤보드
구간 업데이트를 lazy 세그먼트 트리와 imos 차분 배열 두 가지로 풀고 도착 구간 계산하기
-
백준 16563번 어려운 소인수분해
에라토스테네스의 체로 각 수의 가장 작은 소인수를 저장해 여러 수를 빠르게 소인수분해하기
-
백준 2168번 타일 위의 대각선
가로 + 세로 - 최대공약수로 대각선이 지나는 타일 수 계산하기
-
백준 2487번 섞기 순열
순열을 사이클로 나누고 사이클 길이의 최소공배수로 원래대로 돌아오는 시점 구하기
-
백준 2981번 검문
나머지가 모두 같다는 조건을 이웃한 수 차이의 최대공약수와 그 약수 문제로 바꾸기
-
백준 16637번 괄호 추가하기
괄호가 겹치지 않는 모든 배치를 재귀로 만들고 식을 앞에서부터 계산하는 완전 탐색
-
백준 15824번 너 봄에는 캡사이신이 맛있단다
정렬 뒤 각 원소가 최댓값으로 2^i번, 최솟값으로 2^(n-1-i)번 등장한다는 점을 이용한 합 계산
-
백준 1014번 컨닝
윗줄의 앉은 상태를 비트마스크로 두고 행 단위로 내려가며 최대 인원을 메모이제이션하는 DP
-
백준 22871번 징검다리 건너기 (large)
중간 돌을 거치는 비용 중 큰 값을 다시 최소로 만드는 DP, int 범위 주의
-
백준 1700번 멀티탭 스케줄링
멀티탭이 가득 찼을 때 가장 늦게 다시 쓰이거나 다시 안 쓰이는 기기를 뽑는 그리디
-
백준 23797번 개구리
K로 끝난 개구리와 P로 끝난 개구리 수를 세며 합쳐지는 규칙으로 필요한 최대 마리 수 구하기
-
백준 11097번 도시 계획
SCC마다 사이클 하나를 만들고 SCC 사이를 잇되, 다른 경로로 대신할 수 있는 간선은 빼고 출력하기
-
백준 2152번 여행 계획 세우기
SCC로 압축한 그래프에서 시작점에서 닿는 컴포넌트만 따라가며 방문 도시 수 최대화하기
-
백준 3977번 축구 전술
SCC를 구해 진입 차수가 0인 SCC가 하나뿐일 때만 그 안의 노드를 시작 전술로 출력하기
-
백준 4013번 ATM
SCC로 압축한 DAG에서 시작 SCC에서 닿는 경로만 따라가며 최대 현금을 구하는 DP
-
백준 6543번 그래프의 싱크
SCC로 압축한 그래프에서 나가는 간선이 없는 컴포넌트의 노드를 모두 출력하기
-
백준 1199번 오일러 회로
모든 정점의 차수가 짝수인지 확인하고 Hierholzer 알고리즘으로 간선을 한 번씩 쓰는 회로 만들기
-
백준 1948번 임계경로
위상 정렬로 최장 도착 시간을 구한 뒤 역방향으로 따라가며 임계 경로 간선 세기
-
백준 2637번 장난감 조립
위상 정렬 순서로 중간 부품의 기본 부품 필요량을 곱해 누적하기, 역추적으로 난 메모리 초과
-
백준 2848번 알고스팟어
이웃한 단어의 첫 차이로 알파벳 순서 간선을 만들고 위상 정렬로 모순과 여러 답 판정하기
-
백준 3665번 최종 순위
기존 순위로 모든 쌍에 방향 간선을 만들고 바뀐 쌍만 뒤집어 위상 정렬로 최종 순위 구하기
-
백준 1005번 ACM Craft
건물 선행 관계를 위상 정렬로 풀어 목표 건물의 최소 완성 시간 구하기, 전역 배열 초기화 실수까지
-
백준 1516번 게임 개발
위상 정렬 순서대로 선행 건물 완료 시간 중 가장 늦은 값에 자기 건설 시간을 더하기
-
백준 1766번 문제집
진입 차수가 0인 문제를 최소 힙에 넣어 번호가 작은 문제부터 푸는 위상 정렬
-
백준 2623번 음악프로그램
DFS 후 역순으로 출력하는 위상 정렬과 방문 중 상태로 사이클 찾기
-
백준 1647번 도시 분할 계획
MST를 만들다 간선이 N-2개가 되면 멈춰 가장 비싼 간선을 빼고 마을을 둘로 나누기
-
백준 1944번 복제 로봇
시작점과 열쇠 사이 최단 거리를 BFS로 구해 간선으로 만들고 MST로 모두 잇기
-
백준 2887번 행성 터널
x, y, z 좌표별로 정렬해 이웃한 행성 사이 간선만 후보로 두는 MST
-
백준 4343번 Arctic Network
위성 채널 수만큼 연결을 건너뛰고 MST에서 마지막으로 고른 간선 비용을 답으로 내기
-
백준 9373번 복도 뚫기
양쪽 벽과 센서를 정점으로 짧은 간격부터 이어 두 벽이 연결되는 순간의 거리 찾기
-
백준 18185번 라면 사기
1개 3원, 2개 5원, 3개 7원이라는 단가 차이로 앞쪽 공장과 묶어 사는 순서를 정하는 그리디
-
백준 1602번 도망자 원숭이
지연 시간이 짧은 도시부터 경유지로 허용하며 최단 거리와 경로상 최대 지연을 함께 갱신하기
-
백준 1613번 역사
플로이드 워셜로 사건 사이 도달 여부를 구해 앞뒤 관계를 판단하고 연결되지 않은 경우 구분하기
-
백준 2610번 회의준비
컴포넌트를 나누고 플로이드 워셜로 그룹마다 최대 전달 시간이 가장 작은 대표 고르기
-
백준 11657번 타임머신
음의 간선 때문에 다익스트라 대신 벨만 포드로 최단 거리와 음수 사이클을 판정, long long 필요
-
백준 1219번 오민식의 고민
간선에서 비용을 빼고 도시에서 수익을 더하는 벨만 포드, 도착지까지 이어지는 양수 사이클 판정
-
백준 1738번 골목길
벨만 포드로 찾은 양의 사이클 중 실제로 N까지 이어지는 것만 골라내고 경로 복원하기
-
백준 1162번 도로포장
포장한 도로 수를 상태로 둔 다익스트라, 방문 여부 대신 거리 비교로 오래된 항목을 거르는 것이 핵심
-
백준 10217번 KCM Travel
도로포장처럼 사용한 비용을 상태로 두고 비용별 최소 소요 시간을 기록하는 최단 경로
-
백준 2211번 네트워크 복구
MST처럼 보이지만 1번 기준 다익스트라에서 각 노드의 부모 간선만 남기면 되는 문제
-
백준 5719번 거의 최단 경로
다익스트라 후 도착점부터 역추적해 모든 최단 경로 간선을 지우고 다시 다익스트라 돌리기
-
백준 10473번 인간 대포
시작점, 대포, 목적지를 완전 그래프로 만들고 걷기와 대포 중 빠른 쪽으로 간선을 둔 다익스트라
-
백준 15422번 Bumped!
티켓을 쓰기 전과 후로 그래프를 두 겹 만들고 비용 0인 간선으로 이은 다익스트라
-
백준 17435번 합성함수와 쿼리
f를 1, 2, 4, 8번 적용한 결과를 sparse table로 저장해 합성함수를 로그 시간에 계산하기
-
백준 2213번 트리의 독립집합
부모 선택 여부에 따라 현재 노드를 고를지 나누는 트리 DP와 선택된 노드 복원
-
백준 2248번 이진수 찾기
자릿수와 1의 개수 제한별 경우의 수를 DP로 세고 앞자리부터 I번째 수를 만들어 가기
-
백준 2533번 사회망 서비스
부모가 얼리어답터인지에 따라 현재 노드의 선택지를 나누는 트리 DP
-
백준 17131번 여우가 정보섬에 올라온 이유
왼쪽과 오른쪽으로 한 번씩 스위핑하며 자기보다 높은 별 수를 세어 곱하기, 같은 x좌표 처리 주의
-
백준 13925번 수열과 쿼리 13
더하기, 곱하기, 대입 쿼리를 ax+b 형태의 lazy 값 하나로 합성하는 세그먼트 트리
-
백준 5419번 북서풍
x좌표로 정렬하고 압축한 y좌표를 세그먼트 트리에 기록해 북서풍 조건을 만족하는 쌍 세기
-
백준 13537번 수열과 쿼리 1
합병 정렬의 중간 결과를 저장한 머지 소트 트리에서 upper_bound로 K보다 큰 원소 수 세기
-
백준 7469번 K번째 수
머지 소트 트리로 구간에서 어떤 값 이하인 수의 개수를 구하고 이분 탐색으로 K번째 수 찾기
-
백준 1395번 스위치
켜진 스위치 수와 반전 횟수를 lazy로 저장하고 홀수일 때만 뒤집는 구간 토글
-
백준 10999번 구간 합 구하기 2
구간 업데이트를 바로 반영하지 않고 표시만 해 두었다가 방문할 때 밀어 넣는 lazy propagation
-
백준 12844번 XOR
결합·교환 법칙이 성립하는 XOR로 만든 세그먼트 트리와 lazy 전파, += 대신 ^=를 써야 하는 이유
-
백준 5676번 음주 코딩
값을 1, 0, -1로만 바꿔 곱하는 세그먼트 트리로 구간 곱의 부호 판정하기, EOF까지 입력받기
-
백준 1572번 중앙값
값 범위로 만든 세그먼트 트리에서 슬라이딩 윈도우의 K번째 값을 찾아 중앙값 합 구하기
-
백준 2104번 부분배열 고르기
구간 최솟값의 위치를 기준으로 좌우를 나누는 분할 정복, 히스토그램 문제와 같은 구조
-
백준 2517번 달리기
실력을 좌표 압축하고 세그먼트 트리로 앞선 선수 중 자기보다 강한 사람 수 세기
-
백준 7578번 공장
A열 위치를 기계 번호로 기록하고 세그먼트 트리로 교차하는 연결선 수 세기, int 범위 주의
-
백준 2243번 사탕상자
맛별 사탕 개수 합을 세그먼트 트리에 두고 순위를 따라 내려가며 원하는 사탕 찾기
-
백준 9345번 디지털 비디오 디스크(DVDs)
구간 최솟값과 최댓값이 L과 R과 같은지 세그먼트 트리로 확인해 DVD가 제자리인지 판정하기
-
백준 3653번 영화 수집
배열 앞쪽에 빈 자리를 비워 두고 DVD를 맨 위로 옮기며 세그먼트 트리로 위에 쌓인 개수 세기
-
백준 1280번 나무 심기
구간의 나무 개수와 거리 합을 세그먼트 트리에 두고 새 나무를 심는 비용을 바로 계산하기
-
백준 3006번 터보소트
버블 소트 풀이에서 쿼리 순서만 1, N, 2, N-1로 바꿔 세그먼트 트리로 이동 횟수 세기
-
백준 1517번 버블 소트
실제로 버블 정렬하지 않고 세그먼트 트리로 앞쪽의 정렬되지 않은 원소 수를 세어 swap 횟수 구하기
-
백준 6549번 히스토그램에서 가장 큰 직사각형
가장 낮은 막대를 기준으로 구간을 나누는 분할 정복, 최솟값 위치는 세그먼트 트리로 찾기
-
백준 11505번 구간 곱 구하기
구간 합 대신 구간 곱을 저장하는 세그먼트 트리, 범위 밖이면 1을 반환하고 리프부터 다시 곱하는 업데이트
-
백준 12837번 가계부 (Hard)
값을 바꾸는 대신 더하는 쿼리라는 점만 주의하면 되는 구간 합 세그먼트 트리
-
백준 2357번 최솟값과 최댓값
구간 최솟값 트리와 최댓값 트리를 따로 만들어 RMQ 질의에 답하기
-
백준 10775번 공항
남은 가장 큰 게이트에 도킹하는 그리디를 유니온 파인드로 빠르게 찾는 방법
-
백준 17398번 통신망 분할
끊길 간선을 빼고 먼저 합친 뒤 역순으로 다시 이으며 분할 비용을 더하기, long long 필요
-
백준 2042번 구간 합 구하기
구간 합 질의와 값 변경을 모두 O(log N)에 처리하는 세그먼트 트리 기본 구현
-
백준 9938번 방 청소
연결된 서랍 집합의 남은 자리를 루트에 저장하는 유니온 파인드로 술병 보관 여부 판단하기
-
백준 11085번 군사 이동
수용량이 큰 간선부터 이어 붙이다 출발지와 도착지가 연결되는 순간의 수용량을 찾는 유니온 파인드
-
백준 14868번 문명
BFS로 문명을 넓히며 맞닿은 문명을 유니온 파인드로 합쳐 모두 이어지는 해 찾기
-
백준 3197번 백조의 호수
녹는 물을 BFS로 퍼뜨리며 이어진 물을 유니온 파인드로 묶어 백조가 만나는 날 찾기
-
백준 14003번 가장 긴 증가하는 부분 수열 5
O(N log N) LIS를 구하며 값이 갱신될 때마다 이전 원소를 기록해 실제 수열을 복원하는 방법
-
백준 10942번 팰린드롬?
양 끝 문자가 같고 안쪽 구간이 팰린드롬이면 전체도 팰린드롬이라는 점화식으로 여러 질의 처리
-
백준 1509번 팰린드롬 분할
팰린드롬 구간 판정 DP 위에 최소 분할 수 DP를 하나 더 쌓아 시간 초과 피하기
-
백준 2162번 선분 그룹
선분 교차 판정과 유니온 파인드를 합쳐 그룹 수와 가장 큰 그룹 크기 구하기
-
백준 2342번 Dance Dance Revolution
양발 위치와 진행 순서를 상태로 두고 최소 힘을 메모이제이션하는 DP
-
백준 17387번 선분 교차 2
CCW 부호와 끝점 대소 비교로 일반 교차와 일직선 위에서 겹치는 경우까지 판정하기
-
백준 7579번 앱
메모리 대신 비용을 인덱스로 두고 비용별 최대 확보 메모리를 저장하는 배낭 DP
-
백준 11049번 행렬 곱셈 순서
시작과 끝 행렬 구간을 상태로 두고 나누는 지점마다 곱셈 비용의 최솟값을 구하는 구간 DP
-
백준 17404번 RGB거리 2
첫 집의 색을 고정하고 마지막 집이 그 색과 겹치지 않게 하는 원형 RGB 거리 DP
-
백준 14464번 소가 길을 건너간 이유 4
닭이 도울 수 있는 소가 여럿이면 가장 먼저 건너기를 끝내는 소를 고르는 그리디 매칭
-
백준 16562번 친구비
친구비가 가장 싼 사람이 루트가 되도록 합치는 유니온 파인드로 집합별 최소 비용 더하기
-
백준 1717번 집합의 표현
부모 대신 루트를 저장하는 경로 압축 유니온 파인드의 union과 find 구현
-
백준 4195번 친구 네트워크
이름을 번호로 바꾸고 루트에 음수로 집합 크기를 저장하는 유니온 파인드
-
백준 1715번 카드 정렬하기
가장 작은 두 묶음을 계속 합치는 최소 힙 그리디, C++ priority_queue를 최소 힙으로 쓰는 방법
-
백준 2014번 소수의 곱
최소 힙에서 꺼낸 곱에 소수들을 다시 곱해 넣으며 중복과 int 범위를 관리하기
-
백준 2696번 중앙값 구하기
최대 힙과 최소 힙의 크기 균형을 유지하며 입력마다 중앙값 출력하기
-
백준 10649번 프리스비
고른 소 집합의 최대 안정도를 비트마스크 DP로 기록하고 새 소를 위나 아래에 놓는 경우 비교
-
백준 1176번 섞기
마지막으로 세운 학생과 지금까지 세운 학생 집합을 상태로 둔 비트마스크 DP, int 범위 초과 주의
-
백준 1029번 그림 교환
현재 소유자, 구매 가격, 거쳐 간 예술가 집합을 상태로 둔 비트마스크 DP와 문제를 잘못 읽은 실수
-
백준 1480번 보석 모으기
가방 번호, 현재 가방 무게, 담은 보석 집합을 상태로 둔 비트마스크 DP
-
백준 16991번 외판원 순회 3
좌표 사이 유클리드 거리를 비용으로 쓰는 비트마스크 TSP, 소수점 출력 주의
-
백준 2320번 끝말잇기
마지막 글자와 사용한 단어 집합을 상태로 둔 비트마스크 DP로 최고 점수 구하기
-
백준 1102번 발전소
켜진 발전소를 비트마스크로 두고 P개 이상 켜는 최소 비용을 메모이제이션하는 탑다운 DP
-
백준 3056번 007
배정한 미션을 비트마스크로 두고 요원 순서대로 최대 성공 확률을 구하는 DP
-
백준 1600번 말이 되고픈 원숭이
말처럼 뛴 횟수를 BFS 상태에 넣어 벽 부수고 이동하기처럼 푸는 격자 최단 거리
-
백준 2098번 외판원 순회
현재 도시와 방문한 도시 비트마스크를 상태로 둔 외판원 순회 DP
-
백준 14442번 벽 부수고 이동하기 2
지금까지 부순 벽의 수를 BFS 상태에 넣어 K번 이하로 부수는 최단 거리 구하기
-
백준 16933번 벽 부수고 이동하기 3
낮과 밤, 부순 벽 수, 기다린 횟수를 BFS 상태로 기록해 밤에는 벽 앞에서 기다리는 최단 경로
-
백준 9328번 열쇠
열쇠 상태가 바뀌면 막혔던 칸과 테두리를 다시 탐색하는 BFS, visited 초깃값을 -1로 두는 이유
-
백준 1194번 달이 차오른다, 가자.
가진 열쇠를 비트마스크로 기록해 같은 칸이라도 열쇠 상태가 다르면 다시 방문하는 BFS
-
백준 2001번 보석 줍기
가진 보석 상태를 비트마스크로 두고 같은 섬, 같은 상태의 재방문을 막는 탐색
-
백준 12094번 2048 (Hard)
한 방향 밀기만 구현하고 보드를 돌려 네 방향을 처리, 변화 없는 이동과 가망 없는 분기 가지치기
-
백준 1562번 계단 수
길이, 마지막 숫자, 지금까지 쓴 숫자 비트마스크를 상태로 0~9를 모두 쓰는 계단 수 세기
-
백준 1799번 비숍
흑백 칸을 나눠 놓을 자리를 절반으로 줄이고 대각선 점유를 기록하는 비숍 백트래킹
-
백준 2263번 트리의 순회
inorder와 postorder의 인덱스 범위만 넘기며 루트와 서브트리를 찾아 preorder 출력, 벡터 복사로 난 메모리 초과
-
백준 17136번 색종이 붙이기
크기별 5장 제한과 종이 범위를 확인하며 붙였다 떼는 백트래킹으로 최소 장수 찾기
-
백준 1182번 부분수열의 합
각 원소를 넣거나 빼는 2^N 경우를 모두 도는 백트래킹, 벡터를 참조로 넘기면 22배 빨라지는 이유
-
백준 1759번 암호 만들기
모음 1개 이상, 자음 2개 이상 조건을 세며 알파벳을 고르는 백트래킹
-
백준 1987번 알파벳
이미 쓴 알파벳을 기록하며 상하좌우로 가는 DFS 백트래킹으로 가장 긴 경로 찾기
-
백준 2096번 내려가기
직전 줄의 최댓값과 최솟값만 남기는 DP로 4MB 메모리 제한 통과하기
-
백준 2580번 스도쿠
행, 열, 3x3 칸에 쓴 숫자를 기록하며 빈칸을 채우는 백트래킹, 답은 한 번만 출력
-
백준 17071번 숨바꼭질 5
수빈이가 짝수·홀수 초에 도달하는 시간을 따로 기록해 움직이는 동생과 만나는 순간 판정하기
-
백준 2294번 동전 2
금액별 최소 동전 수를 저장하는 DP, INT_MAX에 1을 더해 INT_MIN이 된 실수
-
백준 1525번 퍼즐
퍼즐 상태를 문자열로 바꿔 map에 이동 횟수를 저장하는 BFS로 정답 상태까지의 최단 이동 찾기
-
백준 11967번 불켜기
불은 켜졌지만 아직 못 가는 방을 따로 기억했다가 길이 열리면 BFS에 넣기, 시작 방 불 켜기 주의
-
백준 16920 확장 게임
플레이어마다 큐를 따로 두고 각자 확장 거리만큼 번갈아 BFS를 돌려 점령 칸 세기
-
백준 4179번 불!
불이 번지는 시간을 먼저 BFS로 구하고 그보다 먼저 닿는 칸으로만 지훈이를 옮기기, 불이 없는 경우 주의
-
백준 5014번 스타트링크
건물 범위를 벗어나지 않게 위아래 층으로 BFS 해서 최소 버튼 횟수 구하기
-
백준 9466번 텀 프로젝트
선택 그래프를 DFS로 따라가며 사이클을 이루는 학생만 팀으로 세고 나머지 인원 구하기
-
백준 3015번 오아시스 재결합
같은 키가 연속된 사람 수를 함께 저장하는 스택으로 서로 볼 수 있는 쌍 세기
-
백준 2493번 탑
왼쪽의 더 높은 탑 후보를 스택으로 관리해 각 탑의 레이저를 받는 탑 찾기
-
백준 9251번 LCS
두 문자열의 접두사 쌍마다 최장 공통 부분 수열 길이를 저장하는 2차원 DP
-
백준 1918번 후위 표기식
연산자 우선순위와 괄호를 스택으로 처리해 중위 표기식을 후위 표기식으로 바꾸기
-
백준 1422번 숫자의 신
a+b와 b+a를 비교하는 정렬 기준으로 이어 붙이고, 가장 큰 수를 반복해 남은 자리를 채우기
-
백준 3482번 Labyrinth
칸 사이 경로가 하나뿐인 미궁을 트리로 보고 두 번의 BFS로 가장 먼 두 칸 사이 거리 구하기
-
백준 1167번 트리의 지름
아무 노드에서 가장 먼 노드를 찾고 거기서 다시 가장 먼 거리를 재는 두 번의 DFS가 맞는 이유
-
백준 2407번 조합
파스칼의 삼각형 점화식으로 큰 조합 값을 직접 계산하기
-
백준 9465번 스티커
두 줄 DP 테이블에 각 스티커를 골랐을 때의 최대 점수를 대각선 방향으로 누적하기
-
백준 12865번 평범한 배낭
무게별 최대 가치를 저장하는 DP 테이블로 완전 탐색 없이 푸는 0/1 배낭 문제
-
백준 12851번 숨바꼭질 2
같은 최단 시간으로 도착하는 경우도 큐에 넣어 최단 시간과 방법의 수를 함께 구하는 BFS
-
백준 13549번 숨바꼭질 3
비용 0인 순간이동을 먼저 처리하는 최단 경로, 우선순위 큐 대신 0-1 BFS로도 가능
-
백준 13913번 숨바꼭질 4
BFS로 최단 시간을 구하며 직전 위치를 함께 저장하고 도착점에서 경로를 거꾸로 따라가기
-
백준 17928번 오큰수
다음 큰 수 후보를 스택으로 관리해 각 원소의 오큰수를 O(N)에 찾기
-
백준 1011번 Fly me to the Alpha Centauri
1, 121, 12321처럼 제곱수를 기준으로 대칭인 이동 거리 패턴에서 최소 이동 횟수 구하기
-
백준 11404번 플로이드
거쳐 갈 노드를 가장 바깥 반복문에서 고정해야 하는 플로이드 워셜, 반복문 순서 주의
-
백준 11660번 구간 합 구하기 5
행과 열 방향으로 누적한 2차원 누적합에서 포함-배제로 직사각형 합 구하기
-
백준 1932번 정수 삼각형
왼쪽 위와 오른쪽 위 중 큰 합을 고르며 내려가는 정수 삼각형 DP
-
백준 9935번 문자열 폭발
글자를 스택에 쌓다가 끝부분이 폭발 문자열과 같으면 지워 한 번의 순회로 처리하기
-
백준 2206번 벽 부수고 이동하기
벽을 부쉈는지 여부를 BFS 상태에 넣어 한 번만 부수고 가는 최단 경로 찾기
-
백준 1504번 특정한 최단 경로
1→v1→v2→N과 1→v2→v1→N 중 짧은 쪽을 다익스트라 여러 번으로 비교하기
-
백준 1753번 최단경로
비용 기준 우선순위 큐 다익스트라, 일반 큐와 노드 번호 기준 정렬로 시간 초과가 났던 실수
-
백준 1629번 곱셈
지수를 반으로 나눠 제곱하는 분할 정복 거듭제곱과 모듈러 연산으로 O(log N) 계산
-
백준 11725번 트리의 부모 찾기
루트 1번에서 DFS 한 번으로 모든 노드의 부모를 함께 기록하기, 노드마다 탐색해 시간 초과가 난 첫 시도
-
백준 16953번 A → B
A에서 B로 가는 대신 B에서 끝자리 1을 지우고 2로 나누며 거꾸로 내려가는 풀이
-
백준 1107번 리모컨
0번부터 100만 번까지 갈 수 있는 채널을 모두 시도해 +/- 버튼 이동과 비교하는 완전 탐색
-
백준 10026번 적록색약
같은 색 영역을 BFS로 세고, R을 G로 바꾼 격자에서 한 번 더 세는 적록색약 시야 처리
-
백준 2178번 미로 탐색
한 칸씩 이동하며 거리를 1씩 더하는 기본 BFS 최단 경로
-
백준 1541번 잃어버린 괄호
처음 나온 마이너스 뒤의 수는 괄호로 묶어 모두 뺄 수 있다는 그리디
-
백준 9663번 N-Queen
퀸 위치를 1차원 배열로 두고 열과 대각선 충돌을 검사하는 백트래킹
-
백준 15649번 N과 M
방문 여부, 오름차순, 중복 제거 조건을 바꿔 가며 N과 M 시리즈를 하나의 백트래킹으로 풀기
-
백준 1012번 유기농 배추
이어진 배추 영역을 연결 요소로 보고 DFS가 새 영역을 찾을 때마다 지렁이 수 세기
-
백준 1074번 Z
10억 칸 배열을 만들지 않고 목표 좌표가 속한 사분면만 따라 내려가며 방문 순서 누적하기
-
백준 2579번 계단 오르기
세 계단 연속 금지와 마지막 계단 필수 조건을 두 가지 이전 상태로 처리하는 DP
-
백준 7576번 토마토
처음 익은 토마토를 모두 큐에 넣고 BFS로 날짜를 누적해 전체가 익는 날 구하기
-
백준 11724번 연결 요소의 개수
방문하지 않은 노드에서 탐색을 시작할 때마다 하나씩 세는 연결 요소, Python 재귀 깊이 제한 풀기
-
백준 11726번 2xn 타일링
마지막에 세로 타일 하나를 붙이는 경우와 가로 타일 두 개를 붙이는 경우를 더하는 점화식
-
백준 1764번 듣보잡
리스트 비교 대신 set 교집합으로 O(N)에 두 명단의 공통 이름 찾기
-
백준 11279번 최대 힙
최소 힙만 있는 heapq에 음수를 넣어 최대 힙처럼 쓰는 방법
-
백준 18870번 좌표 압축
정렬, 중복 제거, 딕셔너리 매핑으로 각 좌표보다 작은 서로 다른 좌표 수를 빠르게 구하기
-
백준 1018번 체스판 다시 칠하기
가능한 모든 8x8 영역에서 W 시작, B 시작 체스판과 비교해 다시 칠할 칸 수의 최솟값 찾기
-
백준 10989번 수 정렬하기 3
천만 개 입력을 정렬 대신 값 범위 1만짜리 카운팅 배열로 처리해 메모리 초과 피하기
-
백준 12015번 가장 긴 증가하는 부분 수열 2
길이별로 가장 작은 끝값을 유지하고 이분 탐색으로 갱신하는 O(N log N) LIS
-
백준 11053번 가장 긴 증가하는 부분 수열
각 원소를 끝으로 하는 LIS 길이를 앞의 원소들과 비교해 갱신하는 O(N²) DP와 그 한계
-
백준 1912번 연속합
누적합이 음수가 되면 다음 원소에서 새로 시작하는 카데인 알고리즘
-
백준 2293번 동전 1
동전을 하나씩 추가하며 금액별 경우의 수를 갱신하는 d2[i] = d1[i] + d2[i-v] 점화식
-
백준 11399번 ATM
인출 시간이 짧은 사람부터 줄을 세워 누적 대기 시간을 최소로 만드는 정렬 그리디
-
백준 2606번 바이러스
1번 컴퓨터와 연결된 노드를 DFS나 BFS로 세는 기본 그래프 탐색
-
백준 11047번 동전 0
동전 가치가 서로 배수일 때만 성립하는, 가장 큰 동전부터 쓰는 그리디
-
백준 2630번 색종이 만들기
종이를 넷으로 나눠 한 색이면 세고 아니면 다시 나누는 재귀 분할
-
백준 1992번 쿼드트리
이미지를 넷으로 나눠 모두 같은 값일 때만 압축하는 재귀 분할
-
백준 1697번 숨바꼭질
-1, +1, ×2 이동을 BFS로 탐색하며 각 위치까지 걸린 시간을 기록하기
-
백준 1260번 DFS와 BFS
재귀로 짠 DFS와 deque로 짠 BFS, 작은 번호부터 방문하는 순서 처리
-
백준 1149번 RGB거리
이전 집을 다른 색으로 칠한 최소 비용 중 작은 쪽을 고르는 RGB 거리 DP 점화식
-
백준 9095번 1, 2, 3 더하기
N에서 1, 2, 3을 빼 나가며 순서가 다른 경우까지 모두 세는 재귀
-
백준 1092번 배
가장 센 크레인이 가장 무거운 박스를 맡는 그리디, Python3에서는 시간 초과지만 PyPy3로는 통과
-
백준 1041번 주사위
마주 보지 않는 세 면 조합의 최솟값을 구하고 보이는 면 개수 규칙대로 더하기, int 범위 주의