본문 바로가기

분류 전체보기

(46)
IT 산업기능요원이 되기까지 왜 산업기능요원인가? 나는 병역판정검사에서 보충역을 받았고, 나에게 병역 의무를 수행할 수 있는 선택지는 전문연구요원과 산업기능요원, 그리고 사회복무요원, 이렇게 세 가지 선택지가 있었다. 병역 의무를 수행하면서 1) 노동에 대한 정당한 대가를 받고 싶었고, 2) 학부 졸업 전에 군 복무를 마치고 싶었다. 노동에 대해 정당한 대가를 받으며 병역 의무를 수행하는 제도로는 앞의 두 제도가 있고, 학부를 졸업하기 전에 병역 의무를 마칠 수 있는 제도로는 뒤의 두 가지가 있었다. 그래서 두 조건 모두를 만족하는 산업기능요원으로 군 복무를 수행하기로 했다. 산업기능요원이 되는 과정 어떤 것을 준비했나요? 나는 다양한 회사의 채용 공고를 보면서 내가 어떤 회사의 어느 포지션에 지원할 것인지를 먼저 결정했다. 회사의..
2-SAT 및 그의 응용 1. 2-SAT 문제란? 2-SAT 문제란 참/거짓의 값을 가지는 불리언 변수 $n$개 $x_1, x_2, \cdots, x_n$ 와 2-CNF가 있을 때, 2-CNF를 참으로 만들기 위해 $x_i$ 들에 적당한 값을 할당하는 문제이다. 2-CNF란 2개의 변수를 $\lor$ (or)한 식(절) 여러 개에 $\land$ 연산을 취해 만들어지는 식을 의미한다. 예를 들어, $(x_1 \lor x_2) \land (\bar x_3 \lor x_4)$ 는 2-CNF이다. 그리고, $x_1 = true$, $x_2 = false$, $x_3 = false$, $x_4 = false$ 는 이 식을 만족 시키는 하나의 방법이다. 반대로, $(x_1 \lor x_1) \land (\bar x_1 \lor \bar x..
2021-09-10 Problem Solving 11385. 씽크스몰 단순히 다항식의 곱셈을 FFT로 수행하면 해결할 수 있어 보인다. 하지만, 입력되는 수의 범위를 살펴보면, long double을 써도 맞기 쉽지 않음을 알 수 있다. 나는 조금 더 안전 빵으로, 소수 두 개를 이용해 NTT를 두 번 한 후, CRT를 이용해 계수들을 복원하여 문제를 해결했다. 19265. Is it a p-drome? 모든 값을 0-based index로 생각하자. 어떤 문자열이 $p$-drome 이라면, $p$를 적용한 결과물과 해당 문자열의 라빈 핑거프린트 해시 값이 같을 것이다. 고로, $i$에서 시작하는 길이 $m$인 문자열을 본다고 할 때, 원래 문자열의 해시 값은 $\sum_{j=0}^{m-1} a_{i+j} x^j$ 이 될 것이고, $p$를 적용한 결과..
2021-08-27 Problem Solving 요즘도 꾸준히 1일 1문제는 해결하려고 노력 중이다. 지난 번에 글 쓰고 나서 풀었던 문제들 중 일부를 뽑아서 풀이를 올려본다. 17114. 하이퍼 토마토 간단한 BFS를 통해 문제를 해결할 수 있다...만, 11차원 입력을 효율적으로 처리하는 것이 중요한 문제다. 나는 11차원 배열을 선형으로 펴고, 적절한 사칙연산을 통해 11차원 벡터와 선형 배열 인덱스 사이의 변환을 해주는 방식으로 구현했다. 나의 구현 방식으로 문제를 해결하기에는 다소 빠듯한 면이 있어서, 빠른 입출력 등의 여러 최적화를 함께 사용하여 문제를 해결했다. 22967. 구름다리 성게 그래프를 출력하면, 답이 2 이하임이 보장된다. 이제, 답을 1로 만들 수 있는지를 확인해줘야 하는데, 이는 완전 그래프인 경우에만 가능하다. 따라서, ..
이직 지난 달 말에 이전 회사를 퇴사하고, 조금의 휴식기를 가진 후, 센드버드라는 또 다른 회사로 이직했다. 원래는 이직 생각이 크게 없었지만, 산업기능요원 편입과 관련해 다소 좋지 못한 일이 있었어서, 결국 이직 했고, 지난 주 부터 산업기능요원으로 근무하고 있다. (몰로코가 절대 나쁜 회사는 아니다. 다만, 당분간 산업기능요원을 뽑지 못할 뿐이다.) 비록, 이직의 시작은 불가항력적인 사유였으나, 좋은 기회를 잡게 되어 매우 감사하고 있다. 회사에서 내가 어떤 일을 하게 될 지 차차 알아가면서 일하는 중인데, 너무 재밌고 챌린징해 보이는 태스크들이 많아서 만족스럽다. 그 외에 회사 문화나 급여, 복지 등의 부분도 매우 만족스럽다. (이직의 시작은 불가항력적인 사유였지만, compensation 또한 꽤 많이..
2021-08-21 Problem Solving 이번에도 문제를 비교적 꾸준하게 풀었던 것 같다. 특히, 이번 주 부터는 ho94949님, dennisstar님과 함께 하루에 랜덤 문제 5개를 뽑아서 하나 이상 푸는 챌린지를 하고 있어서 (나 말고 나머지 두 분은 웬만해서 거의 다 풀긴 하는듯) 더 자극이 되었던 것 같다. 20986. Group Photo 1번부터 $i$번까지만 생각해주는 방식으로 DP를 할 수 있다. 이 DP를 효율적으로 하는 방법에 대해서 생각해보면 되는데, $i$ 앞에 $j$가 오는지의 여부를 $N^2$개의 쌍에 대해 전부 이차원 배열에 구해둔 뒤, $x$축과 $y$축 두 방향 모두에 대해서 prefix sum 전처리를 해두고 활용할 수 있다. 15759. Talent Show 1000을 곱해주는 귀찮은 부분은 따로 빼두고 생각..
2021-08-08 Problem Solving 오랜만에 문제 해결을 좀 해봤다. 18227. 성대나라의 물탱크 DFS ordering을 이용하여 트리를 직선으로 펼 수 있다. 구체적으로는, DFS에서 정점 $u$를 처음 방문하는 시각을 $in[u]$, 빠져나오는 시각을 $out[u]$라 할 때, $u$의 서브트리의 방문 시각은 $[in[u], out[u]]$ 범위에 속함을 알 수 있다. 이를 이용하면, 트리를 선형으로 다룰 수 있고, Binary Indexed Tree 와 같은 자료구조를 함께 얹어서 문제를 해결할 수 있다. (왜냐하면, 어떤 정점에 물이 차는 횟수는, 해당 정점을 루트 노드로 하는 서브 트리에 물을 채우려 시도하는 횟수와 같기 때문이다.) 참고로, DFS ordering을 이용하여 트리를 직선으로 펴는 테크닉은 여러 분야에 응용의 ..
2021-08-01 Problem Solving 한 동안 정신 없는 일정 때문에 알고리즘 문제 해결을 별로 하지 못했으나, 최근에 여유가 생겨 SCPC 대비도 해볼 겸 다시 잡기 시작했다. 이번에 해결한 문제들을 정리해본다. 어찌 뒤로 갈수록 풀이를 대충 적은 것 같다... 21586. Another Substring Query Problem 쿼리가 하나만 주어진다면 어떨까? 문자열 $S$에 특정한 패턴 $P$가 $k$ 번째로 등장하는 지점을 찾는 문제가 된다. 이는 라빈 핑거프린트를 이용하여 문자열을 해싱해놓은 후, $|P|$ 길이의 부분 문자열을 살펴보며 쉽게 해결할 수 있다. 이 경우, 전체 과정이 약 $O(|S| + |P|)$ 정도의 시간에 이루어진다. 그런데, 이 과정을 모든 쿼리에 대해 반복하게 된다면, $O(Q(|S| + |P|))$​ 정..
운전을 시작했다 집에 낡은 소나타 한 대를 아무도 안타서 요즘에는 내가 굴리기 시작했다. 처음에는 아파트 단지 한 바퀴 도는 것도 힘들었는데, 운전 2일차에 분당에서 신사동 호텔까지 차를 끌고 가 봤던게 운전 실력 향상에 큰 도움이 되었던 것 같다. 운전 2일만에 차를 긁어먹은 건 다소 안타까운 일이지만.. 별로 티가 안나서 크게 신경 안쓴다. 주차 연습은 아래 사진을 찍은 마트에 오가면서 크게 늘었던 것 같다. 좁은 골목길을 두어시간 정도 빙글빙글 돌 일이 있었는데 그 때 차 폭 감에 대한 이해도 늘었던 것 같다. 그 외에는 그냥 한남동의 마리또 에 몰리에라는 파스타 가게에 밥 먹으러 다녀오면서 고속도로 주행 연습을 했던 것 같다. 아무튼 안전 운전 하도록 노력해야지.
[정자동] 분당 스시야 흔히 분당 스시야, 분스야, 분당의 축복 등으로 불리는 스시야라는 식당에 대해 소개한다. 모 유튜브 채널을 통해 떠서 이미 유명한걸로 알긴 한다. 여튼 위치는 정자역 나와서 네이버 쪽으로 조금 걸어가면 있다. 예약이 다소 빡센 곳이다 보니, 나도 자주 가지는 못한다. 올해에는 아직 4~5번 정도 밖에 가지 못한 것 같다. 예전에 예약이 비교적 쉽던 시절에는 디너도 몇 번 다녀왔는데, 요즘에는 디너를 가기가 어렵다 보니 더더욱 아쉽다. 여튼, 오늘 올리는 사진은 2020년 10월에 대학원생 형들 두 명과 함께 다녀왔을 때 찍은 사진이다. 코스 시작 전에 자리는 이렇게 세팅되어 있었다. 이 날은 술을 먹지 않기로 해서 와인을 들고가지 않았는데, 나중에 크게 후회했다. 샴페인 같은거 두어 병 콜키지 하기 좋으..