본문 바로가기

분류 전체보기

 (65)
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로 만들 수 있는지를 확인해줘야 하는데, 이는 완전 그래프인 경우에만 가능하다. 따라서, ..
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을 곱해주는 귀찮은 부분은 따로 빼두고 생각..
레이블과 소수자성 요즘 들어 나의 글쓰기 실력이 지속적으로 줄어가는 것을 느꼈다. 고로, 내가 했던 생각들을 짧게나마 기록하는 습관을 들이려 노력해본다. 우리 사회는 사람들에게 레이블을 붙이는 것을 참 좋아하는 것 같다. 예를 들어, 사회가 나에게 붙여준 레이블은 남성, 대학생, 개발자, 20대 등이 있다. 이렇듯, 사회의 각 구성원은 여러 레이블을 단 채로 살아간다. 그런데, 한 사람이 여러 레이블을 달고서 살아간다고 한들, 사회는 모든 레이블에 균등한 가중치를 두고 바라보지 않는다. 두 명의 20대 남성 개발자가 있다고 하더라도, 한 명에게는 20대라는 사실에, 다른 한 명에게는 개발자라는 사실에 더 초점을 두고 바라볼 수도 있는 법이다. 즉, 사회가 개인을 바라볼 때 더 우선적으로 바라보게 되는 레이블이 존재하는 것..
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를 부르면서 떼창을 못하게 하는 건 너무한 것 아닌지(?) 코로나-..

티스토리툴바