전체 글 썸네일형 리스트형 BOJ 1201 - NMK (P3) 사용 알고리즘 Greedy-Style Constructive 풀이 BOJ 27244의 확장판이다. https://sehujeong.tistory.com/20에서 설명한 그룹을 확장해보자. 그룹의 크기가 최대 K이고, 그 개수가 M개면 똑같이 풀 수 있을 것이다. 따라서 N을 K+a1+a2+...+a_M-1 꼴로 나타낼 수 있으면 27244와 똑같다.(1k; if(!(m+k-1 더보기 BOJ 27244 - Монотонная подпоследовательность (G1) 사용 알고리즘 Greedy-Style Constructive 풀이 문제를 아주 짧게 요약하면 다음과 같다. N, K (k; if(k*k 더보기 BOJ 16964 - DFS 스페셜 저지 (G3) 사용 알고리즘 DFS 풀이 주어진 방문 순서가 DFS의 성질을 만족한다면 DFS라고 볼 수 있을 것이다. 트리에서 DFS의 성질 중 하나는, 어떤 정점을 루트로 하는 서브트리는 그 서브트리상의 모든 정점을 DFS로 방문한다는 것이다. 또한 이 성질은 모든 정점에서 성립하므로, 각 정점에서 이 성질이 성립하는지만 확인하는 것으로 충분하다. 이를 간단하게 확인하는 방법은, 서브트리의 정점 개수와 주어진 순서대로 방문했을 때의 서브트리의 정점 개수가 같은지를 확인하면 된다. 이 방법이 왜 가능한지를 생각해보자. 방문 순서가 올바른 DFS가 아니라면 방문 순서가 잘못된 지점이 있을 것이다. 그 지점에서는, DFS를 리프 노드까지 진행하지 않고 중간에 다른 곳으로 이동했을 것이다. 위 그림에서 잘못된 순서인 빨간.. 더보기 BOJ 22952 - permutation making (S3) https://www.acmicpc.net/problem/22952 22952번: permutation making 수열 $P$의 원소들 중 서로 다른 값은 $0,3,4$로 3종류가 있고, 총 3개로 $\frac{N}{2} + 1$개 이하이다. www.acmicpc.net 사용 알고리즘 constructive 풀이 N/2+1이 의미하는 것은, P에서 어떤 값을 가지는 정점이 2개씩 존재하도록 만들란 뜻이다. 어떤 값을 가지는 정점이 2개 존재한다는 것은, 어떤 값이 2개 나오도록 만들란 소리다. 어떤 i, j에서 P[i] = P[j]이려면 ∑k=1iAk≡∑k=1jAk 가 mod N에서 성립하면 되며, 이는 $$ \sum_{k=i+1}^{j}.. 더보기 BOJ 4013 - ATM (P2) https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 사용 알고리즘 SCC + 위상정렬 DP 풀이 ATM에서 현금을 인출할 때, 어떤 정점에서 사이클이 존재한다면 그 사이클을 쭉 돌면서 사이클에 속하는 모든 정점의 ATM을 이용할 수 있다. 따라서 사이클 내의 정점들을 묶어 생각할 수 있고, 하나의 SCC로 묶어줄 수 있음을 알 수 있다. 예제 그래프이다. 위에 적힌 숫자는 ATM에서 인출할 수 있는 현금이고, 색칠된 숫자는 그 정점에.. 더보기 KOI 2023 2차 대회 중등부 후기 현재 가채점 결과가 나왔다. 중간에 충전선에 아이패드가 걸려서 카메라가 넘어진 것 때문에 부정행위에 걸리지 않는 이상 3위는 고정일듯 하다. 타임라인 1줄요약 1->2->3긁기->4긁기->3->4긁기 아래부터 나와있는 풀이의 내용은 오류가 있을 수 있다. (부등호 실수, 조건 빠뜨림 등등?) 0:00 ~ 8:26 : 1번 해결 +100점 1번은 문제해석이 중요하다. 문제의 조건을 다 보지 않으면 예제 2의 답이 이상하게 느껴지기 때문이다. 문제를 요약하면 다음과 같다. 스케이트를 속력 0에서 시작하여, N개의 지점에서 아래와 같은 속력 조건에 맞춰 속력을 조정한 후 마지막에는 속력 0으로 끝날 때, 각 부분에서의 속력의 합의 최댓값은? (=N개의 지점에서의 속력의 합) 조건 1 : 배열 A = (a1, .. 더보기 BOJ 2613 - 숫자구슬 (G2) 알고리즘 분류 Dynamic Programming Greedy Binary Search Parametric Search 풀이 풀이 1: Greedy, O(N^3) N이 최대 300이므로 O(N^3)까지 고려할 수 있다. 따라서 임의의 구간 [l, r]을 골라서, [l,r]의 합이 최댓값이 되게 할 수 있는지를 빠르게 구할 수 있으면 된다. [l,r]의 합을 x라 하자. 배열의 처음부터 시작해서 값을 연속해서 더해나간다. 이 때, 합이 x 초과일 경우 새로 그룹을 갱신한다. (단, 하나의 값이 x 초과일경우는 불가능하다.) [l,r]에 대해서는 예외처리를 해준다. 위 알고리즘은 x가 최댓값이 되게 하면서 그룹의 크기를 최소화하는 그리디적인 방법이다. 만약 위 알고리즘대로 만든 그룹의 개수가 m보다 크다면,.. 더보기 2023년도 국제정보올림피아드 국대 후보생 선발 후기 원래 안쓸려 했는데 붙어버려서 대충 후기를 남기기로 했다. 1. 1차 1차는 4월쯤에 했던거 같다. 수학 또는 정보 관련 상을 최대 3개까지 적을 수 있었고, 자소서도 3문항에 200 400 400자였나? 짧아서 크게 무리는 아니었다. 상은 koi 2022 1차 은 2차 동 (중등부) 랑 nypc2021 1214 동상 2개만 적었다. 자소서는 그냥 수학에서 스스로 알아냈던 것 몇개만 써서 냈다. (그렇게 어려운건 아님) 2. 온라인 문제풀이 그렇게 1차를 붙으면 온라인에서 1달정도? 동안 문제 12개를 풀어야 했다. 대충 문제 리스트를 보니까 어려워보이진 않아서 미루고 미뤘다. (사실 영재학교 자소서랑 기간이 겹치기 때문) 그러다가 1주쯤 남았을 때 뭔가 늦은거 같다 싶어서 조금씩 풀기 시작했다. 대부분.. 더보기 이전 1 ··· 8 9 10 11 12 13 다음 목록 더보기
