Posts tagged "ps"

• 백준 17835번 면접보는 승범이네

  2023년 11월 24일 · #ps #boj #graph

  백준 17835번 면접보는 승범이네 풀이. 가상 정점에서 면접장들을 0거리로 연결해 역방향 다익스트라 한 번으로 각 도시의 최단 거리를 구한다.
• 2022 SKKU 프로그래밍 대회 in 소프트의 밤

  2023년 7월 2일 · #ps #skku

  2022 SKKU 프로그래밍 대회 in 소프트의 밤 후기. 대회 결과와 각 문제의 풀이 아이디어, 다음 대회 목표를 정리했다.
• 2022 성균관대학교 프로그래밍 경진대회

  2023년 7월 2일 · #ps #skku

  2022 성균관대학교 프로그래밍 경진대회 후기. 첫 프로그래밍 대회 참가 경험과 문제 풀이 감상을 짧게 남긴 글.
• 그래프 최단경로 알고리즘 정리

  2023년 7월 2일 · #ps #graph

  그래프 최단경로 알고리즘 정리. 다익스트라, 벨만 포드, 플로이드 워셜의 사용 조건과 시간복잡도, 구현 포인트를 비교한다.
• 백준 2261번 가장 가까운 두 점

  2023년 7월 2일 · #boj #ps

  백준 2261번 가장 가까운 두 점 풀이. x좌표 스위핑과 y좌표 기준 set을 이용해 후보 점만 검사하며 최단 거리를 갱신한다.
• 백준 1062번 가르침

  2023년 7월 2일 · #boj #ps

  백준 1062번 가르침 풀이. 배운 알파벳과 단어 구성을 비트마스크로 표현해 읽을 수 있는 단어 수를 최대화한다.
• 백준 10986번 나머지 합

  2023년 7월 2일 · #boj #ps

  백준 10986번 나머지 합 풀이. 누적합의 나머지가 같은 두 지점을 고르면 구간 합이 M으로 나누어떨어진다는 성질을 이용한다.
• 백준 11444번 피보나치 수 6

  2023년 7월 2일 · #boj #ps

  백준 11444번 피보나치 수 6 풀이. 행렬 거듭제곱을 분할 정복으로 계산해 매우 큰 n번째 피보나치 수를 빠르게 구한다.
• 백준 13489번 Vještica

  2023년 7월 2일 · #boj #ps #dp

  백준 13489번 Vještica 풀이. 단어 집합을 비트마스크로 나누고 공통 prefix를 공유하는 Trie 최소 노드 수를 DP로 계산한다.
• 백준 13711번 LCS 4

  2023년 7월 2일 · #boj #ps

  백준 13711번 LCS 4 풀이. 한 수열의 위치 정보를 기준으로 다른 수열을 인덱스 배열로 바꾸고 LIS로 LCS 길이를 구한다.
• 백준 1588번 수열

  2023년 7월 2일 · #boj #ps

  백준 1588번 수열 풀이. 3분할 재귀 구조를 이용해 큰 수열을 직접 만들지 않고 특정 구간의 1, 2, 3 개수를 계산한다.
• 백준 17297번 Messi Gimossi

  2023년 7월 2일 · #boj #ps

  백준 17297번 Messi Gimossi 풀이. 피보나치처럼 이어지는 문자열 길이를 이용해 M번째 문자가 어느 이전 문자열에 속하는지 줄여 간다.
• 백준 23741번 야바위 게임

  2023년 7월 2일 · #boj #ps #graph

  백준 23741번 야바위 게임 풀이. 정점에 홀수 번 또는 짝수 번 이동해 도착했는지만 구분해 여러 번 간선을 타는 상태를 압축한다.
• 백준 24229번 모두싸인 출근길

  2023년 7월 2일 · #boj #ps #dp

  백준 24229번 모두싸인 출근길 풀이. 겹치는 판자를 정렬 후 병합하고, 이어진 구간을 이용해 갈 수 있는 최종 위치를 계산한다.
• 백준 25949번 Jar Game

  2023년 7월 2일 · #boj #ps #dp

  백준 25949번 Jar Game 풀이. 세 항아리의 남은 조약돌과 현재 턴을 상태로 정의해 게임 DP로 승패를 판정한다.
• 백준 25953번 템포럴 그래프

  2023년 7월 2일 · #boj #ps #graph

  백준 25953번 템포럴 그래프 풀이. 시간 T마다 가능한 간선 완화를 한 번씩만 적용하도록 시간별 dist 배열을 분리해 관리한다.
• 백준 2629번 양팔저울

  2023년 7월 2일 · #boj #ps

  백준 2629번 양팔저울 풀이. 추를 왼쪽과 오른쪽에 놓는 경우를 모두 고려해 음수와 양수 무게 상태를 DP로 만든다.
• 백준 27066번 나무 블럭 게임

  2023년 7월 2일 · #boj #ps #greedy

  백준 27066번 나무 블럭 게임 풀이. 정렬 후 가장 큰 블록을 포함하는 경우와 나머지를 합치는 경우를 비교해 최대 점수를 구한다.
• 백준 27068번 이미지 보정 작업

  2023년 7월 2일 · #boj #ps

  백준 27068번 이미지 보정 작업 풀이. 선명도 차이의 허용값을 이분 탐색하고 BFS로 보정해야 하는 구역을 판정한다.
• 백준 9370번 미확인 도착지

  2023년 7월 2일 · #boj #ps #graph

  백준 9370번 미확인 도착지 풀이. 다익스트라로 특정 간선을 지나는 최단 경로가 존재하는 후보 목적지만 걸러낸다.
• 백준 9694번 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

  2023년 7월 2일 · #boj #ps #graph

  백준 9694번 풀이. 최단거리 갱신 시 이전 노드를 함께 저장해 목적지까지의 최단 경로를 복원한다.
• 비트마스크

  2023년 7월 2일 · #ps

  비트마스크 정리. AND, OR, XOR, shift 연산과 원소 추가·삭제·토글, 부분집합 순회 등 PS에서 자주 쓰는 패턴을 요약한다.
• 백준 25406번 식사 계획 세우기

  2022년 9월 11일 · #tree #cpp #greedy #priority-queue #ps #set

  백준 25406번 식사 계획 세우기 풀이. 이전 음식과 과반수 조건을 만족하도록 set과 priority queue로 다음 음식 후보를 관리한다.
• 백준 25402번 트리와 쿼리

  2022년 9월 10일 · #union-find #cpp #ps #tree

  백준 25402번 트리와 쿼리 풀이. 쿼리마다 선택된 노드끼리만 유니온하며 연결된 컴포넌트 크기로 가능한 쌍의 수를 계산한다.
• 프로그래머스 스킬체크 레벨 4

  2022년 6월 22일 · #cpp #programmers #ps

  프로그래머스 스킬체크 레벨 4 응시 기록. 짧은 이미지 중심 후기와 당시의 소감을 남긴 글.
• 백준 2287번 모노디지털 표현

  2022년 6월 21일 · #dp #cpp #ps

  백준 2287번 모노디지털 표현 풀이. 같은 숫자를 i개 써서 만들 수 있는 값 집합을 사칙연산으로 확장하는 DP를 정리한다.
• 백준 19608번 Searching for Strings

  2022년 6월 7일 · #string #cpp #ps

  백준 19608번 Searching for Strings 풀이. 슬라이딩 윈도우의 알파벳 빈도와 해시 중복 제거로 애너그램 substring 개수를 구한다.
• 백준 17228번 아름다운 만영로

  2022년 6월 6일 · #string #cpp #ps

  백준 17228번 아름다운 만영로 풀이. 트리를 DFS로 내려가며 경로 문자열의 롤링 해시를 갱신해 패턴과 일치하는 경로 수를 센다.
• 백준 3033번 가장 긴 문자열

  2022년 6월 4일 · #string #cpp #ps

  백준 3033번 가장 긴 문자열 풀이. 롤링 해시와 이분 탐색으로 중복 부분 문자열이 존재하는 최대 길이를 찾는다.
• 백준 6206번 Milk Patterns

  2022년 6월 4일 · #string #cpp #ps

  백준 6206번 Milk Patterns 풀이. 정수 수열에 롤링 해시를 적용하고 같은 패턴이 K번 이상 등장하는 최대 길이를 찾는다.
