그냥 하는 노트와 메모장

소스 코드 위치: 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..

소스 코드 위치: Google Kickstart 2019 Round C A. Wiggle Walk A 치고 너무 복잡하게 푼 느낌이 든다.. 행과 열에 대해서 DSU를 따로 관리한다. 다음에 이동하는 위치가 (ny, nx)라면 인접한 4방향에 대해서 이미 방문한 칸이 있다면 merge해준다. 이 때 DSU에서 관리하는 데이터는 left와 right로 두 변수가 있고, 각각 행 또는 열에서 이미 방문한 칸들에 가장 가까운 작은 값과 큰 값을 말한다. 위와 같이 행과 열 각각 DSU를 관리하면서 상하좌우 이동해주면 된다. B. Circuit Board i번째 행 j번째 열을 구성하고자하는 사각형의 우측 하단 꼭지점에 위치한다고 치자. i행만 쓴다면 i행에서 최대값과 최소값의 차이가 K를 넘어서지 않는 좌표가..

소스 코드 위치: Google Kickstart 2019 Round B A. Building Palindromes 쿼리 (L, R) 마다 L과 R 사이에 있는 문자들을 재배열하여 팰린드롬을 만들 수 있는지를 묻는 문제다. 사용되는 문자가 26밖에 없으므로 prefix array를 정의하여 L과 R 사이의 i번째 문자가 출현하는 수가 홀수면 1, 짝수면 0으로 두고 이러한 홀수의 수가 2 이상이면 팰린드롬을 구성할 수 없다고 계산하면 된다. B. Energy Stones [시간] 모든 에너지 스톤을 먹었을 때 가능한 가장 긴 시간은 10000까지다. [Lossless] L이 0인 에너지 스톤은 L이 1 이상인 스톤을 모두 먹고난 뒤 처리하는 것이 이득이다. [Ordering] L > 0인 에너지 스톤만 가..

아쉽다.. 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 배열을 사용한다...

* 2017 카카오코드 예선 이 글은 카카오가 제시한 해설과 다소 다를 수 있습니다. 카카오 기술 공식 블로그에서 에디토리얼을 작성하였으니 참고해주세요 URL : http://tech.kakao.com/2017/08/11/code-festival-round-1/ 1. 카카오프렌즈 컬러링북 1번 문제답게 상냥하게 나와줬다. [해설, 분류 - BFS/DFS/Dijkstra/Disjoint set] O(mn) 쭉 순회하며 같은 색상에 대해 같은 Component를 이루도록하고 그 중 가장 큰 Component를 골라내면 된다.#include #include using namespace std; struct _d { int y, x;}; vector solution(int m, int n, vector pict..

새로 등장한 코딩테스트 대행 스타트업 사이트다. 문제를 보아하니 그렇게 나쁘지 않은 난이도 및 구성이라 시험을 치뤄봤다. ㅎㅎ 7등이 나온걸 보아 아직 난 멀었나보다 싶다. [ Solution ] 1. 문자열 변환 그냥 문제 설명 그대로 해주면 되겠다.. #include using namespace std; class Solution{ public: string decryptSpell(string str){ for(int i=2;i

1. 숫자 게임 [ Greedy/ Sorting ] Greedy하게 접근해보자. A팀의 점수를 알고 있다. 여기서 B팀의 순서를 결정하여 최대 이길 수 있는 회수를 결정한다. 이기기 위해서는 A 팀원의 수보다 큰 수를 B가 내야한다. B의 최대값을 X라고 하자, A의 최대값을 Y라고 하자. 그러면 X가 Y보다 작다면, 답은 명확하게 0이다. 다르게 표현하자면, X가 Y보다 크다면 X와 Y를 짝을 지어주자. 그러면 답은 1이 증가한다. 만약 B안에 X보다 작고 Y보다 큰 값이 있다면 어떻게 될까. 어떻게 되든 X는 "반드시" 소모되며 A의 모든 요소보다 크기 때문에 큰 값끼리 묶어 주는 것이다. 더보기 #include #include #include using namespace std; int soluti..

