본문 바로가기

분류 전체보기

(76)
Resume 올해 진짜 한게 뭐지?
[BOJ] 23172 Equivalent Pipeline 문제 링크: [BOJ 23172](https://www.acmicpc.net/problem/23172) 문제 요약 정점이 $n$개인 가중치 있는 트리가 $d$개 있다. $vT(i,j)$를 $T$에서 $i$와 $j$를 잇는 최단경로 중 가중치의 최솟값이라고 하자. 만약 모든 $i$, $j$ 쌍에 대해 이 값이 같다면 두 트리는 동치이다. 동치 관계를 구하여라. 풀이 트리에서 가장 가중치가 작은 간선들을 생각해보자. 이 간선들을 제거하면, 트리가 여러 컴포넌트로 쪼개질 것이다. 이때 같은 컴포넌트에 있는 정점들끼리의 $vT(i,j)$ 값은 반드시 최소 가중치보다 크고, 다른 컴포넌트에 있는 정점들끼리의 값은 정확히 최소 가중치일 것이다. 따라서 두 트리가 동치이려면 최소 가중치 간선들을 기준으로 쪼갰을 때 ..
[BOJ] 16711 Erasing Matrix 문제 링크: [BOJ 16711](https://www.acmicpc.net/problem/16711) 문제 요약 격자가 있다. 격자에서 인접한 두 수를 골라 임의의 수를 더할 수 있다. 격자 안의 수가 항상 음수가 되지 않게 하면서 최종적으로 모든 수가 0이 되게 하는 방법을 찾아라. 풀이 일단 가장 먼저 생각해봐야 할 점은 -1을 찍을 조건이다. 이런 식으로 격자에서 인접한 두 수를 고려하는 문제는 특성상 체스판처럼 색칠하면 이분 그래프 구조가 나오는데, 이를 활용해 볼 수 있다. 인접한 두 수에 어떤 수를 더하더라도 (흰 칸의 수 합) - (검은 칸의 수 합)은 변하지 않으므로, 이 두 값은 반드시 같아야 한다. 만약 이 값이 같다면 항상 0으로 만들 수 있을까? 가능하다. 핵심은 같은 색깔이라면 ..
[BOJ] 17434 도로 청소 문제 링크: [BOJ 17434](https://www.acmicpc.net/problem/17434) 문제 요약 무방향 그래프가 있다. 교집합이 없고 방문하는 간선의 합집합이 그래프 간선 전체인 오일러 투어 2개를 구하여라. 풀이 풀이 방향을 잘못 잡으면 구데기같은 구현에 고통받게 된다. 일단 가장 먼저 생각해야 하는 건, 그래프의 홀수 차수 점 개수는 반드시 0, 2, 4중 하나여야한다는 것이다. 오일러 투어를 하나 구하고 그 간선들을 모두 제거한다고 생각해보자. 그러면 오일러 순환인 경우 홀수 차수 점 개수는 그대로고 아니라면 2개 줄어든다. 모두 지웠을 때 개수가 0이어야 하므로 이 셋 중 하나이다. 홀수점 0개 아무 오일러 순환을 하나 찾자. 그 뒤 아무데서나 적당히 끊어서 오일러 투어 2개로 ..
Google SWE Intern 생존기 (1) Intro 이제 막 구글에 입사한지 2주를 채워갑니다. 첫 회사생활이라 정말 걱정 많이 했는데 시작을 이런 좋은 회사에서 할 수 있어서 매우 행운이라고 생 각합니다. 궁금해하시는 분들이 있을까봐 자세히 적지는 못하더라도 간단하게 이것저것 적어보려고 합니다. Team & Work 구글에 많은 팀들이 있는데, 구글 코리아에도 그 중 일부가 있습니다. 구글 검색을 담당하는 서치 팀, 그리고 머신러닝에 주로 사용되는 프레임워크인 텐서플로우 팀 중에서 하나를 골라야 했는데 작년에 서치 팀에서 인턴 하셨던 대학 선배님이 강력하게 추천해주셔서 서치 팀으로 팀 매칭하게 되었습니다. 업무는... 하드코어합니다. 일단 알고리즘만 하다 보니 개발에 대해서 완전 문외한이고, 심지어 그나마 조금 했던 개발도 백엔드였습니다. 그..
Google SWE Intern 지원부터 오퍼까지 Intro 이번 여름방학에, 6월 말부터 9월 중순까지 구글 코리아에서 SWE 인턴으로 근무하게 되었습니다. 첫 회사 생활이라 무섭기도 하고, 반면에 매우 기대되기도 하네요. 입사까지 약 두달 반정도 남았는데, 그동안 구글 기대하느라 학점을 망칠 것 같아서 조금 불안하기도 합니다만;; 어쨌던 간에 인터넷을 찾아보니 타 직군에 대한 인턴 후기는 꽤 많았는데 SWE 인턴 지원 후기는 거의 없어서 이것저것 짧게 적어봅니다. Main 작년에 아는 대학교 선배 분이 구글 인턴 한번 지원해보지 않겠냐고, 레퍼럴을 써주실 수 있는 분을 안다고 해서 이번 여름에는 되던 안되던 구글 인턴을 한 번 넣어봐야지 생각하고 있었습니다. 사실 그렇게 생각하고 있다가도 그냥 까먹고 있었는데, 선배님이 remind를 해 주셔서 시기..
Random Problem Solving 2 10650 Marathon 다음과 같은 두 배열을 관리하자. $\text{next}[i]$ : $i$번째 좌표에서 $i+1$번째 좌표로 이동하는 거리 $\text{save}[i]$ : $i$번째 좌표를 달리기 중 생략하기로 결정했을 때 절약하는 거리 그러면 쿼리 $Q$는 다음과 같이 해결할 수 있다. $s$에서 $e$까지 이동해야 하면, $\displaystyle \sum_{i=s}^{e-1} \text{next}[i] - \max_{s + 1 \le i \le e - 1} \text{save}[i] $ 가 답이 된다. 따라서 $\text{next}$는 부분 합 세그먼트 트리, $\text{save}$는 부분 최대 세그먼트 트리를 이용해서 관리해주면 $O(\log N)$에 찾을 수 있다. 쿼리 $U$는 ..
[BOJ] 20093 Coins 문제 설명 $8 \times 8$ 크기의 체스보드가 있습니다. $A$와 $B$가 이 위에서 게임을 합니다. 각 체스보드에는 동전이 하나씩 올려져 있고, 처음 상태는 무작위입니다. $A$는 동전을 최대 한 개 뒤집어서, $0$ 이상 $63$ 이하의 정수 하나를 체스보드만 보고 $B$가 알 수 있게끔 해야 합니다. $A$와 $B$의 전략을 직접 구현해 제출하는 투 스텝 문제입니다. 문제 관찰 서브태스크 1 동전을 하나 뒤집을 수 있다는 건, 원하는 위치의 동전을 위 또는 아래로 정확히 맞출 수 있다는 것과 동치입니다. 따라서 0번 위치의 동전을 잘 뒤집어 주면 됩니다. 서브태스크 4 서브태스크 1과 비슷한 느낌으로 접근합시다. $A$가 $B$에게 전달해야 하는 정보는 정확히 6비트어치입니다. 따라서 6개의 ..