• 백준 24525번 SKK 문자열

  2022년 5월 25일 · #prefix-sum #string #cpp #ps

  백준 24525번 SKK 문자열 풀이. S와 K를 가중치로 바꾼 prefix sum에서 같은 값을 갖는 가장 먼 구간을 찾아 조건 문자열 길이를 구한다.
• 백준 11585번 속타는 저녁 메뉴

  2022년 5월 6일 · #string #cpp #ps

  백준 11585번 속타는 저녁 메뉴 풀이. 원형 문자열을 두 번 이어 붙이고 KMP로 일치하는 회전 수를 세어 확률을 구한다.
• 백준 4354번 문자열 제곱

  2022년 5월 5일 · #string #cpp #ps

  백준 4354번 문자열 제곱 풀이. KMP 실패 함수의 마지막 값으로 반복 단위 길이를 구하고 문자열이 몇 번 반복되는지 판정한다.
• 백준 13504번 XOR 합

  2022년 4월 30일 · #trie #cpp #math #ps

  백준 13504번 XOR 합 풀이. 누적 XOR 값을 Trie에 넣고 두 prefix XOR의 최대 조합을 찾아 부분수열 XOR 최댓값을 구한다.
• 백준 13710번 XOR 합 3

  2022년 4월 28일 · #cpp #math #ps

  백준 13710번 XOR 합 3 풀이. 누적 XOR과 비트별 0/1 개수 조합을 이용해 모든 부분수열 XOR 합을 계산한다.
• 백준 2830번 행성 X3

  2022년 4월 28일 · #cpp #math #ps

  백준 2830번 행성 X3 풀이. 각 비트마다 1과 0의 개수를 세고 조합 수를 곱해 모든 쌍의 XOR 합을 구한다.
• 백준 10464번 XOR

  2022년 4월 27일 · #cpp #math #ps

  백준 10464번 XOR 풀이. 1부터 n까지의 XOR 패턴과 prefix XOR 관계를 이용해 구간 XOR 값을 상수 시간에 계산한다.
• 백준 16903번 수열과 쿼리 20

  2022년 4월 26일 · #trie #cpp #ps

  백준 16903번 수열과 쿼리 20 풀이. 이진 Trie에 수를 삽입, 삭제하고 반대 비트를 우선 선택해 XOR 최댓값을 찾는다.
• 백준 5467번 Type Printer

  2022년 4월 25일 · #trie #cpp #ps

  백준 5467번 Type Printer 풀이. Trie를 구성한 뒤 가장 긴 단어 경로를 마지막에 남기도록 출력과 백스페이스 순서를 정한다.
• 백준 3080번 아름다운 이름

  2022년 4월 24일 · #trie #cpp #ps

  백준 3080번 아름다운 이름 풀이. Trie의 자식 노드 개수에 따른 순열 수를 곱해 가능한 이름 배열 수를 계산한다.
• 백준 5446번 용량 부족

  2022년 4월 24일 · #trie #cpp #ps

  백준 5446번 용량 부족 풀이. 지워야 할 파일과 보존 파일을 Trie에 표시해 한 명령으로 삭제 가능한 경로 수를 최소화한다.
• 백준 19585번 전설

  2022년 4월 23일 · #trie #cpp #hash #ps

  백준 19585번 전설 풀이. 색상은 Trie, 닉네임은 set에 저장해 쿼리 문자열을 두 부분으로 나눌 수 있는지 판정한다.
• 백준 16934번 게임 닉네임

  2022년 4월 22일 · #trie #cpp #ps

  백준 16934번 게임 닉네임 풀이. Trie에 닉네임을 삽입하며 처음으로 새로 생기는 prefix를 출력하고 동일 닉네임은 번호를 붙인다.
• 백준 5670번 휴대폰 자판

  2022년 4월 20일 · #trie #cpp #ps

  백준 5670번 휴대폰 자판 풀이. Trie에서 단어 종료 지점과 분기 노드를 기준으로 자동완성에 필요한 평균 입력 횟수를 계산한다.
• 백준 1086번 박성원

  2022년 3월 30일 · #dp #cpp #ps

  백준 1086번 박성원 풀이. 사용한 숫자 집합과 현재 나머지를 상태로 두고, 큰 수를 직접 만들지 않고 나머지 DP로 확률을 구한다.
• 백준 2618번 경찰차

  2022년 3월 29일 · #dp #cpp #ps

  백준 2618번 경찰차 풀이. 두 경찰차가 마지막으로 처리한 사건 번호를 상태로 두고 최소 이동거리와 담당 차량 경로를 복원한다.
• 백준 11689번 GCD(n, k) = 1

  2022년 3월 3일 · #math #cpp #ps

  백준 11689번 GCD(n, k)=1 풀이. 오일러 피 함수와 소인수분해를 이용해 n 이하에서 n과 서로소인 수의 개수를 구한다.
• 백준 24524번 아름다운 문자열

  2022년 3월 1일 · #string #cpp #greedy #ps

  백준 24524번 아름다운 문자열 풀이. 목표 문자열의 각 문자 진행 개수를 관리하며 순서대로 완성 가능한 subsequence 수를 센다.
• 백준 24526번 전화 돌리기

  2022년 3월 1일 · #graph #cpp #ps

  백준 24526번 전화 돌리기 풀이. 그래프를 뒤집고 진입 차수 기반 위상 제거를 수행해 사이클에 연결되지 않는 노드 수를 구한다.
• 백준 24527번 이상한 나라의 갈톤보드

  2022년 3월 1일 · #binary-search #prefix-sum #segment-tree #cpp #imos #ps

  백준 24527번 이상한 나라의 갈톤보드 풀이. 구간 업데이트를 lazy segment tree와 imos 방식으로 각각 풀며 도착 구간 계산을 정리한다.
• 백준 16563번 어려운 소인수분해

  2022년 2월 25일 · #math #cpp #ps

  백준 16563번 어려운 소인수분해 풀이. 각 수의 가장 작은 소인수를 미리 저장해 여러 입력을 빠르게 소인수분해한다.
• 백준 2168번 타일 위의 대각선

  2022년 2월 24일 · #math #cpp #ps

  백준 2168번 타일 위의 대각선 풀이. 가로와 세로 길이, 최대공약수를 이용해 대각선이 지나는 타일 개수를 계산한다.
• 백준 2487번 섞기 순열

  2022년 2월 24일 · #math #cpp #ps

  백준 2487번 섞기 순열 풀이. 순열을 사이클로 분해하고 각 사이클 길이의 최소공배수를 구해 원래 상태로 돌아오는 시점을 찾는다.
• 백준 2981번 검문

  2022년 2월 23일 · #math #cpp #ps

  백준 2981번 검문 풀이. 모든 수의 나머지가 같다는 조건을 인접 차이의 최대공약수와 그 약수 문제로 바꿔 해결한다.
• 백준 16637번 괄호 추가하기

  2022년 2월 21일 · #cpp #ps #simulation

  백준 16637번 괄호 추가하기 풀이. 괄호가 겹치지 않는 모든 배치를 재귀로 만들고, 생성된 식을 앞에서부터 계산한다.
• 백준 15824번 너 봄에는 캡사이신이 맛있단다

  2022년 2월 20일 · #cpp #math #ps

  백준 15824번 너 봄에는 캡사이신이 맛있단다 풀이. 정렬 후 각 원소가 최댓값과 최솟값으로 등장하는 횟수를 거듭제곱으로 계산한다.
• 백준 1014번 컨닝

  2022년 2월 19일 · #dp #cpp #ps

  백준 1014번 컨닝 풀이. 이전 행의 앉은 상태를 비트마스크로 두고 현재 행에서 가능한 배치를 비교하는 DP를 사용한다.
• 백준 22871번 징검다리 건너기 (large)

  2022년 2월 18일 · #dp #cpp #ps

  백준 22871번 징검다리 건너기 풀이. 중간 돌을 거치는 비용의 최댓값을 최소화하도록 가능한 이전 돌들을 비교하는 DP를 정리한다.
• 백준 1700번 멀티탭 스케줄링

  2022년 2월 17일 · #cpp #greedy #ps

  백준 1700번 멀티탭 스케줄링 풀이. 멀티탭이 가득 찼을 때 가장 늦게 다시 쓰이거나 다시 쓰이지 않는 기기를 뽑는 그리디를 설명한다.
