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를 두 개 만들어서 하..

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

정말 기가막히도록 대단한 문제라 생각된다. 문제는 아래와 같다. 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..

UCPC 2021 본선 D번 문제이다. 본선은 정말 괴수들만 진출하는 곳이 맞긴 한가보다. UCPC 본선 중에서 가장 쉬운 문제들 중 하나라고 한다. https://www.acmicpc.net/problem/22876 22876번: 츠바메가에시 "츠바메가에시"(つばめがえし)는 일본의 검사 "사사키 코지로"가 날아가는 제비를 베었다고 전해지는 검 초식의 이름이다. 기록상으로는 세 번 연속 칼질을 했다고 전해지나, 실제로 기술을 재 www.acmicpc.net 처음에 이 문제에서 tree 배열의 범위를 잘못 생각하여 계속 맞왜틀을 하였다... 의식의 흐름 및 해설 / 테스트케이스 첨부 처음에는 단순히 매 순간의 최댓값 3번을 구하면 된다고 생각하여 세그먼트트리를 이용하여 구현하였다. 주의할 점은 좌표의 범위..

KOI 2014 초등부, 중등부, 고등부 모든 부문에 출제된 문제이다. 초등부 입장에선 꽤나 어려웠을 것 같은 문제. https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 의식의 흐름 및 해설 시계, 반시계의 표현으로 헷갈리게 표현했지만, 결국은 a->b의 방향으로, a>b일 경우 a->(b+N)의 방향으로 간다는 점만 생각하면 된다. 우리를 자주 괴롭히는 원형(circular) 문제이다. 원형으로 문제가 ..

문제 https://www.acmicpc.net/problem/15897 15897번: 잘못 구현한 에라토스테네스의 체 성원이는 오늘 이산수학 수업 시간에 에라토스테네스의 체에 대해 배웠다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. 성원이는 이 방법에 너 www.acmicpc.net 꽤 어렵게 다가온 수학문제이다. N이 1e9이므로 O(N)은 시간초과가 발생한다. 어떻게 해결해야 할까? Harmonic Lemma (조화수열의 성질) 예시로 N=6인 경우를 들어보자. j의 값은 i의 값이 더해지므로, i의 값이 횟수에 영향을 준다. 맨 처음에 j는 디폴트값으로 1이므로, 1+(N-1)/i의 값이 횟수가 됨을 확인할 수 있다. 그러나, 아직까지는 아래 O(N) ..

백준 플랫폼에서 류호석배 알고리즘 코딩테스트가 열려 있어서 한번 참가해보았다. https://www.acmicpc.net/contest/view/666 제3회 류호석배 알고리즘 코딩 테스트 www.acmicpc.net 당시에 4문제를 해결하였고, 3번이 꽤나 어려웠던 기억이 있다. 중간중간에 저녁식사, 운동 등으로 잠깐 탈주했긴 했는데, 5시간 풀집중했어도 3번을 해결할 수 있었을지는 미지수. 다음날에 난이도 티어를 구경해봤는데 생각보다 높게 매겨져 있어서 놀랐던 문제셋이었다. 나는 대체로 다른 사람들에 비해 티어를 좀 후하게 주는 편 (의도한 것이 아니다) 이었는데, 이번엔 내가 다른 사람들에 비해 박하게 티어를 매긴 편이었어서 놀랐다. 문제는 역시 알고리즘 대가인 분께서 출제하셔서 그런지 꽤 괜찮았었..

푹 쉴까 아니면 코테를 응시할까 고민하다가 au0504님이 3시쯤에 코테를 응시한다길래 나도 한 번 응시해본 대회이다. https://www.acmicpc.net/contest/view/658 가희와 함께 하는 2회 코딩 테스트 www.acmicpc.net +) 1회 코딩테스트 후기는 아래 주소에서 볼 수 있다. https://kth990303.tistory.com/66 [210523] 가희와 함께하는 1회 코딩테스트 후기 그룹연습 시간과 대회 시간이 겹쳐서 응시할 생각이 없었는데, aru0504님이 응시한다고 하셔서 1~2문제만 풀어보고 넘기려다가 중간에 문제가 안풀려 오기가 생겨 도전해본 대회이다. https://www.acmi kth990303.tistory.com 뒤늦게 응시한 대회인데도 5등을 ..