꾸준함

A. 백준 33990번 3대 512단순 구현 B. 백준 33991번 전철 통학민수가 역 i에 걸어가서 도착하는 데 걸리는 시간은 맨해튼 거리 공식에 따라 |X − X_i∣+ |Y −Y_i| 분역 i의 전철은 0, Ti, 2Ti, 3Ti,…분에 도착하므로, 민수가 도착 시간 Ai​분에 가장 가까우면서도 그 이후 도착하는 전철 시각 K_i는 ⌈T_i / A_i​​⌉ * T_i​세 개의 역에 대해 각각 이 값을 계산한 뒤 min⁡{K1, K2, K3}이 가장 빠른 탑승 시간 C. 백준 33992번 사막 탐험두 가지 방법 중 소모 체력이 더 작은 쪽이 답 직접 경로: 원과 선분이 교차한다면 “전체 거리 – 원 내부 구간 길이”만큼 소모하고, 교차하지 않으면 전체 거리만큼 소모 오아시스 우회 경로: A에서 ..

백준 33701번 새천년관단순 구현 문제 백준 33702번 비밀번호DFS와 비트마스크를 결합한 백트래킹으로 그래프 상의 모든 해밀토니안 경로를 세는 문제 백준 33703번 건덕이의 돌탑하노이 탑 이동 문제와 달리 `중간에 있는 돌도 한 번에 꺼낼 수 있다`는 제약 완화 덕분에어떤 방석에서 가장 큰 돌을 제외한 모든 돌은 언제든지 단 한 번의 이동으로 꺼낼 수 있고꺼낸 돌을 놓을 때에도 빈 방석 또는 더 큰 돌이 있는 방석 위에만 놓으면 되므로 그 방석 내 정렬이 자동으로 보장됨 위 두 가지를 이용하면, 개별 돌 하나를 세 번째 방석에 놓기까지 필요한 이동 횟수를 돌 크기별로 합산하는 방식으로 해를 구할 수 있음맨 밑의 돌이 아니라면 한 번에 꺼낼 수 있으므로, 돌 k를 꺼내는 데는 그 위에 있는 더..

백준 33674번 하늘에서 떨어지는 N개의 별각 점 i에서 청소 없이 f일간 별이 쌓이면 각 점의 누적 별은 f × s_i폭발은 별의 개수가 K를 초과할 경우 발생하므로, 각 점에서 안정하게 유지하기 위해서는 f × s_i ≤ K 를 만족해야 함따라서 각 점 i에 대해 f ≤ floor(K / s_i) 이어야 함모든 점에 대해 동시에 만족시키려면 `f ≤ min_{1≤ i ≤ N} floor(K / s_i)` 가 됨해당 값을 m이라고 정의했을 때, 한 청소 사이에 연속해서 최대 m일 동안 별 쌓기를 안전하게 할 수 있음 D일을 m일 간격으로 나누면, 필요한 청소 횟수는 ceil(D / m) - 1초기 상태는 이미 0이므로 첫 구간은 청소할 필요 없음  백준 33675번 L-트로미노 타일링 N이 홀수인 경..

백준 월간 향유회 2025. 01. 대회 문제들이 올라와서 풀어봤습니다.문제들이 제 기준 쉽지 않았기 때문에 실제 대회에 참가했다면 최대 2 솔이었을 것 같습니다.마지막 문제인 XOR 머신은 제 역량으로는 도저히 못 푸는 문제인 것 같아 나중에 고수님들의 해설을 보고 풀어야 할 것 같습니다. 백준 33272번 TAIDADA이 문제의 핵심은 `어떤 수 x를 골랐을 때, x와 x ⊕ K 두 수는 동시에 고를 수 없다`는 점 이를 그래프로 해석하면, 정점이 1부터 M인 그래프에서 x와 (x ⊕ K)를 간선으로 연결한다고 할 때 인접 정점을 동시에 고를 수 없는 집합을 찾는 문제  백준 33273번 multiple sequence이차원 dp를 사용하는 문제였고 알고리즘은 다음과 같습니다.x_i 기준으로 오름차순..

문제 링크입니다: https://www.acmicpc.net/problem/7469 좌표 압축과 퍼시스턴트 세그먼트 트리를 이용하는 문제였습니다.퍼시스턴트 세그먼트 트리 관련해서는 justicehui님 블로그를 참고하시면 될 것 같습니다.https://justicehui.github.io/medium-algorithm/2020/02/29/PST/ Persistent Segment Tree서론 어떤 자료구조가 “persistent하다”라는 것은, 상태의 변화가 생기더라도 과거 상태를 모두 보존하고 있다는 것을 의미합니다. Persistent Segment Tree(PST)는 세그먼트 트리의 갱신 과정을 모두 저justicehui.github.io 알고리즘은 다음과 같습니다.1. 배열 a의 값들이 [-10^..

문제 링크입니다: https://www.acmicpc.net/problem/1017 소수 관련된 문제이므로 에라토스테네스의 체와 이분 매칭을 통해 풀 수 있는 문제였습니다.저도 처음에 백트래킹으로 접근했다가 TLE가 발생했던 문제입니다 ㅠ 알고리즘은 다음과 같습니다.1. nums[0]과 합쳤을 때 소수를 이루는 nums[i]를 매칭합니다.2. 남은 수들로 이분 그래프를 만드는데 왼쪽 집합은 홀수인 수들, 오른쪽 집합은 짝수인 수들로 구성하며 간선은 두 수의 합이 소수일 때 연결시킵니다.3. 이분 그래프에서 최대 매칭을 찾아서 모든 노드가 매칭에 포함되는지 확인합니다.3.1 매칭의 크기가 남은 노드의 절반이라면 모든 수를 짝지을 수 있다는 의미입니다.  개발환경:Visual Studio 2017 지적, 조..

문제 링크입니다: https://www.acmicpc.net/problem/27989 맥스 펜윅 트리를 활용하는 문제였습니다. 알고리즘은 다음과 같습니다.1. cache는 수열 A를 오름차순으로 정렬한 배열입니다.2. 수열 A를 순회하며 이분탐색을 통해 현재 A[i]가 cache에 위치한 인덱스를 찾습니다.2.1 +1을 하는 이유는 A는 0-인덱스인 반면 펜윅 트리는 1-인덱스이기 때문입니다.3. A[i]보다 작은 모든 값들에 대해 현재까지 계산된 최대 부분합을 구합니다.4. 3번에서 구한 값과 A[i]를 합치면 현재 인덱스까지의 최대 부분합을 구할 수 있습니다. 해당 값을 펜윅 트리의 idx 위치에 업데이트합니다.5. 2 ~ 4번 과정을 반복한 뒤 N번째 인덱스에 대해 쿼리를 수행하면 답을 구할 수 있..

문제 링크입니다: https://www.acmicpc.net/problem/1344 문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 구간, A팀 득점 수, B팀 득점 수임을 유추할 수 있습니다.따라서 세 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/17837 문제에서 주어진 대로 풀면 되는 문제였습니다.저는 같은 칸에 여러 개의 말이 위치할 수 있고 쌓인 순서를 토대로 로직이 달라질 수 있기 때문에 stack 자료구조를 사용하여 말이 쌓인 순서를 표현했습니다,. * moveDir[4]를 {1, 0}이 아닌 {0, 1}로 해놓고 맞왜틀 이러고 있었네요... 아까운 내 시간 개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1535 전형적인 Knapsack DP 문제였습니다.세준이의 체력이 0이어도 기쁨을 못 느낀다는 것이 핵심이었습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~