• 백준 23797번 개구리

  2022년 2월 17일 · #cpp #ps

  백준 23797번 개구리 풀이. K와 P로 끝나는 개구리 수를 상태처럼 관리하며 합쳐지는 규칙에 따라 필요한 최댓값을 계산한다.
• 백준 11097번 도시 계획

  2022년 2월 13일 · #cpp #floyd #ps #graph

  백준 11097번 도시 계획 풀이. SCC 내부 순환 간선과 SCC 간 필요한 간선을 구성해 조건을 만족하는 도시 계획을 출력한다.
• 백준 2152번 여행 계획 세우기

  2022년 2월 13일 · #dp #graph #cpp #ps

  백준 2152번 여행 계획 세우기 풀이. SCC를 압축하고 시작점에서 도달 가능한 컴포넌트만 따라가며 방문 가능한 도시 수의 최댓값을 구한다.
• 백준 3977번 축구 전술

  2022년 2월 11일 · #cpp #ps #graph

  백준 3977번 축구 전술 풀이. SCC를 구한 뒤 진입 차수가 0인 SCC가 하나뿐인지 확인해 가능한 시작 전술 노드를 출력한다.
• 백준 4013번 ATM

  2022년 2월 11일 · #dp #graph #cpp #ps

  백준 4013번 ATM 풀이. SCC를 압축해 DAG를 만들고 시작 SCC에서 도달 가능한 경로의 최대 수금액을 DP로 계산한다.
• 백준 6543번 그래프의 싱크

  2022년 2월 11일 · #cpp #ps #graph

  백준 6543번 그래프의 싱크 풀이. SCC 압축 그래프에서 나가는 간선이 없는 컴포넌트의 모든 원래 노드를 찾아 출력한다.
• 백준 1199번 오일러 회로

  2022년 2월 8일 · #graph #cpp #ps

  백준 1199번 오일러 회로 풀이. 모든 정점의 차수가 짝수인지 확인하고 Hierholzer 알고리즘으로 간선을 한 번씩 쓰는 회로를 만든다.
• 백준 1948번 임계경로

  2022년 2월 7일 · #graph #cpp #ps

  백준 1948번 임계경로 풀이. 위상 정렬로 최장 시간을 구한 뒤 역방향으로 추적해 임계 경로에 포함되는 간선 수를 센다.
• 백준 2637번 장난감 조립

  2022년 2월 4일 · #dp #graph #cpp #ps

  백준 2637번 장난감 조립 풀이. 위상 정렬로 중간 부품의 기본 부품 필요량을 누적해 완제품에 필요한 기본 부품 개수를 구한다.
• 백준 2848번 알고스팟어

  2022년 2월 4일 · #graph #cpp #ps

  백준 2848번 알고스팟어 풀이. 인접한 단어의 첫 차이로 알파벳 순서 그래프를 만들고 위상 정렬로 모순과 다중 해를 판정한다.
• 백준 3665번 최종 순위

  2022년 2월 4일 · #graph #cpp #ps

  백준 3665번 최종 순위 풀이. 기존 순위의 상대적 방향 간선을 만들고 바뀐 쌍을 뒤집어 위상 정렬로 최종 순위를 구한다.
• 백준 1005번 ACM Craft

  2022년 2월 3일 · #graph #cpp #ps

  백준 1005번 ACM Craft 풀이. 건물 선행 관계를 위상 정렬로 처리하고 목표 건물까지 필요한 최소 완성 시간을 계산한다.
• 백준 1516번 게임 개발

  2022년 2월 3일 · #graph #cpp #ps

  백준 1516번 게임 개발 풀이. 위상 정렬 순서대로 각 건물의 선행 건물 완료 시간 중 최댓값을 반영해 완성 시간을 구한다.
• 백준 1766번 문제집

  2022년 2월 3일 · #graph #cpp #ps

  백준 1766번 문제집 풀이. 진입 차수가 0인 문제를 최소 힙에 넣어 가능한 문제 중 번호가 작은 것부터 푸는 순서를 만든다.
• 백준 2623번 음악프로그램

  2022년 2월 2일 · #graph #cpp #ps

  백준 2623번 음악프로그램 풀이. DFS 기반 위상 정렬과 진행 중 방문 상태를 이용해 가능한 순서와 사이클 여부를 판단한다.
• 백준 1647번 도시 분할 계획

  2022년 2월 1일 · #graph #cpp #ps

  백준 1647번 도시 분할 계획 풀이. MST를 만들되 가장 큰 간선을 제외해 두 마을로 나누는 최소 유지비를 구한다.
• 백준 1944번 복제 로봇

  2022년 2월 1일 · #graph #cpp #ps

  백준 1944번 복제 로봇 풀이. 시작점과 열쇠 사이 최단거리를 BFS로 간선화하고 MST를 만들어 모든 열쇠를 연결한다.
• 백준 2887번 행성 터널

  2022년 2월 1일 · #graph #sort #cpp #ps

  백준 2887번 행성 터널 풀이. x, y, z 좌표별 인접 행성 간선만 후보로 삼아 MST 간선 수를 크게 줄인다.
• 백준 4343번 Arctic Network

  2022년 2월 1일 · #graph #cpp #ps

  백준 4343번 Arctic Network 풀이. 위성 채널 수만큼 네트워크를 분리하도록 MST에서 필요한 마지막 간선 비용을 계산한다.
• 백준 9373번 복도 뚫기

  2022년 2월 1일 · #graph #cpp #ps

  백준 9373번 복도 뚫기 풀이. 센서와 양쪽 벽을 정점으로 보고 MST처럼 연결해 두 벽이 막히는 최소 간격을 찾는다.
• 백준 18185번 라면 사기

  2022년 1월 31일 · #cpp #greedy #ps

  백준 18185번 라면 사기 풀이. 연속한 공장에서 묶어 사는 단가 차이를 이용해 3개, 2개, 1개 구매를 그리디하게 배치한다.
• 백준 1602번 도망자 원숭이

  2022년 1월 29일 · #cpp #floyd #ps

  백준 1602번 도망자 원숭이 풀이. 노드의 지연 시간을 고려해 경유 가능한 노드를 순서대로 확장하며 최단 거리와 최대 지연을 함께 계산한다.
• 백준 1613번 역사

  2022년 1월 26일 · #cpp #floyd #ps

  백준 1613번 역사 풀이. 플로이드 워셜로 사건 간 도달 가능성을 계산해 두 사건의 선후 관계를 판단한다.
• 백준 2610번 회의준비

  2022년 1월 26일 · #cpp #floyd #ps

  백준 2610번 회의준비 풀이. 컴포넌트를 나누고 플로이드 워셜로 각 그룹에서 최대 전달 시간이 가장 작은 대표를 고른다.
• 백준 11657번 타임머신

  2022년 1월 24일 · #bellman-ford #cpp #ps

  백준 11657번 타임머신 풀이. 음의 간선이 있는 그래프에서 벨만 포드 알고리즘으로 최단거리와 음수 사이클을 판정한다.
• 백준 1219번 오민식의 고민

  2022년 1월 24일 · #bellman-ford #cpp #ps

  백준 1219번 오민식의 고민 풀이. 수익을 반영한 벨만 포드와 사이클 전파로 도착지에서 무한히 돈을 벌 수 있는지 판정한다.
• 백준 1738번 골목길

  2022년 1월 24일 · #bellman-ford #cpp #ps

  백준 1738번 골목길 풀이. 목적지까지 이어지는 양의 사이클만 걸러내도록 벨만 포드 변형과 경로 복원을 함께 사용한다.
• 1162번 도로포장

  2022년 1월 22일 · #cpp #dijkstra #ps

  백준 1162번 도로포장 풀이. 도로를 몇 번 포장했는지 상태에 포함한 다익스트라로 K개 이하 도로를 무료화한 최단 거리를 구한다.
• 백준 10217번 KCM Travel

  2022년 1월 22일 · #cpp #dijkstra #ps

  백준 10217번 KCM Travel 풀이. 사용한 비용을 상태로 두고 각 비용에서 가능한 최소 시간을 관리하는 최단 경로 접근을 정리한다.
