구사과

[2016.11.02 초판][2017.10.05 트리와 쿼리 7/11 추가]https://www.acmicpc.net/contest/scoreboard/195 시간이 남을때마다 하긴 했는데... 너무 힘든 연습이었다 ㅠㅠ 아주 간략하게 풀이를 설명한다. 트리와 쿼리 2 Sparse table로 level ancestor를 빠르게 구할 줄 안다면, 간단한 케이스 분석으로 풀 수 있다. 트리와 쿼리 1 / 3 Heavy Light Decomposition으로 풀 수 있다. 1번의 경우 range max segment tree, 3번의 경우 std::set으로 해결 가능하다. 어렵지 않고 개념도 유용하니 모른다면 배워보자. https://blog.anudeep2011.com/heavy-light-decompo..

(9/30 초판) (9/30 ~ 10/10 PDF 연습 문제 17/22개 해결. 나머지는 시험 끝나고 시작할 것 같습니다.) (자료 출처는 이 사이트 내부 어딘가. 난 혜아한테 받아서 잘 모른다) 수학적 귀납법이란? 어떠한 명제 $P(1), P(2), P(3), \cdots$ 가 다음 두 성질을 만족한다고 하자. * (기저 조건) $P(1)$ 이 참이다. * (귀납 조건) $n \geq 1$ 일 때, $P(1), P(2), \cdots P(n)$이 참이면, $P(n+1)$이 참이다. 그렇다면 $P(1), P(2), P(3), \cdots$가 모두 참이다. 왜? 사실 위에 적은 수학적 귀납법을 "강한 수학적 귀납법" 이라고 부르고, 조금 더 약한 폼의 수학적 귀납법을 "수학적 귀납법" 이라 한다. 진짜 "..

(2017.9.26 : 초판)(2017.9.30 : J번을 제외한 모든 문제의 풀이를 추가했습니다. 블로그에 LaTeX 조판을 설치했고, G번 문제 풀이를 시험적으로 전부 LaTeX 수식으로 변경했습니다. J번 문제를 포함해서 앞으로 올라오는 글들은 모두 다 예쁘게 조판되어서 올라갈 예정이에요!)(2017.9.30 : J번의 풀이가 추가되었습니다.) Scoreboard잘해서 좋당 ㅋㅋ Problems / Solution sketch대충 난이도 순으로 정렬했다. 사실 5번째부터 10번째까지는 이견이 있을 수도 있고 나도 잘 모르겠지만 (…) 푼 사람 수와 개인적인 의견 등을 감안하여 적당히 정렬했다.마음에 들었던 문제는 D / G / J였다. B도 풀이가 상당히 재미있다.K. RegistrationH. M..