* 2017 카카오코드 본선이 글은 카카오가 제시한 해설과 다소 다를 수 있습니다.카카오 기술 공식 블로그에서 에디토리얼을 작성하였으니 참고해주세요 URL : http://tech.kakao.com/2017/09/14/code-festival-round-2/ 1. 단체 사진 찍기 [ 분류 - Brute force/ Permutation ] 전체 경우의 수를 생각해보면 8!밖에 되지 않고, 조건의 수가 최대 100개이기 때문에 완전 탐색으로 답을 도출해낼 수 있다. next_permutation이나 기타 완탐 구조를 통해 답을 도출해내자.#include #include #include #include using namespace std; struct _d { int a,b,cnt, code; }; int ..

* Codeforces Round #462 (Div. 2) A. A Compatible Pair 곱셈에 대해 가장 작게 만들기 위해 for문을 세 개로 구성해서 Brute force로 알아낼 수 있다. O(N^2 M) #include using namespace std; using ll = long long; ll min_v(ll a, ll b) { return a b ? a : b; } int main() { int n, m,i,j,k; ll ans=1e18, tmp, A[50], B[50]; cin >> n >> m; for (i = 0; i > A[i]; for (i = 0; i < m..

A. B. 걷다보니 신천역 삼 (Small)/(Large) 단순 dynamic으로 생각할 수 있다. 마지막 수에 대해서 0,1,2가 들어갈 수 있으므로 현재 k자리 수에 대해서 3*dp[k]를 처리해주면 된다. 단 int의 경우 3개를 더했을 경우 오버플로가 발생할 수 있으니 유의. #include #define MOD 1000000009 int main() { long long N,R=0; scanf("%lld", &N); if (N > 1) R = 2; while (N-- > 2) R = ((R + R) % MOD + R) % MOD; printf("%lld", R); return 0; } C. 나는 행복합니다 ~ 규칙이 있는 2차원에서 해싱을 할 수 있는지 물어보는 문제. 가로로 순서대로 적혀지기 ..

A. Eleven 주어진 길이에 대해 피보나치 수가 넘어가지 않을 때까지 'O'로 바꿔주기만 하면 된다. #include #include int main() { int N,a=1,b=1,t; char name[1001] = {}; scanf("%d", &N); memset(name, 'o', N); name[0] = 'O'; while (a + b

A. Perfect Squares sqrt 함수를 이용하여 제곱수인지 확인하고 그 중에서 최대값을 찾으면 된다. #include #include int max_v(int a, int b) { return a > b ? a : b; } int main() { int n, D,ans=-1e9; double tD; scanf("%d", &n); while(n--) { scanf("%d", &D); if (D >= 0) { tD = sqrt(D); if (tD != (int)tD) ans = max_v(ans, D); } else ans = max_v(ans, D); } printf("%d", ans); return 0; } B. Conan and Agasa play a Card Game Greedy하게 접근한..

A. 순서쌍의 곱의 합 단순 for 두번 O(N^2)으로는 시간초과가 나버린다. 구하는 것은 (A1*A2 + A1*A3 + ... + A1*AN) + (A2*A3 + A2*A4 + ... A2*AN) + ... + (AN-1*AN) 꼴이 된다. 규칙성을 말하자면 A1의 경우 A2부터 AN까지의 합에 곱셈을 해야하고, AK의 경우(1

A. 비밀번호 재귀 완전탐색을 구현한다. 모든 가능한 숫자에 대해서 사용했으면 1을 추가해준다. 매우 간단. #include int ans,n,m, used[10], mc[10]; void back(int p) { if (p >= n + 1) { bool f = 1; for (int i = 0; i < m && f; i++) if (!used[mc[i]]) f = 0; ans += f; return; } for (int i = 0; i < 10; i++) { used[i]++; back(p + 1); used[i]--; } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) scanf("%d", &mc[i]); back(1); printf..