• 백준 2211번 네트워크 복구

  2022년 1월 18일 · #cpp #dijkstra #ps

  백준 2211번 네트워크 복구 풀이. 1번 노드 기준 다익스트라를 수행하며 각 노드의 부모 간선을 저장해 복구할 네트워크를 만든다.
• 백준 5719번 거의 최단 경로

  2022년 1월 18일 · #graph #cpp #dijkstra #ps

  백준 5719번 거의 최단 경로 풀이. 모든 최단 경로에 포함된 간선을 역추적으로 제거한 뒤 다시 다익스트라를 수행한다.
• 백준 10473번 인간 대포

  2022년 1월 16일 · #cpp #dijkstra #geometry #ps

  백준 10473번 인간 대포 풀이. 시작점, 대포, 목적지를 완전 그래프로 만들고 걷기와 대포 이동 시간을 비교해 다익스트라를 적용한다.
• 백준 15422번 Bumped!

  2022년 1월 16일 · #cpp #dijkstra #ps

  백준 15422번 Bumped! 풀이. 비행기 티켓 사용 전후를 두 그래프 층으로 나누고 0비용 간선을 연결해 최단 시간을 구한다.
• 백준 17435번 합성함수와 쿼리

  2022년 1월 8일 · #data-structure #cpp #ps

  백준 17435번 합성함수와 쿼리 풀이. f의 1, 2, 4, 8회 적용 결과를 sparse table로 저장해 합성함수 값을 로그 시간에 구한다.
• 백준 2213번 트리의 독립집합

  2022년 1월 6일 · #dp #cpp #ps #tree

  백준 2213번 트리의 독립집합 풀이. 부모 선택 여부에 따라 노드 선택을 나누는 트리 DP와 선택 노드 복원 과정을 정리한다.
• 백준 2248번 이진수 찾기

  2022년 1월 5일 · #dp #prefix-sum #cpp #ps

  백준 2248번 이진수 찾기 풀이. 자릿수와 1의 개수 제한별 경우의 수를 DP로 세고, prefix count로 I번째 수를 구성한다.
• 백준 2533번 사회망 서비스

  2021년 12월 29일 · #dp #cpp #ps #tree

  백준 2533번 사회망 서비스 풀이. 트리에서 부모의 얼리어답터 여부에 따라 현재 노드 선택 가능성을 나누는 DP를 정리한다.
• 백준 17131번 여우가 정보섬에 올라온 이유

  2021년 12월 12일 · #segment-tree #cpp #ps #sweeping

  백준 17131번 여우가 정보섬에 올라온 이유 풀이. 좌우 스위핑으로 각 별보다 높은 별의 개수를 구하고 곱해 별자리 경우를 계산한다.
• 백준 13925번 수열과 쿼리 13

  2021년 12월 11일 · #segment-tree #cpp #ps

  백준 13925번 수열과 쿼리 13 풀이. 더하기, 곱하기, 대입 쿼리를 ax+b 형태의 lazy 값으로 합성해 처리한다.
• 백준 5419번 북서풍

  2021년 12월 11일 · #data-structure #segment-tree #cpp #ps #sweeping

  백준 5419번 북서풍 풀이. 좌표 압축과 세그먼트 트리를 이용해 정렬된 순서에서 조건을 만족하는 점 쌍의 수를 센다.
• 백준 13537번 수열과 쿼리 1

  2021년 12월 9일 · #sort #segment-tree #cpp #ps

  백준 13537번 수열과 쿼리 1 풀이. 머지 소트 트리의 정렬된 구간 벡터에서 upper_bound로 K보다 큰 원소 개수를 구한다.
• 백준 7469번 K번째 수

  2021년 12월 9일 · #binary-search #sort #segment-tree #cpp #ps

  백준 7469번 K번째 수 풀이. 머지 소트 트리로 구간 내 특정 값 이하의 개수를 구하고 이분 탐색으로 K번째 수를 찾는다.
• 백준 1395번 스위치

  2021년 12월 8일 · #segment-tree #cpp #ps

  백준 1395번 스위치 풀이. 켜진 스위치 개수와 반전 lazy 값을 저장해 구간 토글과 개수 질의를 처리한다.
• 백준 10999번 구간 합 구하기 2

  2021년 12월 7일 · #segment-tree #cpp #ps

  백준 10999번 구간 합 구하기 2 풀이. Lazy propagation으로 구간 업데이트를 미뤄 두고 필요한 순간에 합을 반영한다.
• 백준 12844번 XOR

  2021년 12월 7일 · #segment-tree #cpp #ps

  백준 12844번 XOR 풀이. XOR의 결합법칙과 교환법칙을 이용해 구간 XOR 쿼리와 lazy XOR 업데이트를 처리한다.
• 백준 5676번 음주 코딩

  2021년 12월 7일 · #segment-tree #cpp #ps

  백준 5676번 음주 코딩 풀이. 수를 양수, 음수, 0으로만 변환해 구간 곱의 부호를 세그먼트 트리로 빠르게 판단한다.
• 백준 1572번 중앙값

  2021년 12월 6일 · #segment-tree #cpp #ps

  백준 1572번 중앙값 풀이. 값 범위에 대한 세그먼트 트리를 만들고 슬라이딩 윈도우의 K번째 값을 찾아 중앙값 합을 구한다.
• 백준 2104번 부분배열 고르기

  2021년 12월 6일 · #divide-and-conquer #segment-tree #cpp #ps

  백준 2104번 부분배열 고르기 풀이. 구간 최솟값의 인덱스를 기준으로 분할 정복하며 부분배열 합과 최솟값의 곱을 최대화한다.
• 백준 2517번 달리기

  2021년 12월 5일 · #data-structure #segment-tree #cpp #ps

  백준 2517번 달리기 풀이. 실력을 좌표 압축한 뒤 세그먼트 트리로 앞선 선수 중 자신보다 강한 사람 수를 계산한다.
• 백준 7578번 공장

  2021년 12월 5일 · #segment-tree #cpp #ps

  백준 7578번 공장 풀이. 두 생산 라인의 같은 기계 위치를 매핑하고 세그먼트 트리로 교차하는 연결선 수를 센다.
• 백준 2243번 사탕상자

  2021년 12월 3일 · #binary-search #segment-tree #cpp #ps

  백준 2243번 사탕상자 풀이. 맛별 사탕 개수 합을 세그먼트 트리에 저장하고, 순위 기반 탐색으로 원하는 사탕 맛을 찾는다.
• 백준 9345번 디지털 비디오 디스크(DVDs)

  2021년 12월 3일 · #segment-tree #cpp #ps

  백준 9345번 디지털 비디오 디스크 풀이. 구간의 최솟값과 최댓값을 세그먼트 트리에 저장해 해당 범위의 DVD가 모두 있는지 확인한다.
• 백준 3653번 영화 수집

  2021년 12월 2일 · #segment-tree #cpp #ps

  백준 3653번 영화 수집 풀이. DVD 위치를 넉넉한 인덱스 영역에 배치하고 세그먼트 트리로 위에 쌓인 DVD 개수를 센다.
• 백준 1280번 나무 심기

  2021년 12월 1일 · #segment-tree #cpp #ps

  백준 1280번 나무 심기 풀이. 왼쪽과 오른쪽 나무의 개수와 거리 합을 세그먼트 트리에 저장해 새 나무의 비용을 계산한다.
• 백준 3006번 터보소트

  2021년 12월 1일 · #segment-tree #cpp #ps

  백준 3006번 터보소트 풀이. 세그먼트 트리로 남아 있는 원소 수를 세며 1, N, 2, N-1 순서의 이동 횟수를 계산한다.
• 백준 1517번 버블 소트

  2021년 11월 30일 · #segment-tree #cpp #ps

  백준 1517번 버블 소트 풀이. 실제 버블 정렬 대신 세그먼트 트리로 아직 정렬되지 않은 앞쪽 원소 수를 세어 swap 횟수를 구한다.
• 백준 6549번 히스토그램에서 가장 큰 직사각형

  2021년 11월 29일 · #divide-and-conquer #segment-tree #cpp #ps

  백준 6549번 히스토그램에서 가장 큰 직사각형 풀이. 최소 높이 막대를 기준으로 구간을 나누고 세그먼트 트리로 최솟값 인덱스를 찾는다.
