백준 25406번 식사 계획 세우기
백준 25406번 식사 계획 세우기 풀이. 이전 음식과 과반수 조건을 만족하도록 set과 priority queue로 다음 음식 후보를 관리한다.
모든 태그
주제
#cpp
155편의 기록
-
-
백준 25402번 트리와 쿼리
백준 25402번 트리와 쿼리 풀이. 쿼리마다 선택된 노드끼리만 유니온하며 연결된 컴포넌트 크기로 가능한 쌍의 수를 계산한다.
-
프로그래머스 스킬체크 레벨 4
프로그래머스 스킬체크 레벨 4 응시 기록. 짧은 이미지 중심 후기와 당시의 소감을 남긴 글.
-
백준 2287번 모노디지털 표현
백준 2287번 모노디지털 표현 풀이. 같은 숫자를 i개 써서 만들 수 있는 값 집합을 사칙연산으로 확장하는 DP를 정리한다.
-
백준 19608번 Searching for Strings
백준 19608번 Searching for Strings 풀이. 슬라이딩 윈도우의 알파벳 빈도와 해시 중복 제거로 애너그램 substring 개수를 구한다.
-
백준 17228번 아름다운 만영로
백준 17228번 아름다운 만영로 풀이. 트리를 DFS로 내려가며 경로 문자열의 롤링 해시를 갱신해 패턴과 일치하는 경로 수를 센다.
-
백준 3033번 가장 긴 문자열
백준 3033번 가장 긴 문자열 풀이. 롤링 해시와 이분 탐색으로 중복 부분 문자열이 존재하는 최대 길이를 찾는다.
-
백준 6206번 Milk Patterns
백준 6206번 Milk Patterns 풀이. 정수 수열에 롤링 해시를 적용하고 같은 패턴이 K번 이상 등장하는 최대 길이를 찾는다.
-
백준 24525번 SKK 문자열
백준 24525번 SKK 문자열 풀이. S와 K를 가중치로 바꾼 prefix sum에서 같은 값을 갖는 가장 먼 구간을 찾아 조건 문자열 길이를 구한다.
-
백준 11585번 속타는 저녁 메뉴
백준 11585번 속타는 저녁 메뉴 풀이. 원형 문자열을 두 번 이어 붙이고 KMP로 일치하는 회전 수를 세어 확률을 구한다.
-
백준 4354번 문자열 제곱
백준 4354번 문자열 제곱 풀이. KMP 실패 함수의 마지막 값으로 반복 단위 길이를 구하고 문자열이 몇 번 반복되는지 판정한다.
-
백준 13504번 XOR 합
백준 13504번 XOR 합 풀이. 누적 XOR 값을 Trie에 넣고 두 prefix XOR의 최대 조합을 찾아 부분수열 XOR 최댓값을 구한다.
-
백준 13710번 XOR 합 3
백준 13710번 XOR 합 3 풀이. 누적 XOR과 비트별 0/1 개수 조합을 이용해 모든 부분수열 XOR 합을 계산한다.
-
백준 2830번 행성 X3
백준 2830번 행성 X3 풀이. 각 비트마다 1과 0의 개수를 세고 조합 수를 곱해 모든 쌍의 XOR 합을 구한다.
-
백준 10464번 XOR
백준 10464번 XOR 풀이. 1부터 n까지의 XOR 패턴과 prefix XOR 관계를 이용해 구간 XOR 값을 상수 시간에 계산한다.
-
백준 16903번 수열과 쿼리 20
백준 16903번 수열과 쿼리 20 풀이. 이진 Trie에 수를 삽입, 삭제하고 반대 비트를 우선 선택해 XOR 최댓값을 찾는다.
-
백준 5467번 Type Printer
백준 5467번 Type Printer 풀이. Trie를 구성한 뒤 가장 긴 단어 경로를 마지막에 남기도록 출력과 백스페이스 순서를 정한다.
-
백준 3080번 아름다운 이름
백준 3080번 아름다운 이름 풀이. Trie의 자식 노드 개수에 따른 순열 수를 곱해 가능한 이름 배열 수를 계산한다.
-
백준 5446번 용량 부족
백준 5446번 용량 부족 풀이. 지워야 할 파일과 보존 파일을 Trie에 표시해 한 명령으로 삭제 가능한 경로 수를 최소화한다.
-
백준 19585번 전설
백준 19585번 전설 풀이. 색상은 Trie, 닉네임은 set에 저장해 쿼리 문자열을 두 부분으로 나눌 수 있는지 판정한다.
-
백준 16934번 게임 닉네임
백준 16934번 게임 닉네임 풀이. Trie에 닉네임을 삽입하며 처음으로 새로 생기는 prefix를 출력하고 동일 닉네임은 번호를 붙인다.
-
백준 5670번 휴대폰 자판
백준 5670번 휴대폰 자판 풀이. Trie에서 단어 종료 지점과 분기 노드를 기준으로 자동완성에 필요한 평균 입력 횟수를 계산한다.
-
백준 1086번 박성원
백준 1086번 박성원 풀이. 사용한 숫자 집합과 현재 나머지를 상태로 두고, 큰 수를 직접 만들지 않고 나머지 DP로 확률을 구한다.
-
백준 2618번 경찰차
백준 2618번 경찰차 풀이. 두 경찰차가 마지막으로 처리한 사건 번호를 상태로 두고 최소 이동거리와 담당 차량 경로를 복원한다.
-
백준 11689번 GCD(n, k) = 1
백준 11689번 GCD(n, k)=1 풀이. 오일러 피 함수와 소인수분해를 이용해 n 이하에서 n과 서로소인 수의 개수를 구한다.
-
백준 24524번 아름다운 문자열
백준 24524번 아름다운 문자열 풀이. 목표 문자열의 각 문자 진행 개수를 관리하며 순서대로 완성 가능한 subsequence 수를 센다.
-
백준 24526번 전화 돌리기
백준 24526번 전화 돌리기 풀이. 그래프를 뒤집고 진입 차수 기반 위상 제거를 수행해 사이클에 연결되지 않는 노드 수를 구한다.
-
백준 24527번 이상한 나라의 갈톤보드
백준 24527번 이상한 나라의 갈톤보드 풀이. 구간 업데이트를 lazy segment tree와 imos 방식으로 각각 풀며 도착 구간 계산을 정리한다.
-
백준 16563번 어려운 소인수분해
백준 16563번 어려운 소인수분해 풀이. 각 수의 가장 작은 소인수를 미리 저장해 여러 입력을 빠르게 소인수분해한다.
-
백준 2168번 타일 위의 대각선
백준 2168번 타일 위의 대각선 풀이. 가로와 세로 길이, 최대공약수를 이용해 대각선이 지나는 타일 개수를 계산한다.
-
백준 2487번 섞기 순열
백준 2487번 섞기 순열 풀이. 순열을 사이클로 분해하고 각 사이클 길이의 최소공배수를 구해 원래 상태로 돌아오는 시점을 찾는다.
-
백준 2981번 검문
백준 2981번 검문 풀이. 모든 수의 나머지가 같다는 조건을 인접 차이의 최대공약수와 그 약수 문제로 바꿔 해결한다.
-
백준 16637번 괄호 추가하기
백준 16637번 괄호 추가하기 풀이. 괄호가 겹치지 않는 모든 배치를 재귀로 만들고, 생성된 식을 앞에서부터 계산한다.
-
백준 15824번 너 봄에는 캡사이신이 맛있단다
백준 15824번 너 봄에는 캡사이신이 맛있단다 풀이. 정렬 후 각 원소가 최댓값과 최솟값으로 등장하는 횟수를 거듭제곱으로 계산한다.
-
백준 1014번 컨닝
백준 1014번 컨닝 풀이. 이전 행의 앉은 상태를 비트마스크로 두고 현재 행에서 가능한 배치를 비교하는 DP를 사용한다.
-
백준 22871번 징검다리 건너기 (large)
백준 22871번 징검다리 건너기 풀이. 중간 돌을 거치는 비용의 최댓값을 최소화하도록 가능한 이전 돌들을 비교하는 DP를 정리한다.
-
백준 1700번 멀티탭 스케줄링
백준 1700번 멀티탭 스케줄링 풀이. 멀티탭이 가득 찼을 때 가장 늦게 다시 쓰이거나 다시 쓰이지 않는 기기를 뽑는 그리디를 설명한다.
-
백준 23797번 개구리
백준 23797번 개구리 풀이. K와 P로 끝나는 개구리 수를 상태처럼 관리하며 합쳐지는 규칙에 따라 필요한 최댓값을 계산한다.
-
백준 11097번 도시 계획
백준 11097번 도시 계획 풀이. SCC 내부 순환 간선과 SCC 간 필요한 간선을 구성해 조건을 만족하는 도시 계획을 출력한다.
-
백준 2152번 여행 계획 세우기
백준 2152번 여행 계획 세우기 풀이. SCC를 압축하고 시작점에서 도달 가능한 컴포넌트만 따라가며 방문 가능한 도시 수의 최댓값을 구한다.
-
백준 3977번 축구 전술
백준 3977번 축구 전술 풀이. SCC를 구한 뒤 진입 차수가 0인 SCC가 하나뿐인지 확인해 가능한 시작 전술 노드를 출력한다.
-
백준 4013번 ATM
백준 4013번 ATM 풀이. SCC를 압축해 DAG를 만들고 시작 SCC에서 도달 가능한 경로의 최대 수금액을 DP로 계산한다.
-
백준 6543번 그래프의 싱크
백준 6543번 그래프의 싱크 풀이. SCC 압축 그래프에서 나가는 간선이 없는 컴포넌트의 모든 원래 노드를 찾아 출력한다.
-
백준 1199번 오일러 회로
백준 1199번 오일러 회로 풀이. 모든 정점의 차수가 짝수인지 확인하고 Hierholzer 알고리즘으로 간선을 한 번씩 쓰는 회로를 만든다.
-
백준 1948번 임계경로
백준 1948번 임계경로 풀이. 위상 정렬로 최장 시간을 구한 뒤 역방향으로 추적해 임계 경로에 포함되는 간선 수를 센다.
-
백준 2637번 장난감 조립
백준 2637번 장난감 조립 풀이. 위상 정렬로 중간 부품의 기본 부품 필요량을 누적해 완제품에 필요한 기본 부품 개수를 구한다.
-
백준 2848번 알고스팟어
백준 2848번 알고스팟어 풀이. 인접한 단어의 첫 차이로 알파벳 순서 그래프를 만들고 위상 정렬로 모순과 다중 해를 판정한다.
-
백준 3665번 최종 순위
백준 3665번 최종 순위 풀이. 기존 순위의 상대적 방향 간선을 만들고 바뀐 쌍을 뒤집어 위상 정렬로 최종 순위를 구한다.
-
백준 1005번 ACM Craft
백준 1005번 ACM Craft 풀이. 건물 선행 관계를 위상 정렬로 처리하고 목표 건물까지 필요한 최소 완성 시간을 계산한다.
-
백준 1516번 게임 개발
백준 1516번 게임 개발 풀이. 위상 정렬 순서대로 각 건물의 선행 건물 완료 시간 중 최댓값을 반영해 완성 시간을 구한다.
-
백준 1766번 문제집
백준 1766번 문제집 풀이. 진입 차수가 0인 문제를 최소 힙에 넣어 가능한 문제 중 번호가 작은 것부터 푸는 순서를 만든다.
-
백준 2623번 음악프로그램
백준 2623번 음악프로그램 풀이. DFS 기반 위상 정렬과 진행 중 방문 상태를 이용해 가능한 순서와 사이클 여부를 판단한다.
-
백준 1647번 도시 분할 계획
백준 1647번 도시 분할 계획 풀이. MST를 만들되 가장 큰 간선을 제외해 두 마을로 나누는 최소 유지비를 구한다.
-
백준 1944번 복제 로봇
백준 1944번 복제 로봇 풀이. 시작점과 열쇠 사이 최단거리를 BFS로 간선화하고 MST를 만들어 모든 열쇠를 연결한다.
-
백준 2887번 행성 터널
백준 2887번 행성 터널 풀이. x, y, z 좌표별 인접 행성 간선만 후보로 삼아 MST 간선 수를 크게 줄인다.
-
백준 4343번 Arctic Network
백준 4343번 Arctic Network 풀이. 위성 채널 수만큼 네트워크를 분리하도록 MST에서 필요한 마지막 간선 비용을 계산한다.
-
백준 9373번 복도 뚫기
백준 9373번 복도 뚫기 풀이. 센서와 양쪽 벽을 정점으로 보고 MST처럼 연결해 두 벽이 막히는 최소 간격을 찾는다.
-
백준 18185번 라면 사기
백준 18185번 라면 사기 풀이. 연속한 공장에서 묶어 사는 단가 차이를 이용해 3개, 2개, 1개 구매를 그리디하게 배치한다.
-
백준 1602번 도망자 원숭이
백준 1602번 도망자 원숭이 풀이. 노드의 지연 시간을 고려해 경유 가능한 노드를 순서대로 확장하며 최단 거리와 최대 지연을 함께 계산한다.
-
백준 1613번 역사
백준 1613번 역사 풀이. 플로이드 워셜로 사건 간 도달 가능성을 계산해 두 사건의 선후 관계를 판단한다.
-
백준 2610번 회의준비
백준 2610번 회의준비 풀이. 컴포넌트를 나누고 플로이드 워셜로 각 그룹에서 최대 전달 시간이 가장 작은 대표를 고른다.
-
백준 11657번 타임머신
백준 11657번 타임머신 풀이. 음의 간선이 있는 그래프에서 벨만 포드 알고리즘으로 최단거리와 음수 사이클을 판정한다.
-
백준 1219번 오민식의 고민
백준 1219번 오민식의 고민 풀이. 수익을 반영한 벨만 포드와 사이클 전파로 도착지에서 무한히 돈을 벌 수 있는지 판정한다.
-
백준 1738번 골목길
백준 1738번 골목길 풀이. 목적지까지 이어지는 양의 사이클만 걸러내도록 벨만 포드 변형과 경로 복원을 함께 사용한다.
-
1162번 도로포장
백준 1162번 도로포장 풀이. 도로를 몇 번 포장했는지 상태에 포함한 다익스트라로 K개 이하 도로를 무료화한 최단 거리를 구한다.
-
백준 10217번 KCM Travel
백준 10217번 KCM Travel 풀이. 사용한 비용을 상태로 두고 각 비용에서 가능한 최소 시간을 관리하는 최단 경로 접근을 정리한다.
-
백준 2211번 네트워크 복구
백준 2211번 네트워크 복구 풀이. 1번 노드 기준 다익스트라를 수행하며 각 노드의 부모 간선을 저장해 복구할 네트워크를 만든다.
-
백준 5719번 거의 최단 경로
백준 5719번 거의 최단 경로 풀이. 모든 최단 경로에 포함된 간선을 역추적으로 제거한 뒤 다시 다익스트라를 수행한다.
-
백준 10473번 인간 대포
백준 10473번 인간 대포 풀이. 시작점, 대포, 목적지를 완전 그래프로 만들고 걷기와 대포 이동 시간을 비교해 다익스트라를 적용한다.
-
백준 15422번 Bumped!
백준 15422번 Bumped! 풀이. 비행기 티켓 사용 전후를 두 그래프 층으로 나누고 0비용 간선을 연결해 최단 시간을 구한다.
-
백준 17435번 합성함수와 쿼리
백준 17435번 합성함수와 쿼리 풀이. f의 1, 2, 4, 8회 적용 결과를 sparse table로 저장해 합성함수 값을 로그 시간에 구한다.
-
백준 2213번 트리의 독립집합
백준 2213번 트리의 독립집합 풀이. 부모 선택 여부에 따라 노드 선택을 나누는 트리 DP와 선택 노드 복원 과정을 정리한다.
-
백준 2248번 이진수 찾기
백준 2248번 이진수 찾기 풀이. 자릿수와 1의 개수 제한별 경우의 수를 DP로 세고, prefix count로 I번째 수를 구성한다.
-
백준 2533번 사회망 서비스
백준 2533번 사회망 서비스 풀이. 트리에서 부모의 얼리어답터 여부에 따라 현재 노드 선택 가능성을 나누는 DP를 정리한다.
-
백준 17131번 여우가 정보섬에 올라온 이유
백준 17131번 여우가 정보섬에 올라온 이유 풀이. 좌우 스위핑으로 각 별보다 높은 별의 개수를 구하고 곱해 별자리 경우를 계산한다.
-
백준 13925번 수열과 쿼리 13
백준 13925번 수열과 쿼리 13 풀이. 더하기, 곱하기, 대입 쿼리를 ax+b 형태의 lazy 값으로 합성해 처리한다.
-
백준 5419번 북서풍
백준 5419번 북서풍 풀이. 좌표 압축과 세그먼트 트리를 이용해 정렬된 순서에서 조건을 만족하는 점 쌍의 수를 센다.
-
백준 13537번 수열과 쿼리 1
백준 13537번 수열과 쿼리 1 풀이. 머지 소트 트리의 정렬된 구간 벡터에서 upper_bound로 K보다 큰 원소 개수를 구한다.
-
백준 7469번 K번째 수
백준 7469번 K번째 수 풀이. 머지 소트 트리로 구간 내 특정 값 이하의 개수를 구하고 이분 탐색으로 K번째 수를 찾는다.
-
백준 1395번 스위치
백준 1395번 스위치 풀이. 켜진 스위치 개수와 반전 lazy 값을 저장해 구간 토글과 개수 질의를 처리한다.
-
백준 10999번 구간 합 구하기 2
백준 10999번 구간 합 구하기 2 풀이. Lazy propagation으로 구간 업데이트를 미뤄 두고 필요한 순간에 합을 반영한다.
-
백준 12844번 XOR
백준 12844번 XOR 풀이. XOR의 결합법칙과 교환법칙을 이용해 구간 XOR 쿼리와 lazy XOR 업데이트를 처리한다.
-
백준 5676번 음주 코딩
백준 5676번 음주 코딩 풀이. 수를 양수, 음수, 0으로만 변환해 구간 곱의 부호를 세그먼트 트리로 빠르게 판단한다.
-
백준 1572번 중앙값
백준 1572번 중앙값 풀이. 값 범위에 대한 세그먼트 트리를 만들고 슬라이딩 윈도우의 K번째 값을 찾아 중앙값 합을 구한다.
-
백준 2104번 부분배열 고르기
백준 2104번 부분배열 고르기 풀이. 구간 최솟값의 인덱스를 기준으로 분할 정복하며 부분배열 합과 최솟값의 곱을 최대화한다.
-
백준 2517번 달리기
백준 2517번 달리기 풀이. 실력을 좌표 압축한 뒤 세그먼트 트리로 앞선 선수 중 자신보다 강한 사람 수를 계산한다.
-
백준 7578번 공장
백준 7578번 공장 풀이. 두 생산 라인의 같은 기계 위치를 매핑하고 세그먼트 트리로 교차하는 연결선 수를 센다.
-
백준 2243번 사탕상자
백준 2243번 사탕상자 풀이. 맛별 사탕 개수 합을 세그먼트 트리에 저장하고, 순위 기반 탐색으로 원하는 사탕 맛을 찾는다.
-
백준 9345번 디지털 비디오 디스크(DVDs)
백준 9345번 디지털 비디오 디스크 풀이. 구간의 최솟값과 최댓값을 세그먼트 트리에 저장해 해당 범위의 DVD가 모두 있는지 확인한다.
-
백준 3653번 영화 수집
백준 3653번 영화 수집 풀이. DVD 위치를 넉넉한 인덱스 영역에 배치하고 세그먼트 트리로 위에 쌓인 DVD 개수를 센다.
-
백준 1280번 나무 심기
백준 1280번 나무 심기 풀이. 왼쪽과 오른쪽 나무의 개수와 거리 합을 세그먼트 트리에 저장해 새 나무의 비용을 계산한다.
-
백준 3006번 터보소트
백준 3006번 터보소트 풀이. 세그먼트 트리로 남아 있는 원소 수를 세며 1, N, 2, N-1 순서의 이동 횟수를 계산한다.
-
백준 1517번 버블 소트
백준 1517번 버블 소트 풀이. 실제 버블 정렬 대신 세그먼트 트리로 아직 정렬되지 않은 앞쪽 원소 수를 세어 swap 횟수를 구한다.
-
백준 6549번 히스토그램에서 가장 큰 직사각형
백준 6549번 히스토그램에서 가장 큰 직사각형 풀이. 최소 높이 막대를 기준으로 구간을 나누고 세그먼트 트리로 최솟값 인덱스를 찾는다.
-
백준 11505번 구간 곱 구하기
백준 11505번 구간 곱 구하기 풀이. 세그먼트 트리에 구간 곱을 저장하고 업데이트 시 리프부터 부모 노드까지 값을 다시 계산한다.
-
백준 12837번 가계부 (Hard)
백준 12837번 가계부 (Hard) 풀이. 값 변경이 아니라 누적 추가가 일어나는 구간 합 질의를 세그먼트 트리로 처리한다.
-
백준 2357번 최솟값과 최댓값
백준 2357번 최솟값과 최댓값 풀이. 구간 최솟값 트리와 최댓값 트리를 각각 만들어 RMQ 질의에 답한다.
-
백준 10775번 공항
백준 10775번 공항 풀이. 도킹 가능한 가장 큰 게이트를 유니온 파인드로 추적해 비행기를 최대한 많이 배치한다.
-
백준 17398번 통신망 분할
백준 17398번 통신망 분할 풀이. 제거되지 않는 간선을 먼저 합치고, 끊은 간선을 역순으로 복구하며 분할 비용을 누적한다.
-
백준 2042번 구간 합 구하기
백준 2042번 구간 합 구하기 풀이. 세그먼트 트리로 구간 합 질의와 단일 값 업데이트를 모두 O(log N)에 처리한다.
-
백준 9938번 방 청소
백준 9938번 방 청소 풀이. 연결된 서랍 집합의 남은 공간 수를 루트에 저장해 각 술병을 보관할 수 있는지 빠르게 판단한다.
-
백준 11085번 군사 이동
백준 11085번 군사 이동 풀이. 간선을 수용량 내림차순으로 연결하며 출발지와 도착지가 이어지는 순간의 최소 수용량을 찾는다.
-
백준 14868번 문명
백준 14868번 문명 풀이. BFS로 문명을 확장하고 인접한 문명을 유니온 파인드로 합치며 모두 연결되는 해를 찾는다.
-
백준 3197번 백조의 호수
백준 3197번 백조의 호수 풀이. 물 확산을 BFS로 진행하고 녹아 연결된 영역을 유니온 파인드로 묶어 백조가 만나는 날을 구한다.
-
백준 14003번 가장 긴 증가하는 부분 수열 5
백준 14003번 가장 긴 증가하는 부분 수열 5 풀이. O(N log N) LIS 과정에서 이전 값을 추적해 실제 증가 부분 수열을 복원한다.
-
백준 10942번 팰린드롬?
백준 10942번 팰린드롬 풀이. 양끝 문자가 같고 내부 구간이 팰린드롬인지 여부를 메모이제이션해 여러 질의에 답한다.
-
백준 1509번 팰린드롬 분할
백준 1509번 팰린드롬 분할 풀이. 팰린드롬 구간 판정과 최소 분할 개수 DP를 결합해 문자열을 나누는 최솟값을 구한다.
-
백준 2162번 선분 그룹
백준 2162번 선분 그룹 풀이. 선분 교차 판정과 유니온 파인드를 결합해 그룹 개수와 가장 큰 그룹 크기를 계산한다.
-
백준 2342번 Dance Dance Revolution
백준 2342번 Dance Dance Revolution 풀이. 양발의 위치와 진행 인덱스를 상태로 두어 발판을 밟는 최소 힘을 메모이제이션한다.
-
백준 17387번 선분 교차 2
백준 17387번 선분 교차 2 풀이. CCW와 끝점 대소 비교를 이용해 일반 교차와 일직선상 겹침을 모두 판정한다.
-
백준 7579번 앱
백준 7579번 앱 풀이. 비용을 DP 인덱스로 삼아 각 비용으로 확보 가능한 최대 메모리를 저장하고 최소 비용을 찾는다.
-
백준 11049번 행렬 곱셈 순서
백준 11049번 행렬 곱셈 순서 풀이. 시작과 끝 행렬 범위를 상태로 두고 분할 지점별 곱셈 비용의 최솟값을 메모이제이션한다.
-
백준 17404번 RGB거리 2
백준 17404번 RGB거리 2 풀이. 첫 집의 색을 고정한 뒤 마지막 집과 겹치지 않도록 색칠 비용의 최솟값을 DP로 구한다.
-
백준 14464번 소가 길을 건너간 이유 4
백준 14464번 소가 길을 건너간 이유 4 풀이. 닭이 도와줄 수 있는 소 중 종료 시간이 가장 빠른 소를 고르는 그리디 매칭을 설명한다.
-
백준 16562번 친구비
백준 16562번 친구비 풀이. 친구 관계를 유니온 파인드로 묶고 각 집합의 최소 친구비를 합산해 예산 가능 여부를 판단한다.
-
백준 1717번 집합의 표현
백준 1717번 집합의 표현 풀이. 경로 압축을 사용하는 유니온 파인드의 union과 find 연산을 구현해 집합 포함 여부를 판정한다.
-
백준 4195번 친구 네트워크
백준 4195번 친구 네트워크 풀이. 이름을 인덱스로 매핑하고 루트에 집합 크기를 저장하는 유니온 파인드로 네트워크 크기를 출력한다.
-
백준 1715번 카드 정렬하기
백준 1715번 카드 정렬하기 풀이. 가장 작은 카드 묶음 두 개를 반복해서 합치는 최소 힙 기반 그리디 전략을 정리한다.
-
백준 2014번 소수의 곱
백준 2014번 소수의 곱 풀이. 최소 힙에서 작은 곱을 꺼내 다시 소수들과 곱하며 중복과 오버플로우를 관리한다.
-
백준 2696번 중앙값 구하기
백준 2696번 중앙값 구하기 풀이. 최대 힙과 최소 힙의 균형을 유지해 입력이 들어올 때마다 중앙값을 출력한다.
-
백준 10649번 프리스비
백준 10649번 프리스비 풀이. 선택된 소 집합의 안정도를 비트마스크 DP로 저장하고, 소를 위나 아래에 놓는 경우를 비교한다.
-
백준 1176번 섞기
백준 1176번 섞기 풀이. 마지막으로 세운 학생과 지금까지 세운 학생 집합을 상태로 두어 조건을 만족하는 순서의 수를 센다.
-
백준 1029번 그림 교환
백준 1029번 그림 교환 풀이. 현재 소유자, 구매 가격, 방문한 예술가 집합을 상태로 두어 가능한 최대 거래 인원 수를 구한다.
-
백준 1480번 보석 모으기
백준 1480번 보석 모으기 풀이. 가방 번호, 현재 가방 무게, 담은 보석 집합을 상태로 관리해 담을 수 있는 보석 수의 최댓값을 찾는다.
-
백준 16991번 외판원 순회 3
백준 16991번 외판원 순회 3 풀이. 좌표 사이의 유클리드 거리를 비용으로 사용해 비트마스크 TSP를 적용한다.
-
백준 2320번 끝말잇기
백준 2320번 끝말잇기 풀이. 마지막 문자와 사용한 단어 집합을 상태로 두고 얻을 수 있는 최고 점수를 메모이제이션한다.
-
백준 1102번 발전소
백준 1102번 발전소 풀이. 켜진 발전소 상태를 비트마스크로 표현하고, 목표 개수 이상을 켜는 최소 추가 비용을 탐색한다.
-
백준 3056번 007
백준 3056번 007 풀이. 미션 할당 여부를 비트마스크로 두고 각 요원에게 미션을 배정하는 최대 성공 확률을 DP로 계산한다.
-
백준 1600번 말이 되고픈 원숭이
백준 1600번 말이 되고픈 원숭이 풀이. 말처럼 점프한 횟수를 BFS 상태에 포함해 장애물이 있는 격자에서 최단 이동을 구한다.
-
백준 2098번 외판원 순회
백준 2098번 외판원 순회 풀이. 현재 도시와 방문 도시 비트마스크를 상태로 두고 모든 도시를 방문하는 최소 비용을 메모이제이션한다.
-
백준 14442번 벽 부수고 이동하기 2
백준 14442번 벽 부수고 이동하기 2 풀이. 현재까지 부순 벽의 개수를 BFS 상태로 포함해 K번 이하로 벽을 부수는 최단 거리를 찾는다.
-
백준 16933번 벽 부수고 이동하기 3
백준 16933번 벽 부수고 이동하기 3 풀이. 낮과 밤, 벽을 부순 횟수, 대기 횟수를 상태로 기록해 조건이 있는 최단 경로를 탐색한다.
-
백준 9328번 열쇠
백준 9328번 열쇠 풀이. 열쇠 보유 상태가 바뀌면 이전에 막혔던 위치도 다시 탐색할 수 있게 처리해 문서 개수를 센다.
-
백준 1194번 달이 차오른다, 가자.
백준 1194번 달이 차오른다, 가자 풀이. 열쇠 보유 상태를 비트마스크로 기록해 같은 위치라도 다른 열쇠 상태면 다시 탐색한다.
-
백준 2001번 보석 줍기
백준 2001번 보석 줍기 풀이. 보유 보석 집합을 비트마스크로 관리하며 같은 섬과 같은 보석 상태의 중복 방문을 막는다.
-
백준 12094번 2048 (Hard)
백준 12094번 2048 (Hard) 풀이. 보드를 회전해 한 방향 이동만 구현하고, 변화 없는 이동과 도달 불가능한 최댓값을 가지치기한다.
-
백준 1562번 계단 수
백준 1562번 계단 수 풀이. 길이, 마지막 숫자, 사용한 숫자 비트마스크를 상태로 두어 모든 숫자를 포함하는 계단 수를 센다.
-
백준 1799번 비숍
백준 1799번 비숍 풀이. 대각선 점유 여부를 이용하고 흑백 칸을 분리해 탐색량을 줄이는 백트래킹 전략을 정리한다.
-
백준 2263번 트리의 순회
백준 2263번 트리의 순회 풀이. inorder와 postorder의 인덱스 범위만 넘기며 루트와 서브트리 크기를 찾아 preorder를 출력한다.
-
백준 17136번 색종이 붙이기
백준 17136번 색종이 붙이기 풀이. 붙일 수 있는 색종이 크기와 남은 장수를 확인하며 되돌리기 가능한 백트래킹으로 최소 장수를 구한다.
-
백준 1182번 부분수열의 합
백준 1182번 부분수열의 합 풀이. 각 원소를 선택하거나 선택하지 않는 모든 경우를 백트래킹으로 탐색해 목표 합의 개수를 센다.
-
백준 1759번 암호 만들기
백준 1759번 암호 만들기 풀이. 알파벳 선택 여부를 백트래킹하며 모음 1개 이상, 자음 2개 이상 조건을 만족하는 암호를 출력한다.
-
백준 1987번 알파벳
백준 1987번 알파벳 풀이. 지금까지 사용한 알파벳을 기록하면서 상하좌우로 이동 가능한 경로의 최대 길이를 DFS로 찾는다.
-
백준 2096번 내려가기
백준 2096번 내려가기 풀이. 현재 칸에 올 수 있는 이전 칸의 최댓값과 최솟값만 유지해 메모리 제한 안에서 DP를 수행한다.
-
백준 2580번 스도쿠
백준 2580번 스도쿠 풀이. 행, 열, 3x3 박스의 사용 숫자를 기록하고 빈 칸을 백트래킹으로 채워 유효한 보드를 찾는다.
-
백준 17071번 숨바꼭질 5
백준 17071번 숨바꼭질 5 풀이. 수빈이의 도달 시간을 홀짝 상태로 나누어 기록하고, 움직이는 동생과 만날 수 있는 시점을 판정한다.
-
백준 2294번 동전 2
백준 2294번 동전 2 풀이. 각 금액을 만드는 데 필요한 최소 동전 수를 저장하고 현재 동전을 사용하는 경우와 비교해 갱신한다.
-
백준 1525번 퍼즐
백준 1525번 퍼즐 풀이. 퍼즐 상태를 문자열 키로 표현하고 map에 이동 횟수를 저장하며 BFS로 목표 상태까지의 최단 이동을 찾는다.
-
백준 11967번 불켜기
백준 11967번 불켜기 풀이. 불은 켜졌지만 아직 갈 수 없는 방을 따로 기록하고, 새로 접근 가능해지는 방을 BFS에 반영한다.
-
백준 16920 확장 게임
백준 16920번 확장 게임 풀이. 플레이어별 큐를 따로 두고 각자의 확장 거리만큼 차례대로 BFS를 진행해 점령 칸 수를 계산한다.
-
백준 4179번 불!
백준 4179번 불! 풀이. 불의 확산 시간과 지훈이의 이동 시간을 따로 BFS로 구해 불보다 먼저 도달 가능한 탈출 경로를 찾는다.
-
백준 5014번 스타트링크
백준 5014번 스타트링크 풀이. 엘리베이터가 갈 수 있는 층을 BFS로 탐색하며 범위와 방문 시간을 관리해 최소 버튼 횟수를 구한다.
-
백준 9466번 텀 프로젝트
백준 9466번 텀 프로젝트 풀이. 학생 선택 그래프에서 사이클을 이루는 학생만 팀으로 분류하고 나머지 인원을 계산한다.
-
백준 3015번 오아시스 재결합
백준 3015번 오아시스 재결합 풀이. 같은 키가 연속되는 사람 수를 스택에 함께 저장해 서로 볼 수 있는 쌍을 효율적으로 계산한다.
-
백준 2493번 탑
백준 2493번 탑 풀이. 스택으로 왼쪽에 있는 더 높은 탑 후보를 관리하며 각 탑의 레이저를 수신하는 위치를 찾는다.