1. 도어맨굉장히 간단한 O(N) 그리디 풀이도 있는 거 같은데 난 잘 모르겠어서 DP로 해결했다. DP[i] = (1 ~ i번 사람이 모두 럽에 들어갔을 때 더 넣을 수 있는 사람의 수) 라고 정의하자. 두가지 케이스가 있다. * 첫번째 사람을 클럽에 영영 안 넣고 두번째 사람부터만 계속 추가. 이 방법으로 K명이 추가로 들어갔다면 DP[i] = K가 가능해진다. * 두번째 사람 이후를 K번 정도 더 넣고, 첫번째 사람을 추가. 차이에 문제가 생기지 않는다면 DP[i] = DP[i + K + 1] + K + 1가 가능해 진다. 모든 K에 대해서 대충 시뮬레이션한 후, 시뮬레이션 과정에서 문제가 없었으면 값을 갱신해주면 된다. 이런 식으로 DP 테이블을 채우면 DP[0]이 답이 된다. 잘 구현하면 O(N..

1. 지뢰찾기디스크립션에 매우 중요한 내용이 누락되어 있는데, 외곽선만 숫자가 공개되어 있으며 외곽선이 아닌 부분은 숫자가 전혀 써져있지 않다. 고로 외곽선과 붙어있는 영역에만 지뢰가 있을 수도 없을 수도 있는 것이고, 그렇지 않은 n-4 * n-4 영역에는 지뢰가 무조건 있다고 가정해도 된다. 최대화가 목표이기 때문이다. 외곽선과 붙어있는 영역의 지뢰를 최대화하라고 하지만, 사실 지뢰의 개수를 유일하게 결정할 수 있다. 모서리에 있는 지뢰를 제외한 모든 지뢰는 주위 3개의 셀에게 노출된다. 즉 모서리 지뢰를 제거하면 나머지 지뢰의 수는 적혀있는 숫자의 합 / 3 이라는 것이다. 모서리에 있는 지뢰는 모서리에 있는 숫자로 존재 여부를 결정할 수 있으니, 이를 결정하고 나머지 숫자의 합을 세주면 된다. n

1. Arrays 두 행과 열을 바꾼다는 것이 무슨 뜻인지 먼저 생각해 보자. 각각의 행과 열에 대해서 순열 P[i]와 Q[i]를 정의하자. P[i] = (현재 i번 행의 원래 위치), Q[i] = (현재 i번 열의 원래 위치) 라고 하면, 두 행을 바꾸는 것은 단순히 P[i]와 P[j]를 바꾸고, 열을 바꾸는 것은 단순히 Q[i]와 Q[j]를 바꾸는 것이다. 고로 우리가 주어진 연산으로 할 수 있는 것은 P와 Q를 임의의 순열로 섞는 것이니, A와 B가 닮았다 (alike) 는 것은 A[P[i]][Q[j]] = B[i][j] 를 만족하는 순열 P, Q가 존재한다는 것과 동치이다. 모든 수가 다르니, 각 수가 A에서 어떤 위치, B에서 어떤 위치에 있는지를 유일하게 결정할 수 있다. 즉 P[i] = j,..

1. 전구편의상 왼쪽 스위치와 오른쪽 전구의 번호가 1 2 3 4.. 처럼 순서대로 되어 있다고 하자. p[i] = (왼쪽 i번 스위치를 눌렀을 때 켜진 오른쪽 전구의 번호) 라 하자. 전선이 교차하지 않게 왼쪽에서 {i1, i2, i3, ... ik} 스위치를 켰다는 것은, p[i1] < p[i2] < p[i3] < ... < p[ik] 라는 것과 동치이다. 이렇게 최대 개수의 스위치를 켜는 것은, 최장 증가 부분 수열 (LIS) 문제와 동일하다. 이는 동적 계획법으로 O(N^2)에 찾고 역추적도 할 수 있다. (만약 방법을 모른다면, dp[i] = i번 수에서 끝나는 최대 길이의 LIS라 정의하고 생각해 보자.)왼쪽 스위치와 오른쪽 전구의 번호가 실제로 1 2 3 4가 아니라는 것이 문제인데, 그냥 ..

1. 생존자이 문제를 푸는 데 있어서 아주 중요한 아이디어는, 바로 이것이 스케줄링 문제라는 것을 발견하는 것이다. 다음과 같은 문제를 생각해 보자. * N개의 작업이 있다. 각 작업은 S_i 시간 동안 연속적으로 해야 하며, P_i + S_i 시간 내에 완수해야 한다. 작업이 돌아가는 시간을 최대화하여라.이 문제는 원래 문제랑 완전히 동일한 문제일까? 한번 문제의 조건들을 다시 잘 살펴보자. * S_i 시간 만큼 허기를 채울 수 있고 (작업을 돌릴 수 있고), P_i 시간 전에 시작해야 한다는 것은 P_i + S_i 시간 전에 끝내야 한다는 것과 동치이다. * 허기를 채울 수 있는 시간동안은 먹지 않는다. 즉 두 개의 작업을 동시에 하지 않는다. * 지금부터 음식을 먹는다 / 허기를 채우지 않으면 바로..

1. 회색 영역해당 데이터가 어떤 막대에 들어가게 되는지 판별할 수 있는 기준이 전부 문제에 적혀 있다. 기준에 따라 각 막대에 들어간 개수를 세주자. 가장 큰 값을 들고 있는 막대가 마지막 막대이니, 전체 막대의 개수를 알 수 있다. 막대 개수와 각 막대의 높이를 알면 문제에 적힌 대로 답을 계산할 수 있다. 2. 편집 거리문제 디스크립션이 많이 엉망이다 ㅠㅠ 다시 문제를 정리하면 다음과 같다. 초기 문자열 S와 최종 문자열 T가 주어진다. 입력 문자열은 처음에 S가 들어있고 출력 문자열은 비어있다. 입력 문자열의 맨 앞 글자를 삭제하고 출력 문자열의 맨 뒤에 글자를 추가하는 다양한 연산들이 주어진다. 연산 후에 입력 문자열은 비어야 하고, 출력 문자열은 T 여야 한다. 복사를 제외한 연산의 개수를 스..

1. The Postman경로에 대한 조건이 없을 때 이 문제는 방향 그래프에서 오일러 회로를 찾는 잘 알려진 문제이다. 오일러 회로는 모든 정점의 indegree와 outdegree가 같으며, 연결되어 있는 그래프라면 항상 존재한다. 이 문제의 그래프가 그러함을 가정하자 (그렇지 않다면 NIE).오일러 회로는 다음과 같은 재귀 함수 Rec(v) 로 선형 시간에 찾을 수 있다. 오일러 회로에 대해서는 복습을 위해 알고리즘만 간략히 적어두고 설명하지는 않겠다. * 정점 v에서 나가는 에지 e를 아무거나 찾고 제거 (사용한 에지들의 인덱스를 전역 변수 등에다 마킹해 놓고, vector에서 pop_back() 하면서 에지를 지워주자) * e의 반대편 끝점이 w라면, Rec(w) 호출 * Rec(w)가 종료되면..