• 백준 11505번 구간 곱 구하기

  2021년 11월 28일 · #segment-tree #cpp #ps

  백준 11505번 구간 곱 구하기 풀이. 세그먼트 트리에 구간 곱을 저장하고 업데이트 시 리프부터 부모 노드까지 값을 다시 계산한다.
• 백준 12837번 가계부 (Hard)

  2021년 11월 28일 · #segment-tree #cpp #ps

  백준 12837번 가계부 (Hard) 풀이. 값 변경이 아니라 누적 추가가 일어나는 구간 합 질의를 세그먼트 트리로 처리한다.
• 백준 2357번 최솟값과 최댓값

  2021년 11월 28일 · #segment-tree #cpp #ps

  백준 2357번 최솟값과 최댓값 풀이. 구간 최솟값 트리와 최댓값 트리를 각각 만들어 RMQ 질의에 답한다.
• 백준 10775번 공항

  2021년 11월 27일 · #union-find #cpp #ps

  백준 10775번 공항 풀이. 도킹 가능한 가장 큰 게이트를 유니온 파인드로 추적해 비행기를 최대한 많이 배치한다.
• 백준 17398번 통신망 분할

  2021년 11월 27일 · #union-find #cpp #ps

  백준 17398번 통신망 분할 풀이. 제거되지 않는 간선을 먼저 합치고, 끊은 간선을 역순으로 복구하며 분할 비용을 누적한다.
• 백준 2042번 구간 합 구하기

  2021년 11월 27일 · #segment-tree #cpp #ps

  백준 2042번 구간 합 구하기 풀이. 세그먼트 트리로 구간 합 질의와 단일 값 업데이트를 모두 O(log N)에 처리한다.
• 백준 9938번 방 청소

  2021년 11월 26일 · #union-find #cpp #ps #python

  백준 9938번 방 청소 풀이. 연결된 서랍 집합의 남은 공간 수를 루트에 저장해 각 술병을 보관할 수 있는지 빠르게 판단한다.
• 백준 11085번 군사 이동

  2021년 11월 25일 · #union-find #cpp #ps

  백준 11085번 군사 이동 풀이. 간선을 수용량 내림차순으로 연결하며 출발지와 도착지가 이어지는 순간의 최소 수용량을 찾는다.
• 백준 14868번 문명

  2021년 11월 25일 · #graph #union-find #cpp #ps

  백준 14868번 문명 풀이. BFS로 문명을 확장하고 인접한 문명을 유니온 파인드로 합치며 모두 연결되는 해를 찾는다.
• 백준 3197번 백조의 호수

  2021년 11월 25일 · #graph #union-find #cpp #ps

  백준 3197번 백조의 호수 풀이. 물 확산을 BFS로 진행하고 녹아 연결된 영역을 유니온 파인드로 묶어 백조가 만나는 날을 구한다.
• 백준 14003번 가장 긴 증가하는 부분 수열 5

  2021년 11월 24일 · #dp #binary-search #cpp #ps

  백준 14003번 가장 긴 증가하는 부분 수열 5 풀이. O(N log N) LIS 과정에서 이전 값을 추적해 실제 증가 부분 수열을 복원한다.
• 백준 10942번 팰린드롬?

  2021년 11월 23일 · #dp #cpp #ps

  백준 10942번 팰린드롬 풀이. 양끝 문자가 같고 내부 구간이 팰린드롬인지 여부를 메모이제이션해 여러 질의에 답한다.
• 백준 1509번 팰린드롬 분할

  2021년 11월 23일 · #dp #cpp #ps

  백준 1509번 팰린드롬 분할 풀이. 팰린드롬 구간 판정과 최소 분할 개수 DP를 결합해 문자열을 나누는 최솟값을 구한다.
• 백준 2162번 선분 그룹

  2021년 11월 23일 · #union-find #cpp #geometry #ps

  백준 2162번 선분 그룹 풀이. 선분 교차 판정과 유니온 파인드를 결합해 그룹 개수와 가장 큰 그룹 크기를 계산한다.
• 백준 2342번 Dance Dance Revolution

  2021년 11월 23일 · #dp #cpp #ps

  백준 2342번 Dance Dance Revolution 풀이. 양발의 위치와 진행 인덱스를 상태로 두어 발판을 밟는 최소 힘을 메모이제이션한다.
• 백준 17387번 선분 교차 2

  2021년 11월 22일 · #cpp #geometry #ps

  백준 17387번 선분 교차 2 풀이. CCW와 끝점 대소 비교를 이용해 일반 교차와 일직선상 겹침을 모두 판정한다.
• 백준 7579번 앱

  2021년 11월 21일 · #dp #cpp #ps

  백준 7579번 앱 풀이. 비용을 DP 인덱스로 삼아 각 비용으로 확보 가능한 최대 메모리를 저장하고 최소 비용을 찾는다.
• 백준 11049번 행렬 곱셈 순서

  2021년 11월 20일 · #divide-and-conquer #dp #cpp #ps

  백준 11049번 행렬 곱셈 순서 풀이. 시작과 끝 행렬 범위를 상태로 두고 분할 지점별 곱셈 비용의 최솟값을 메모이제이션한다.
• 백준 17404번 RGB거리 2

  2021년 11월 20일 · #dp #cpp #ps

  백준 17404번 RGB거리 2 풀이. 첫 집의 색을 고정한 뒤 마지막 집과 겹치지 않도록 색칠 비용의 최솟값을 DP로 구한다.
• 백준 14464번 소가 길을 건너간 이유 4

  2021년 11월 19일 · #priority-queue #binary-search #cpp #greedy #ps #set

  백준 14464번 소가 길을 건너간 이유 4 풀이. 닭이 도와줄 수 있는 소 중 종료 시간이 가장 빠른 소를 고르는 그리디 매칭을 설명한다.
• 백준 16562번 친구비

  2021년 11월 19일 · #union-find #cpp #ps

  백준 16562번 친구비 풀이. 친구 관계를 유니온 파인드로 묶고 각 집합의 최소 친구비를 합산해 예산 가능 여부를 판단한다.
• 백준 1717번 집합의 표현

  2021년 11월 19일 · #union-find #cpp #ps

  백준 1717번 집합의 표현 풀이. 경로 압축을 사용하는 유니온 파인드의 union과 find 연산을 구현해 집합 포함 여부를 판정한다.
• 백준 4195번 친구 네트워크

  2021년 11월 19일 · #union-find #cpp #ps

  백준 4195번 친구 네트워크 풀이. 이름을 인덱스로 매핑하고 루트에 집합 크기를 저장하는 유니온 파인드로 네트워크 크기를 출력한다.
• 백준 1715번 카드 정렬하기

  2021년 11월 18일 · #priority-queue #cpp #greedy #ps

  백준 1715번 카드 정렬하기 풀이. 가장 작은 카드 묶음 두 개를 반복해서 합치는 최소 힙 기반 그리디 전략을 정리한다.
• 백준 2014번 소수의 곱

  2021년 11월 18일 · #priority-queue #cpp #ps

  백준 2014번 소수의 곱 풀이. 최소 힙에서 작은 곱을 꺼내 다시 소수들과 곱하며 중복과 오버플로우를 관리한다.
• 백준 2696번 중앙값 구하기

  2021년 11월 18일 · #priority-queue #cpp #ps

  백준 2696번 중앙값 구하기 풀이. 최대 힙과 최소 힙의 균형을 유지해 입력이 들어올 때마다 중앙값을 출력한다.
• 백준 10649번 프리스비

  2021년 11월 16일 · #dp #bitmasking #cpp #ps

  백준 10649번 프리스비 풀이. 선택된 소 집합의 안정도를 비트마스크 DP로 저장하고, 소를 위나 아래에 놓는 경우를 비교한다.
• 백준 1176번 섞기

  2021년 11월 16일 · #dp #bitmasking #cpp #ps

  백준 1176번 섞기 풀이. 마지막으로 세운 학생과 지금까지 세운 학생 집합을 상태로 두어 조건을 만족하는 순서의 수를 센다.
• 백준 1029번 그림 교환

  2021년 11월 15일 · #dp #bitmasking #cpp #ps

  백준 1029번 그림 교환 풀이. 현재 소유자, 구매 가격, 방문한 예술가 집합을 상태로 두어 가능한 최대 거래 인원 수를 구한다.
