kth990303의 코딩 블로그

고인물들 사이에선 웰노운이라길래 풀어봤는데, 엄청 어렵진 않지만, 이게 어떻게 웰노운인가... 싶은 문제. 처음 문제를 보면 단순 레이지세그를 돌리면 되는거 아닌가 싶어 쉽게 생각했는데, 그렇지 않다. 문제는 아래와 같다. https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 의식의 흐름 및 해설 처음에는 단순히 update_lazy를 두 개 만들어서 하..

나름 유명한 문제인데, 내가 아직 이걸 안풀었다는 사실을 알고 시도해본 문제. 내가 treeDp에 약해서 그런건진 모르겠는데 생각보다 좀 틀렸다. (2회 WA, 3회째 AC) https://www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net tree dp 중에선 꽤나 웰노운이라 해서 포스팅해보려 한다. 의식의 흐름 및 해설 트리에서의 노드를 포함하는지의 여부에 따라 최댓값이 달라지는 흔한 treedp 유형이다. 그럼에도 불구하고,..

아이디어는 크게 어렵지 않으나, 시간이 상당히 빡빡한 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/19700 19700번: 수업 키가 188cm, 154cm인 학생들을 한 팀으로, 키가 180cm, 161cm인 학생들을 한 팀으로, 키가 172cm인 학생을 혼자 팀으로 묶으면 총 3개의 팀을 구성할 수 있다. 더 적은 갯수의 팀으로 학생들을 묶을 수 있 www.acmicpc.net 의식의 흐름 및 해설 팀에서 자신보다 키가 큰 학생들이 Ki명 이상이면 수업을 째버리겠다는 굉장히 이상한 수강생들만 존재하는 수업이다. 나중에 사회생활은 어떻게 하려는거지 ㄷㄷ 이는 자신보다 키가 큰 학생이 Ki-1명 이하여야 한다는 소리이며, 키큰 순서대로 등수를 매길 때, Ki ..

UCPC 2021 예선 E번으로 나왔던 문제이다. 대회 당시에 lazy segment tree 느낌이 팍팍 들어서 일단 보류하고 다른 문제로 넘어갔던 기억이 나는데, 넘어가길 잘했던 문제. 상당히 시간이 오래 걸리며, 구현량도 꽤 있는 편이었다. 또한, 그래프가 unimodal하고, 기울기가 같은 구간이 존재하므로 ternary_search (삼분탐색)을 이용하기까지 해야 하는 문제였다. 이분탐색으로도 가능하다는데, 잘은 모르겠다. 문제는 아래와 같다. https://www.acmicpc.net/problem/22355 22355번: 말뚝 첫 번째 줄에는 말뚝의 개수 $N$, 만족해야 하는 UCPC 농장의 아름다움 $K$가 주어진다. $(1 \leq N \leq 100\ 000, 1 \leq K \leq..

문제를 풀다가 너무 어려워서 힌트를 접하고 신박한 점화식으로 풀 수 있다는 것을 알아챈 후에 바텀업으로 AC를 받았다. (나중에 포스팅해볼 듯?) 난 항상 dp는 탑다운으로 푸는데, sparse_table을 이용해야 하는 dp는 탑다운을 좀 어려워하는 경향이 있어서, 이번 문제는 탑다운으로 풀어야지 하고 탑다운도 시도해보는데 쏟아지는 WA... 탑다운으로 푸신 분이 딱 한분 보이길래 그 분 풀이코드를 봤는데도, 내 WA 코드랑 별 다른점을 못느끼겠어서 도대체 어디가 문제일까... 하고 봤는데 알고보니 MAX 범위를 늘려주면 AC였다. 신기한건 조건문으로 N을 넘어가지 않게 설정을 해주었는데도 MAX범위를 늘려줬더니 AC였다는 것이다. 1시간 삽질의 이유가 MAX범위때문이었다니... 앞으론 그냥 MAX 범..

정말 기가막히도록 대단한 문제라 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 대충 생각나는 건 수학, 그래프 알고리즘이 생각나지 않는가? 좀 더 생각해보면 MST와 dfs로 연결지을 수 있다. 의식의 흐름 및 해설 이긴 사람은 천국으로 떠나고, 진 사람이 경기를 계속해서 이어갈 수 있는 특이한 룰이다. 즉, 사람 수가 N명일 때, 경기는 N-1번 진행된다. 시청률의 합이 최대가 되도록 해야 하며..

예전에 AC받았다가, 데이터가 추가되면서 WA로 바뀐 문제를 오늘 한번 다시 도전해봤다. https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 난이도가 상당함에도, Solve수가 상당히 많은 문제. kks227님의 블로그에서 SCC 예제문제이기도 하고, 애초에 scc + topology 연습문제로 좋은 문제이기 때문에 많이 풀린 것이 아닐까 예상된다. 오랜만에 scc를 풀어본 것이라 간단하게 해설을 써보겠다. 의식의 흐름 및 해설 단방..

요즘 웹개발 공부를 하느라 백준을 많이 풀지 못해서 풀어본 문제. https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 생긴게 트리dp, DFS처럼 생겨서 해결해보려 한 문제이다. 의식의 흐름 및 해설 사실 맨 처음에 생각난 것은 '인접행렬과 그래프' 이다. 즉, 아래 문제가 먼저 떠오른 것이다. https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,0..

월간 코드 챌린지 시즌3 9월 3번으로 출제된 문제이다. 처음엔 4.2점, 다음엔 12.5점, 20.8점을 얻고 한참 고민하여 만점을 받아 풀이를 작성해본다. https://programmers.co.kr/learn/courses/30/lessons/86053 코딩테스트 연습 - 금과 은 운반하기 어느 왕국에 하나 이상의 도시들이 있습니다. 왕국의 왕은 새 도시를 짓기로 결정하였습니다. 해당 도시를 짓기 위해서는 도시를 짓는 장소에 금 a kg과 은 b kg이 전달되어야 합니다. 각 도시에는 programmers.co.kr 접근 방법 T가 딱히 10^5라 이분탐색을 떠올리기 어려웠을 수 있다. 그러나 어차피 운반하는데에 걸리는 최소 시간을 묻는 문제이며, 이는 결정여부를 따지는 문제로 충분히 이분탐색을 ..

프로그래머스에서 진행하는 위클리 챌린지 7주차 문제이다. https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 꽤 재밌는 문제였다. 프로그래머스 레벨2에 존재하는 문제이다. 이 문제 풀면서 느낀 점은... 프로그래머스 레벨2 범위가 생각보다 넓은 것 같다. 월간 코드 챌린지 시즌3 9월의 2번 문제랑, 이 문제랑 동급이라 생각되지 않는데, 둘이 같은 level 2 라는 것이 신기할 따름이다. 아무튼 간단하게 후기를 ..