그냥 하는 노트와 메모장

소스 코드 위치: Google Kickstart 2021 Round C solutions A. Smaller Strings 1. 주어진 문자열(s)의 넘어가지 않도록 첫 문자부터 건설해나가자. 문자 'a'부터 시작해서 문자 'a'+K-1까지 사용한다. 2. i(단, 0 최적 부분 구조, 겹치는 부분 문제 -> 다이나믹 프로그래밍 1.에서 각 날은 독립적이고, 문제에서 주어진 조건에선 어떤 X가 주어지든 답은 반드시 존재하므로 각 날마다 점수의 기대값을 최대로하면 반드시 X보다 크거나 같은 값이 나온다. 따라서 2. 구조를 파악하여 동적 프로그래밍을 구성한다. dp[i][j][k] = i번 rock을 냈었고, j번 scissor를 냈었고, k번 paper을 낸 상태에서 가질 수 있는 점수의 기대값의 최대값..

소스 코드 위치: Google Kickstart 2021 Round B A. Increasing Substring 거저 주는 문제.. 이전 값과 비교해서 현재가 크면 이어주고 아니면 끊는다. B. Longest Progression 음? 갑자기 구현이 빡세진 느낌. prefix array, suffix array를 유지하면서 현재 i번째를 바꾸려고 할 경우 i기준 왼쪽과 함께할 것인지 오른쪽과 할 것인지를 결정한다. 이때 양쪽 어디든 합치려고 할 때 그 차이값을 다른 한쪽과 비교하여 이어질 수 있는지도 판단해야 한다. 양끝 처리 때문에 좀 시간이 걸렸던 문제. C. Consecutive Primes Analysis보고 풀었다.. 10^9보다 작은 인접한 두 소수의 차이는 계산할만큼 작다. Prime ga..

아쉽다.. 4번 플로우 문젠줄 알고 그래프 그리다가 시간이 끝나버렸다 ㅠ 소스 코드 위치: [Google Kickstart 2021 Round A] A. K-Goodness String 양 끝에서 한 칸씩 이동하면서 같은 문자의 수(c)를 셈한다. 같아야 하는 문자의 수가 정확히 K이어야 함으로 abs(K - c)를 답으로 내면된다. B. L Shaped Plots 2차원의 각 좌표는 L의 꺽이는 위치의 후보가 된다. 모두 순회해봐야 하니 이 과정은 O(N^2)이 걸린다. 동서남북 4방향 0을 만나기 전까지 연속된 1의 길이를 각 방향에 대해 구한다. 이 때 for문을 한 번 더 돌려서 구하지않고 prefix sum을 구해서 계산하도록 한다. 방향이 4방향이니 4개의 prefix sum 배열을 사용한다...