• 백준 1480번 보석 모으기

  2021년 11월 15일 · #dp #bitmasking #cpp #ps

  백준 1480번 보석 모으기 풀이. 가방 번호, 현재 가방 무게, 담은 보석 집합을 상태로 관리해 담을 수 있는 보석 수의 최댓값을 찾는다.
• 백준 16991번 외판원 순회 3

  2021년 11월 15일 · #dp #bitmasking #cpp #ps

  백준 16991번 외판원 순회 3 풀이. 좌표 사이의 유클리드 거리를 비용으로 사용해 비트마스크 TSP를 적용한다.
• 백준 2320번 끝말잇기

  2021년 11월 15일 · #dp #bitmasking #cpp #ps

  백준 2320번 끝말잇기 풀이. 마지막 문자와 사용한 단어 집합을 상태로 두고 얻을 수 있는 최고 점수를 메모이제이션한다.
• 백준 1102번 발전소

  2021년 11월 14일 · #dp #bitmasking #cpp #ps

  백준 1102번 발전소 풀이. 켜진 발전소 상태를 비트마스크로 표현하고, 목표 개수 이상을 켜는 최소 추가 비용을 탐색한다.
• 백준 3056번 007

  2021년 11월 14일 · #dp #bitmasking #cpp #ps

  백준 3056번 007 풀이. 미션 할당 여부를 비트마스크로 두고 각 요원에게 미션을 배정하는 최대 성공 확률을 DP로 계산한다.
• 백준 1600번 말이 되고픈 원숭이

  2021년 11월 12일 · #graph #cpp #ps

  백준 1600번 말이 되고픈 원숭이 풀이. 말처럼 점프한 횟수를 BFS 상태에 포함해 장애물이 있는 격자에서 최단 이동을 구한다.
• 백준 2098번 외판원 순회

  2021년 11월 12일 · #dp #bitmasking #cpp #ps

  백준 2098번 외판원 순회 풀이. 현재 도시와 방문 도시 비트마스크를 상태로 두고 모든 도시를 방문하는 최소 비용을 메모이제이션한다.
• 백준 14442번 벽 부수고 이동하기 2

  2021년 11월 10일 · #graph #cpp #ps

  백준 14442번 벽 부수고 이동하기 2 풀이. 현재까지 부순 벽의 개수를 BFS 상태로 포함해 K번 이하로 벽을 부수는 최단 거리를 찾는다.
• 백준 16933번 벽 부수고 이동하기 3

  2021년 11월 10일 · #graph #cpp #ps

  백준 16933번 벽 부수고 이동하기 3 풀이. 낮과 밤, 벽을 부순 횟수, 대기 횟수를 상태로 기록해 조건이 있는 최단 경로를 탐색한다.
• 백준 9328번 열쇠

  2021년 11월 10일 · #graph #bitmasking #cpp #ps #simulation

  백준 9328번 열쇠 풀이. 열쇠 보유 상태가 바뀌면 이전에 막혔던 위치도 다시 탐색할 수 있게 처리해 문서 개수를 센다.
• 백준 1194번 달이 차오른다, 가자.

  2021년 11월 9일 · #graph #bitmasking #cpp #ps

  백준 1194번 달이 차오른다, 가자 풀이. 열쇠 보유 상태를 비트마스크로 기록해 같은 위치라도 다른 열쇠 상태면 다시 탐색한다.
• 백준 2001번 보석 줍기

  2021년 11월 9일 · #graph #bitmasking #cpp #ps

  백준 2001번 보석 줍기 풀이. 보유 보석 집합을 비트마스크로 관리하며 같은 섬과 같은 보석 상태의 중복 방문을 막는다.
• 백준 12094번 2048 (Hard)

  2021년 11월 7일 · #backtracking #cpp #ps #simulation

  백준 12094번 2048 (Hard) 풀이. 보드를 회전해 한 방향 이동만 구현하고, 변화 없는 이동과 도달 불가능한 최댓값을 가지치기한다.
• 백준 1562번 계단 수

  2021년 11월 6일 · #dp #bitmasking #cpp #ps

  백준 1562번 계단 수 풀이. 길이, 마지막 숫자, 사용한 숫자 비트마스크를 상태로 두어 모든 숫자를 포함하는 계단 수를 센다.
• 백준 1799번 비숍

  2021년 11월 2일 · #backtracking #cpp #ps

  백준 1799번 비숍 풀이. 대각선 점유 여부를 이용하고 흑백 칸을 분리해 탐색량을 줄이는 백트래킹 전략을 정리한다.
• 백준 2263번 트리의 순회

  2021년 11월 1일 · #divide-and-conquer #cpp #ps #tree

  백준 2263번 트리의 순회 풀이. inorder와 postorder의 인덱스 범위만 넘기며 루트와 서브트리 크기를 찾아 preorder를 출력한다.
• 백준 17136번 색종이 붙이기

  2021년 10월 29일 · #backtracking #cpp #ps

  백준 17136번 색종이 붙이기 풀이. 붙일 수 있는 색종이 크기와 남은 장수를 확인하며 되돌리기 가능한 백트래킹으로 최소 장수를 구한다.
• 백준 1182번 부분수열의 합

  2021년 10월 27일 · #backtracking #cpp #ps

  백준 1182번 부분수열의 합 풀이. 각 원소를 선택하거나 선택하지 않는 모든 경우를 백트래킹으로 탐색해 목표 합의 개수를 센다.
• 백준 1759번 암호 만들기

  2021년 10월 27일 · #backtracking #cpp #ps

  백준 1759번 암호 만들기 풀이. 알파벳 선택 여부를 백트래킹하며 모음 1개 이상, 자음 2개 이상 조건을 만족하는 암호를 출력한다.
• 백준 1987번 알파벳

  2021년 10월 27일 · #backtracking #graph #cpp #ps

  백준 1987번 알파벳 풀이. 지금까지 사용한 알파벳을 기록하면서 상하좌우로 이동 가능한 경로의 최대 길이를 DFS로 찾는다.
• 백준 2096번 내려가기

  2021년 10월 27일 · #dp #cpp #ps

  백준 2096번 내려가기 풀이. 현재 칸에 올 수 있는 이전 칸의 최댓값과 최솟값만 유지해 메모리 제한 안에서 DP를 수행한다.
• 백준 2580번 스도쿠

  2021년 10월 27일 · #backtracking #cpp #ps

  백준 2580번 스도쿠 풀이. 행, 열, 3x3 박스의 사용 숫자를 기록하고 빈 칸을 백트래킹으로 채워 유효한 보드를 찾는다.
• 백준 17071번 숨바꼭질 5

  2021년 10월 26일 · #graph #cpp #ps

  백준 17071번 숨바꼭질 5 풀이. 수빈이의 도달 시간을 홀짝 상태로 나누어 기록하고, 움직이는 동생과 만날 수 있는 시점을 판정한다.
• 백준 2294번 동전 2

  2021년 10월 26일 · #dp #cpp #ps

  백준 2294번 동전 2 풀이. 각 금액을 만드는 데 필요한 최소 동전 수를 저장하고 현재 동전을 사용하는 경우와 비교해 갱신한다.
• 백준 1525번 퍼즐

  2021년 10월 24일 · #graph #hash #string #cpp #ps

  백준 1525번 퍼즐 풀이. 퍼즐 상태를 문자열 키로 표현하고 map에 이동 횟수를 저장하며 BFS로 목표 상태까지의 최단 이동을 찾는다.
• 백준 11967번 불켜기

  2021년 10월 23일 · #graph #cpp #ps

  백준 11967번 불켜기 풀이. 불은 켜졌지만 아직 갈 수 없는 방을 따로 기록하고, 새로 접근 가능해지는 방을 BFS에 반영한다.
• 백준 16920 확장 게임

  2021년 10월 23일 · #graph #cpp #ps

  백준 16920번 확장 게임 풀이. 플레이어별 큐를 따로 두고 각자의 확장 거리만큼 차례대로 BFS를 진행해 점령 칸 수를 계산한다.
• 백준 4179번 불!

  2021년 10월 19일 · #graph #cpp #ps

  백준 4179번 불! 풀이. 불의 확산 시간과 지훈이의 이동 시간을 따로 BFS로 구해 불보다 먼저 도달 가능한 탈출 경로를 찾는다.
