본문 바로가기

분류 전체보기

 (46)
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월에 대학원생 형들 두 명과 함께 다녀왔을 때 찍은 사진이다. 코스 시작 전에 자리는 이렇게 세팅되어 있었다. 이 날은 술을 먹지 않기로 해서 와인을 들고가지 않았는데, 나중에 크게 후회했다. 샴페인 같은거 두어 병 콜키지 하기 좋으..
[넬 콘서트] Let The Hope Shine In 작년에 준원이랑 넬의 콘서트에 갔었다. 8.15 광복절 집회 발 코로나-19 대유행과 겨울의 코로나-19 대유행 사이의 짧은 "잔잔한" 시기에 마침 콘서트가 있어서 다행히도 다녀올 수 있었다. 넬은 고등학교 동기 중에 음악하는 친구가 한 명 있는데, 그 친구의 소개로 고등학교 때 부터 좋아했었다. 넬 콘서트도 마찬가지로 저번에 간게 처음이었다. 뭔가 적을 내용이 많지는 않다 보니 콘서트 가기 전에 준원이랑 딘타이펑에서 먹은 저녁 사진도 넣어봄 ㄱ- 이건 콘서트 장 도착해서 줄 기다리면서 급하게 찍은 사진... 이 날 콘서트 역시도 코로나-19 관련 방역 수칙을 준수하기 위해 떼창을 할 수는 없었지만, 너무나도 좋았다. 그치만... Stay를 부르면서 떼창을 못하게 하는 건 너무한 것 아닌지(?) 코로나-..

티스토리툴바