Seungil Kim
All tags

Posts tagged "dp"

  • 백준 13489번 Vještica
    #boj #ps #dp
    백준 13489번 Vještica 풀이. 단어 집합을 비트마스크로 나누고 공통 prefix를 공유하는 Trie 최소 노드 수를 DP로 계산한다.
  • 백준 24229번 모두싸인 출근길
    #boj #ps #dp
    백준 24229번 모두싸인 출근길 풀이. 겹치는 판자를 정렬 후 병합하고, 이어진 구간을 이용해 갈 수 있는 최종 위치를 계산한다.
  • 백준 25949번 Jar Game
    #boj #ps #dp
    백준 25949번 Jar Game 풀이. 세 항아리의 남은 조약돌과 현재 턴을 상태로 정의해 게임 DP로 승패를 판정한다.
  • 백준 2287번 모노디지털 표현
    #dp #cpp #ps
    백준 2287번 모노디지털 표현 풀이. 같은 숫자를 i개 써서 만들 수 있는 값 집합을 사칙연산으로 확장하는 DP를 정리한다.
  • 백준 1086번 박성원
    #dp #cpp #ps
    백준 1086번 박성원 풀이. 사용한 숫자 집합과 현재 나머지를 상태로 두고, 큰 수를 직접 만들지 않고 나머지 DP로 확률을 구한다.
  • 백준 2618번 경찰차
    #dp #cpp #ps
    백준 2618번 경찰차 풀이. 두 경찰차가 마지막으로 처리한 사건 번호를 상태로 두고 최소 이동거리와 담당 차량 경로를 복원한다.
  • 백준 1014번 컨닝
    #dp #cpp #ps
    백준 1014번 컨닝 풀이. 이전 행의 앉은 상태를 비트마스크로 두고 현재 행에서 가능한 배치를 비교하는 DP를 사용한다.
  • 백준 22871번 징검다리 건너기 (large)
    #dp #cpp #ps
    백준 22871번 징검다리 건너기 풀이. 중간 돌을 거치는 비용의 최댓값을 최소화하도록 가능한 이전 돌들을 비교하는 DP를 정리한다.
  • 백준 2152번 여행 계획 세우기
    #dp #graph #cpp #ps
    백준 2152번 여행 계획 세우기 풀이. SCC를 압축하고 시작점에서 도달 가능한 컴포넌트만 따라가며 방문 가능한 도시 수의 최댓값을 구한다.
  • 백준 4013번 ATM
    #dp #graph #cpp #ps
    백준 4013번 ATM 풀이. SCC를 압축해 DAG를 만들고 시작 SCC에서 도달 가능한 경로의 최대 수금액을 DP로 계산한다.
  • 백준 2637번 장난감 조립
    #dp #graph #cpp #ps
    백준 2637번 장난감 조립 풀이. 위상 정렬로 중간 부품의 기본 부품 필요량을 누적해 완제품에 필요한 기본 부품 개수를 구한다.
  • 백준 2213번 트리의 독립집합
    #dp #cpp #ps #tree
    백준 2213번 트리의 독립집합 풀이. 부모 선택 여부에 따라 노드 선택을 나누는 트리 DP와 선택 노드 복원 과정을 정리한다.
  • 백준 2248번 이진수 찾기
    #dp #prefix-sum #cpp #ps
    백준 2248번 이진수 찾기 풀이. 자릿수와 1의 개수 제한별 경우의 수를 DP로 세고, prefix count로 I번째 수를 구성한다.
  • 백준 2533번 사회망 서비스
    #dp #cpp #ps #tree
    백준 2533번 사회망 서비스 풀이. 트리에서 부모의 얼리어답터 여부에 따라 현재 노드 선택 가능성을 나누는 DP를 정리한다.
  • 백준 14003번 가장 긴 증가하는 부분 수열 5
    #dp #binary-search #cpp #ps
    백준 14003번 가장 긴 증가하는 부분 수열 5 풀이. O(N log N) LIS 과정에서 이전 값을 추적해 실제 증가 부분 수열을 복원한다.
  • 백준 10942번 팰린드롬?
    #dp #cpp #ps
    백준 10942번 팰린드롬 풀이. 양끝 문자가 같고 내부 구간이 팰린드롬인지 여부를 메모이제이션해 여러 질의에 답한다.
  • 백준 1509번 팰린드롬 분할
    #dp #cpp #ps
    백준 1509번 팰린드롬 분할 풀이. 팰린드롬 구간 판정과 최소 분할 개수 DP를 결합해 문자열을 나누는 최솟값을 구한다.
  • 백준 2342번 Dance Dance Revolution
    #dp #cpp #ps
    백준 2342번 Dance Dance Revolution 풀이. 양발의 위치와 진행 인덱스를 상태로 두어 발판을 밟는 최소 힘을 메모이제이션한다.
  • 백준 7579번 앱
    #dp #cpp #ps
    백준 7579번 앱 풀이. 비용을 DP 인덱스로 삼아 각 비용으로 확보 가능한 최대 메모리를 저장하고 최소 비용을 찾는다.
  • 백준 11049번 행렬 곱셈 순서
    #divide-and-conquer #dp #cpp #ps
    백준 11049번 행렬 곱셈 순서 풀이. 시작과 끝 행렬 범위를 상태로 두고 분할 지점별 곱셈 비용의 최솟값을 메모이제이션한다.
  • 백준 17404번 RGB거리 2
    #dp #cpp #ps
    백준 17404번 RGB거리 2 풀이. 첫 집의 색을 고정한 뒤 마지막 집과 겹치지 않도록 색칠 비용의 최솟값을 DP로 구한다.
  • 백준 10649번 프리스비
    #dp #bitmasking #cpp #ps
    백준 10649번 프리스비 풀이. 선택된 소 집합의 안정도를 비트마스크 DP로 저장하고, 소를 위나 아래에 놓는 경우를 비교한다.
  • 백준 1176번 섞기
    #dp #bitmasking #cpp #ps
    백준 1176번 섞기 풀이. 마지막으로 세운 학생과 지금까지 세운 학생 집합을 상태로 두어 조건을 만족하는 순서의 수를 센다.
  • 백준 1029번 그림 교환
    #dp #bitmasking #cpp #ps
    백준 1029번 그림 교환 풀이. 현재 소유자, 구매 가격, 방문한 예술가 집합을 상태로 두어 가능한 최대 거래 인원 수를 구한다.
  • 백준 1480번 보석 모으기
    #dp #bitmasking #cpp #ps
    백준 1480번 보석 모으기 풀이. 가방 번호, 현재 가방 무게, 담은 보석 집합을 상태로 관리해 담을 수 있는 보석 수의 최댓값을 찾는다.
  • 백준 16991번 외판원 순회 3
    #dp #bitmasking #cpp #ps
    백준 16991번 외판원 순회 3 풀이. 좌표 사이의 유클리드 거리를 비용으로 사용해 비트마스크 TSP를 적용한다.
  • 백준 2320번 끝말잇기
    #dp #bitmasking #cpp #ps
    백준 2320번 끝말잇기 풀이. 마지막 문자와 사용한 단어 집합을 상태로 두고 얻을 수 있는 최고 점수를 메모이제이션한다.
  • 백준 1102번 발전소
    #dp #bitmasking #cpp #ps
    백준 1102번 발전소 풀이. 켜진 발전소 상태를 비트마스크로 표현하고, 목표 개수 이상을 켜는 최소 추가 비용을 탐색한다.
  • 백준 3056번 007
    #dp #bitmasking #cpp #ps
    백준 3056번 007 풀이. 미션 할당 여부를 비트마스크로 두고 각 요원에게 미션을 배정하는 최대 성공 확률을 DP로 계산한다.
  • 백준 2098번 외판원 순회
    #dp #bitmasking #cpp #ps
    백준 2098번 외판원 순회 풀이. 현재 도시와 방문 도시 비트마스크를 상태로 두고 모든 도시를 방문하는 최소 비용을 메모이제이션한다.
  • 백준 1562번 계단 수
    #dp #bitmasking #cpp #ps
    백준 1562번 계단 수 풀이. 길이, 마지막 숫자, 사용한 숫자 비트마스크를 상태로 두어 모든 숫자를 포함하는 계단 수를 센다.
  • 백준 2096번 내려가기
    #dp #cpp #ps
    백준 2096번 내려가기 풀이. 현재 칸에 올 수 있는 이전 칸의 최댓값과 최솟값만 유지해 메모리 제한 안에서 DP를 수행한다.
  • 백준 2294번 동전 2
    #dp #cpp #ps
    백준 2294번 동전 2 풀이. 각 금액을 만드는 데 필요한 최소 동전 수를 저장하고 현재 동전을 사용하는 경우와 비교해 갱신한다.
  • 백준 9251번 LCS
    #dp #string #ps #python
    백준 9251번 LCS 풀이. 두 문자열의 접두사 조합마다 최장 공통 부분 수열 길이를 저장하는 2차원 DP를 정리한다.
  • 백준 2407번 조합
    #dp #ps #python
    백준 2407번 조합 풀이. 큰 조합 값을 직접 계산하기 위해 파스칼의 삼각형 점화식을 활용하는 방법을 정리한다.
  • 백준 9465번 스티커
    #dp #ps #python
    백준 9465번 스티커 풀이. 위아래 스티커 선택 상태를 나눠 각 위치를 선택했을 때 가능한 최대 점수를 누적한다.
  • 백준 12865번 평범한 배낭
    #dp #ps #python
    백준 12865번 평범한 배낭 풀이. 무게별 최대 가치를 저장하는 DP 테이블로 0/1 배낭 문제의 최적값을 계산한다.
  • 백준 11660번 구간 합 구하기 5
    #dp #ps #python
    백준 11660번 구간 합 구하기 5 풀이. 2차원 누적합을 만들어 직사각형 영역 합을 포함-배제 방식으로 빠르게 계산한다.
  • 백준 1932번 정수 삼각형
    #dp #ps #python
    백준 1932번 정수 삼각형 풀이. 각 칸에 도달 가능한 왼쪽 위와 오른쪽 위 경로 중 더 큰 합을 누적하는 DP를 정리한다.
  • 백준 2579번 계단 오르기
    #dp #ps #python
    백준 2579번 계단 오르기 풀이. 마지막 계단을 반드시 밟되 세 계단 연속 금지를 만족하도록 두 가지 이전 상태를 비교하는 DP를 정리한다.
  • 백준 11726번 2xn 타일링
    #dp #ps #python
    백준 11726번 2xn 타일링 풀이. 마지막에 붙이는 타일 모양을 기준으로 n-1, n-2 경우를 더하는 DP 점화식을 설명한다.
  • 백준 12015번 가장 긴 증가하는 부분 수열 2
    #dp #binary-search #ps #python
    백준 12015번 가장 긴 증가하는 부분 수열 2 풀이. 길이별 최소 끝값을 유지하고 이분 탐색으로 O(N log N)에 LIS 길이를 구한다.
  • 백준 11053번 가장 긴 증가하는 부분 수열
    #dp #ps #python
    백준 11053번 가장 긴 증가하는 부분 수열 풀이. 각 위치를 마지막 원소로 삼는 LIS 길이를 앞쪽 원소들과 비교해 갱신한다.
  • 백준 1912번 연속합
    #dp #ps #python
    백준 1912번 연속합 풀이. 누적합이 음수가 되는 지점에서 시작점을 바꾸는 카데인 알고리즘의 핵심 아이디어를 설명한다.
  • 백준 2293번 동전 1
    #dp #ps #python
    백준 2293번 동전 1 풀이. 동전을 하나씩 추가하며 각 금액을 만드는 경우의 수를 갱신하는 DP 점화식을 정리한다.
  • 백준 1149번 RGB거리
    #dp #ps #python
    백준 1149번 RGB거리 풀이. 각 집을 특정 색으로 칠할 때 이전 집의 다른 색 비용 중 최솟값을 누적하는 DP 점화식을 정리한다.