꾸준함

백준 월간 향유회 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 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1513 문제 지문으로부터 메모이제이션을 적용할 수 있는 상태값은 현재 위치(y, x), 방문한 오락실 개수, 그리고 직전에 방문한 오락실 번호임을 유추할 수 있습니다.따라서 네 상태값을 기준으로 DP를 적용하여 풀면 되는 문제였습니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/12865 전형적인 Knapsack DP 문제였습니다.주의할 점은 동전 2 문제와 달리 각 물건은 하나씩 존재한다는 점입니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/12852 연산을 하는 횟수의 최솟값은 DP를 통해 간단하게 구할 수 있는 문제였습니다.문제는 " N을 1로 만드는 방법에 포함되어 있는 수"를 출력하는 것이었는데 이는 DP에 사용했던 cache 배열을 역추적하며 구할 수 있었습니다.테스트해 본 결과 top-down 방식으로 구현할 경우 N이 100만 일 때 stackoverflow가 발생하는 것 같은데 AC를 받는 것으로 보아 데이터 추가가 필요해 보입니다.  개발환경:Visual Studio 2022 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~