• 백준 5014번 스타트링크

  2021년 10월 19일 · #graph #cpp #ps

  백준 5014번 스타트링크 풀이. 엘리베이터가 갈 수 있는 층을 BFS로 탐색하며 범위와 방문 시간을 관리해 최소 버튼 횟수를 구한다.
• 백준 9466번 텀 프로젝트

  2021년 10월 19일 · #graph #cpp #ps

  백준 9466번 텀 프로젝트 풀이. 학생 선택 그래프에서 사이클을 이루는 학생만 팀으로 분류하고 나머지 인원을 계산한다.
• 백준 3015번 오아시스 재결합

  2021년 10월 16일 · #cpp #ps #stack

  백준 3015번 오아시스 재결합 풀이. 같은 키가 연속되는 사람 수를 스택에 함께 저장해 서로 볼 수 있는 쌍을 효율적으로 계산한다.
• 백준 2493번 탑

  2021년 10월 15일 · #cpp #ps #stack

  백준 2493번 탑 풀이. 스택으로 왼쪽에 있는 더 높은 탑 후보를 관리하며 각 탑의 레이저를 수신하는 위치를 찾는다.
• 백준 9251번 LCS

  2021년 10월 14일 · #dp #string #ps #python

  백준 9251번 LCS 풀이. 두 문자열의 접두사 조합마다 최장 공통 부분 수열 길이를 저장하는 2차원 DP를 정리한다.
• 백준 1918번 후위 표기식

  2021년 10월 13일 · #ps #python #stack

  백준 1918번 후위 표기식 풀이. 연산자 우선순위와 괄호 처리를 스택으로 관리해 중위 표기식을 후위 표기식으로 변환한다.
• 백준 1422번 숫자의 신

  2021년 10월 10일 · #sort #greedy #ps #python

  백준 1422번 숫자의 신 풀이. 두 수를 이어 붙였을 때 더 큰 순서를 비교 기준으로 삼고, 가장 큰 수를 추가로 반복해 최대 숫자를 만든다.
• 백준 3482번 Labyrinth

  2021년 10월 7일 · #graph #ps #python #tree

  백준 3482번 Labyrinth 풀이. 미궁을 트리처럼 보고 두 번의 BFS로 가장 멀리 떨어진 두 칸 사이의 거리를 구한다.
• 백준 1167번 트리의 지름

  2021년 10월 5일 · #graph #ps #python #tree

  백준 1167번 트리의 지름 풀이. 임의의 노드에서 가장 먼 노드를 찾고, 그 노드에서 다시 가장 먼 거리까지 탐색하는 두 번의 DFS를 설명한다.
• 백준 2407번 조합

  2021년 10월 2일 · #dp #ps #python

  백준 2407번 조합 풀이. 큰 조합 값을 직접 계산하기 위해 파스칼의 삼각형 점화식을 활용하는 방법을 정리한다.
• 백준 9465번 스티커

  2021년 10월 2일 · #dp #ps #python

  백준 9465번 스티커 풀이. 위아래 스티커 선택 상태를 나눠 각 위치를 선택했을 때 가능한 최대 점수를 누적한다.
• 백준 12865번 평범한 배낭

  2021년 9월 30일 · #dp #ps #python

  백준 12865번 평범한 배낭 풀이. 무게별 최대 가치를 저장하는 DP 테이블로 0/1 배낭 문제의 최적값을 계산한다.
• 백준 12851번 숨바꼭질 2

  2021년 9월 29일 · #graph #ps #python

  백준 12851번 숨바꼭질 2 풀이. BFS에서 같은 최단 시간으로 도달하는 경우도 큐에 반영해 최단 시간과 경우의 수를 함께 구한다.
• 백준 13549번 숨바꼭질 3

  2021년 9월 29일 · #graph #ps #python

  백준 13549번 숨바꼭질 3 풀이. 순간이동 비용이 0인 조건을 우선 처리하기 위해 우선순위 큐 기반 최단 경로 탐색을 사용한다.
• 백준 13913번 숨바꼭질 4

  2021년 9월 29일 · #graph #ps #python

  백준 13913번 숨바꼭질 4 풀이. BFS로 최단 시간을 구하면서 이전 위치를 함께 저장하고, 도착점에서 경로를 역추적한다.
• 백준 17928번 오큰수

  2021년 9월 29일 · #ps #python #stack

  백준 17928번 오큰수 풀이. 오른쪽의 후보 값을 스택으로 관리해 각 원소의 다음 큰 수를 O(N)에 찾는 방법을 정리한다.
• 백준 1011번 Fly me to the Alpha Centauri

  2021년 9월 26일 · #ps #python

  백준 1011번 Fly me to the Alpha Centauri 풀이. 이동 거리 패턴이 제곱수를 기준으로 대칭을 이룬다는 점을 이용해 최소 이동 횟수를 구한다.
• 백준 11404번 플로이드

  2021년 9월 25일 · #floyd #ps #python

  백준 11404번 플로이드 풀이. 중간 정점을 하나씩 허용하며 모든 도시 쌍의 최단 비용을 갱신하는 플로이드 워셜 알고리즘을 설명한다.
• 백준 11660번 구간 합 구하기 5

  2021년 9월 25일 · #dp #ps #python

  백준 11660번 구간 합 구하기 5 풀이. 2차원 누적합을 만들어 직사각형 영역 합을 포함-배제 방식으로 빠르게 계산한다.
• 백준 1932번 정수 삼각형

  2021년 9월 25일 · #dp #ps #python

  백준 1932번 정수 삼각형 풀이. 각 칸에 도달 가능한 왼쪽 위와 오른쪽 위 경로 중 더 큰 합을 누적하는 DP를 정리한다.
• 백준 9935번 문자열 폭발

  2021년 9월 24일 · #string #ps #python #stack

  백준 9935번 문자열 폭발 풀이. 문자열을 한 번 훑으며 스택의 끝이 폭발 문자열과 일치할 때 제거하는 선형 시간 접근을 정리한다.
• 백준 2206번 벽 부수고 이동하기

  2021년 9월 23일 · #graph #ps #python

  백준 2206번 벽 부수고 이동하기 풀이. 벽을 부쉈는지 여부를 BFS 상태에 포함해 한 번만 벽을 부수는 최단 경로를 탐색한다.
• 백준 1504번 특정한 최단 경로

  2021년 9월 19일 · #dijkstra #ps #python

  백준 1504번 특정한 최단 경로 풀이. 다익스트라를 여러 번 실행해 v1, v2를 지나는 두 경로 후보 중 더 짧은 값을 선택한다.
• 백준 1753번 최단경로

  2021년 9월 19일 · #dijkstra #ps #python

  백준 1753번 최단경로 풀이. 우선순위 큐를 사용한 다익스트라로 시작 정점에서 모든 정점까지의 최단 거리를 구한다.
• 백준 1629번 곱셈

  2021년 9월 18일 · #divide-and-conquer #ps #python

  백준 1629번 곱셈 풀이. 거듭제곱을 반으로 나눠 재사용하는 분할 정복과 모듈러 연산으로 O(log N)에 값을 계산한다.
• 백준 11725번 트리의 부모 찾기

  2021년 9월 15일 · #graph #ps #python

  백준 11725번 트리의 부모 찾기 풀이. 루트 1번에서 한 번의 DFS를 수행하며 각 노드의 부모를 동시에 기록한다.
• 백준 16953번 A → B

  2021년 9월 14일 · #greedy #ps #python

  백준 16953번 A → B 풀이. A에서 B로 확장하지 않고 B에서 1 제거와 2 나누기를 역으로 적용해 가능 여부와 연산 횟수를 구한다.
• 백준 1107번 리모컨

  2021년 9월 12일 · #brute-force #ps #python

  백준 1107번 리모컨 풀이. 만들 수 있는 채널을 완전 탐색하고, 숫자 버튼 입력 횟수와 +/- 이동 횟수의 최솟값을 비교한다.
• 백준 10026번 적록색약

  2021년 9월 7일 · #graph #ps #python

  백준 10026번 적록색약 풀이. 일반 시야와 적록색약 시야를 각각 BFS로 탐색해 색 영역의 개수를 비교한다.
• 백준 2178번 미로 탐색

  2021년 9월 6일 · #graph #ps #python

  백준 2178번 미로 탐색 풀이. BFS로 한 칸씩 이동하며 방문 칸에 거리 값을 누적해 최단 경로 길이를 계산한다.
