전체 글 (78) 썸네일형 리스트형 Sage Installation on WSL2 Disclaimer: I don't know why this works/doesn't work; it is only a result of trial and error. 0. If you didn't install a WSL2, please download and install it(https://learn.microsoft.com/en-us/windows/wsl/install). - You should be aware that you must turn on virtualization on windows and bios. 1. AFAIK installing from conda-forge is best. Download Anaconda(https://www.anaconda.com/) here or somet.. [BOJ] 24973 Up Down Subsequence 문제 요약 길이가 $N$인 수열이 주어진다. 어떤 부분수열을 앞에서부터 읽었을 때 인접한 두 수가 커지면 U, 작아지면 D를 적은 문자열이 있다고 하자. 문자열 $S$가 주어질 때 부분수열을 잘 골라서 만든 문자열과 $S$의 common prefix 길이를 최대화하여라. 문제 풀이 결론부터 말하면, 다음을 반복하면 된다. 1. 문자열을 (연속한 문자 종류, 개수)로 압축한다. 2. 맨 앞이 U면 LIS, D면 LDS를 길이가 그 문자의 개수가 될 때까지 찾는다. 3-1. 만약 찾지 못한다면 LIS나 LDS의 길이(정확히는 길이-1)만큼 추가로 문자를 처리할 수 있고 그 뒤는 불가능하다. 3-2. 만약 찾는다면 연속한 문자를 모두 처리할 수 있다. LIS/LDS의 마지막 위치가 pos라고 하자. 그러면 계.. 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를 해 주셔서 시기.. 이전 1 2 3 4 ··· 10 다음