• 백준 1541번 잃어버린 괄호

  2021년 9월 5일 · #greedy #ps #python

  백준 1541번 잃어버린 괄호 풀이. 첫 마이너스 이후의 덧셈 묶음을 모두 빼면 최솟값이 되는 그리디 아이디어를 정리한다.
• 백준 9663번 N-Queen

  2021년 7월 15일 · #backtracking #ps #python #divide-and-conquer

  백준 9663번 N-Queen 풀이. 1차원 배열로 퀸의 위치를 표현하고 열과 대각선 충돌을 검사하는 백트래킹 방법을 설명한다.
• 백준 15649번 N과 M

  2021년 7월 12일 · #backtracking #ps #python #divide-and-conquer

  백준 N과 M 시리즈 풀이. 방문 여부, 오름차순 조건, 중복 제거 조건을 조합해 여러 백트래킹 문제를 한 흐름으로 정리한다.
• 백준 1012번 유기농 배추

  2021년 7월 11일 · #graph #ps #python

  백준 1012번 유기농 배추 풀이. 배추가 이어진 영역을 그래프의 연결 요소로 보고, 새 영역을 발견할 때마다 필요한 지렁이 수를 센다.
• 백준 1074번 Z

  2021년 7월 11일 · #divide-and-conquer #ps #python

  백준 1074번 Z 풀이. 전체 배열을 실제로 만들지 않고, 목표 좌표가 속한 사분면만 따라가며 방문 순서를 누적한다.
• 백준 2579번 계단 오르기

  2021년 7월 9일 · #dp #ps #python

  백준 2579번 계단 오르기 풀이. 마지막 계단을 반드시 밟되 세 계단 연속 금지를 만족하도록 두 가지 이전 상태를 비교하는 DP를 정리한다.
• 백준 7576번 토마토

  2021년 7월 9일 · #graph #ps #python

  백준 7576번 토마토 풀이. 처음 익은 토마토들을 모두 큐에 넣고 BFS로 날짜를 누적해 전체가 익는 최소 시간을 계산한다.
• 백준 11724번 연결 요소의 개수

  2021년 7월 8일 · #graph #ps #python

  백준 11724번 연결 요소의 개수 풀이. 방문하지 않은 노드에서 탐색을 시작할 때마다 연결 요소 하나를 세는 DFS/BFS 방식을 정리한다.
• 백준 11726번 2xn 타일링

  2021년 7월 8일 · #dp #ps #python

  백준 11726번 2xn 타일링 풀이. 마지막에 붙이는 타일 모양을 기준으로 n-1, n-2 경우를 더하는 DP 점화식을 설명한다.
• 백준 1764번 듣보잡

  2021년 7월 8일 · #hash #ps #python

  백준 1764번 듣보잡 풀이. 두 명단의 교집합을 set으로 구해 탐색 비용을 줄이고 결과를 정렬해 출력한다.
• 백준 11279번 최대 힙

  2021년 7월 5일 · #priority-queue #ps #python

  백준 11279번 최대 힙 풀이. Python의 최소 힙에 음수 값을 넣어 최대 힙처럼 동작하게 만드는 구현 방법을 정리한다.
• 백준 18870번 좌표 압축

  2021년 7월 5일 · #sort #hash #ps #python

  백준 18870번 좌표 압축 풀이. 정렬, 중복 제거, 딕셔너리 매핑을 이용해 각 좌표보다 작은 서로 다른 좌표의 개수를 빠르게 구한다.
• 백준 1018번 체스판 다시 칠하기

  2021년 7월 4일 · #brute-force #ps #python

  백준 1018번 체스판 다시 칠하기 풀이. 가능한 8x8 영역을 모두 확인하고 시작 색에 따른 칠해야 할 칸 수의 최솟값을 구한다.
• 백준 10989번 수 정렬하기 3

  2021년 7월 4일 · #sort #ps #python

  백준 10989번 수 정렬하기 3 풀이. 입력 수의 범위가 작다는 조건을 이용해 카운팅 배열로 메모리 사용을 줄여 정렬한다.
• 백준 12015번 가장 긴 증가하는 부분 수열 2

  2021년 7월 1일 · #dp #binary-search #ps #python

  백준 12015번 가장 긴 증가하는 부분 수열 2 풀이. 길이별 최소 끝값을 유지하고 이분 탐색으로 O(N log N)에 LIS 길이를 구한다.
• 백준 11053번 가장 긴 증가하는 부분 수열

  2021년 6월 29일 · #dp #ps #python

  백준 11053번 가장 긴 증가하는 부분 수열 풀이. 각 위치를 마지막 원소로 삼는 LIS 길이를 앞쪽 원소들과 비교해 갱신한다.
• 백준 1912번 연속합

  2021년 6월 27일 · #dp #ps #python

  백준 1912번 연속합 풀이. 누적합이 음수가 되는 지점에서 시작점을 바꾸는 카데인 알고리즘의 핵심 아이디어를 설명한다.
• 백준 2293번 동전 1

  2021년 6월 26일 · #dp #ps #python

  백준 2293번 동전 1 풀이. 동전을 하나씩 추가하며 각 금액을 만드는 경우의 수를 갱신하는 DP 점화식을 정리한다.
• 백준 11399번 ATM

  2021년 5월 25일 · #greedy #ps #python

  백준 11399번 ATM 풀이. 인출 시간이 짧은 사람부터 배치해 누적 대기 시간을 최소화하는 정렬 기반 그리디 풀이를 설명한다.
• 백준 2606번 바이러스

  2021년 5월 25일 · #graph #ps #python

  백준 2606번 바이러스 풀이. 1번 컴퓨터와 연결된 노드를 DFS/BFS로 탐색해 감염되는 컴퓨터 수를 계산한다.
• 백준 11047번 동전 0

  2021년 5월 24일 · #greedy #ps #python

  백준 11047번 동전 0 풀이. 동전 가치가 배수 관계라는 조건을 이용해 가장 큰 동전부터 사용하는 그리디 전략을 정리한다.
• 백준 2630번 색종이 만들기

  2021년 5월 24일 · #divide-and-conquer #ps #python

  백준 2630번 색종이 만들기 풀이. 종이를 네 조각으로 재귀 분할하며 한 색으로만 이루어진 영역의 개수를 센다.
• 백준 1992번 쿼드트리

  2021년 5월 23일 · #divide-and-conquer #ps #python

  백준 1992번 쿼드트리 풀이. 이미지를 네 영역으로 나누고 같은 값으로 압축 가능한지 확인하는 재귀 분할 방식을 설명한다.
• 백준 1697번 숨바꼭질

  2021년 5월 22일 · #graph #ps #python

  백준 1697번 숨바꼭질 풀이. 현재 위치에서 -1, +1, *2 이동을 BFS로 탐색하며 각 위치까지 걸린 시간을 기록한다.
• 백준 1260번 DFS와 BFS

  2021년 5월 21일 · #graph #ps #python

  백준 1260번 DFS와 BFS 풀이. 재귀 기반 DFS와 deque 기반 BFS를 구현하고, 방문 순서를 조건에 맞게 처리하는 방법을 정리한다.
• 백준 1149번 RGB거리

  2021년 5월 20일 · #dp #ps #python

  백준 1149번 RGB거리 풀이. 각 집을 특정 색으로 칠할 때 이전 집의 다른 색 비용 중 최솟값을 누적하는 DP 점화식을 정리한다.
• 백준 9095번 1, 2, 3 더하기

  2021년 5월 19일 · #ps #python

  백준 9095번 1, 2, 3 더하기 풀이. N을 1, 2, 3으로 줄여 가며 경우의 수를 나누는 재귀적 사고를 설명한다.
• 백준 1092번 배

  2021년 5월 18일 · #greedy #ps #python

  백준 1092번 배 풀이. 가장 강한 크레인이 가장 무거운 박스를 맡도록 정렬해 매 단계 최선의 선택을 하는 그리디 접근을 정리한다.
• 백준 1041번 주사위

  2021년 5월 17일 · #greedy #ps #python

  백준 1041번 주사위 풀이. 서로 마주보지 않는 면 조합의 최솟값을 구하고, 보이는 면의 개수 규칙에 맞춰 합을 계산한다.