남성성이라는 것은 사회가 붙이는 것이기 때문에, 남성이 남성성에 갇힐 필요는 없다. 하지만 나는 사회를 살아가는 사람이고, 나는 태어날 때 남성이라는 성별이 지정되었기 때문에, 사회에 있는 나는 남성성을 강요받는다. 전통적으로 남성성이라고 말함은 체력, 용기, 독립심, 리더십, 강한 의사 표현이다. [1] 나는 여기서 체력, 강한 의사 표현, 리더십 같은 특징에 가치를 둔다. 용기에 대해서는 가치 중립적이며, 독립심은 내가 추구하고자 하는 가치와는 거리가 있다. 또한, 나는 사회에서 요구되는 여성성도 가지고 있다. 전통적으로 여성성이라고 말함은, 우아함, 친절함, 공감, 겸손, 섬세함이다. [1] 이 특성들은 내가 추구하고자 하는 가치와 일맥상통한다. 나는 신체 자체에 대한 성별 불일치감을 다른 트랜스젠더처럼 크게 느끼지 않는다. 내가 신체 자체에 대해 성별 불일치감을 느끼는 거의 유일하다시피 하는 부분은 내가 임신을 할 수 있는 몸이 아니라는 것이다. 다른 내가 느끼는 성별 불일치감은 대부분 사회적인 시선에서 나온다. 솔직히 나는 내 키와 체격이 마음이 안 든다고 생각하지만, 신체적 성별 불일치감이냐고 물으면 아닌 것 같다. 하지만, 사회가 나의 키와 체격 때문에 나를 여성으로 바라봐주지 않는다는 점은 트리거가 되고, 이는 나의 성별 불일치감에 일조한다. 전통적인 남성성을 추구하지 않는 것도 아니며, 신체적인 성별 불일치감을 크게 느끼지도 않는데, 왜 호르몬 치료를 받냐고 나에게 물어보면, 그것은 내가 사회에 받아들여지기 위한 노력이다. 사회에 순응하지 않는 나의 표현을 쓰면, 나의 호르몬 치료는 잘못되었다. 어릴 적부터 나의 여성성을 표현하려는 시도는 많이 제지당했다. 실제로 내가 여성적인 취미라고 보이는 뜨개질을 하고부터 좋아하는 색이 분홍색이라고 말하는 것까지 많은 사람은 한두 마디를 얹었다. 내가 머리를 기르면 사람들은 칼같이 그 머리를 자르려고 했고, 내 머리를 어울리지 않는다고 표현했으며, 짧게 자른 나의 머리를 좋다고 표현했다. 그 사람들은 스트레스가 쌓여 가위로 내가 내 머리를 자르는 행위에 대해서 '이렇게라도 자르는 게 어디야.'라고 말했을 수도 있다. 내 주위의 사회는 나의 여성성을 외면했으며, 나의 성급함은 정제되지 못했고, 나의 다정함은 갈 곳을 잃었다. 나의 여성성은 억압되어왔다. 반면에 나의 남성성은 큰 성공을 이룬 것 같다. 이래서 당연히 모두가 나를 남성으로 인식했고, 나조차도 나를 사회적 남성성에 빗대어 인식했다. 나는 우아함, 공감, 섬세함 등의 가치를 기르는 데에 멀어졌고, 오히려 내 주위의 남성 사회 평균보다 낮아졌을 수도 있을 것 같다.
내가 남성 사회에서 불쾌함을 덜 인식했던 이유는, 나에게서 전통적인 남성성을 찾아볼 수 있어서 그걸 선택적으로 표출했고, 또한 내 주위에서 내 여성성을 인정해 주는 사람이 있기 때문이었던 것 같다. 나는 나에게서 여성성을 찾아주는 사회를 찾아가야 했고, 찾아갔다. 흔히 말하는 얼굴을 보며 얘기하는 "일반적이고 정상적인" 사회가 내 여성성을 하나도 찾아주지 않았기 때문이다. 이는 나의 큰 체격과도 관련이 있을 것이다. 내가 가장 크게 성별 불일치감을 느낀 곳은 기초군사훈련을 받은 4주 동안이다. 내가 보던 가장 남성성이 강조되는 사회였고, 나는 이 사회에 적응하지 못했다. 이 사회는 나에게서 모든 여성성을 표현할 기회를 주지 않았으며, 그런 점은 나에게 압박과 불안, 그리고 공포감으로 나타났다. 성별 정체성은 내가 정하지만, 사회적 성별은 내가 정하는 것이 아니다. 사회적 성별은 사회가 정하고, 사회적 성별이 내가 원하는 대로 비치기 위한 노력을 할 수 있지만, 모든 노력이 성과로 다가오는 것은 아니다. 나는 이를 위해서 강력한 수단을 써야 했고, 정체화와 호르몬 치료는 그런 사회가 나를 받아주게 하는 거의 유일하다시피 한 방법이었다. 정체화를 한 이후에, 누구보다도 성별 고정관념을 타파하고 싶은 사람인 나는 사회가 만들어 놓은 여성성이라는 고정관념에 갇혀버렸다. 머리를 기르지 않고 짧게 자른 여성도 여성이다. 하지만 나는 머리를 길게 기른다. 마른 몸을 동경하지 않는 여성도 여성이다. 하지만 나는 마른 몸을 동경한다. 치마를 입지 않는 여성도 여성이다. 하지만 나는 치마를 입는다. 나는 나 자신에게 여성성을 강요하고, 그래야 사회가 나를 그나마 여성으로 봐준다는 점을 잘 안다. 동시에, 남성으로 사회가 나를 바라볼 때는 느끼지 못했던, 여성으로 사회에서 비칠 때 사회가 나에게 주는 상처와 억압을 느끼고 있다. 몸의 상처도 있다. 나에게는 아직도 아물지 않은 왼쪽 다리의 상처가 있고, 사회적 여성성에 맞춰 제모하다가 얻은 상처이다. 그리고 마음의 상처가 낫는 것은 몸의 상처가 낫는 것보다 느리다. 모든 사람이 마스크를 끼고 다닌다. 여성으로 비치는 데에 얼굴의 지방배치나 하관도 영향을 끼치는데 마스크는 이를 완벽하게 가려준다. 내가 머리가 조금 길고, 내가 치마를 입고, 조금만 높은 목소리를 낸다면, 내가 여성으로 비치는 데는 문제가 없다. 사람들은 내가 남성인데 여성복을 입었다고 생각하기보다는, 내가 여성인데 키가 매우 크다고 생각하기로 했나 보다. 여성성에 부합하기 위해 나는 머리를 길렀고, 머리를 기르는 것은 내가 나갈 때 준비하는 시간을 늘린다. 옷도 골라서 입어야 하고, 여성복은 의도적으로 불편하게 설계된 것이 아닌가 할 정도로 편의성이 없다. 나는 왜 단추 방향이 블라우스와 와이셔츠가 반대인지도 모르겠고, 왜 청바지에 앞주머니가 없는지도 모르겠다. 나는 이제야 왜 많은 여성이 핸드백을 들고 다니는지 이해했다.
길거리를 걸어갈 때, 장사하는 사람이 집요하게 나에게 말을 거는 경우가 늘어났다. 같이 얘기하는 사람이 나의 말에 귀 기울이지 않는 경우가 늘어났다. 내가 한번 말하면 들었던 것을 두세 번 말해야 하는 경우가 늘어났다. 내가 여성적인 이름과 외형을 가지고 사람에게 조언할 때, 내 조언을 무시하는 일이 눈에 띄게 늘어났다. 이런 것은 나만 느끼는 것이 아닌 것 같다. 이런 여성에 대해 무의식적이든 의식적이든 깔린 성차별은 수치화가 될 수 있을 정도로 나타났다. 가령이면, 여성이라는 정보는 취업에 악영향을 준다. [2] 나는 아직 여성적인 표현을 하고 구직활동을 해 본적은 없기 때문에 느끼는 차별에 대해서 자세히 알지는 못하지만, 일상에서 느끼는 차별과 같거나 혹은 더 큰 수준의 차별을 느낄 것 같다는 생각이 있다. 나는 나의 자기표현과 지적 성취도 중요하기 때문에, 실제로 내가 사회에서 직업을 구하고, 논문을 쓰고, 발표하고 남을 설득하려면, 내가 선택할 수 있는 가장 편한 수단은 남성성을 사용하는 것이다. 사회적 남성성은 유용하다. 나를 표현하고 내가 받아들여지기 위해서 남성성을 사용한다. 사람들이 나의 말을 듣는 이유가 그냥 내가 그런 사람이라서가 아니라, 젠더에 무관한 게 아니라, 그 사람들이 나를 남성으로 인식하고 있어서라는 이유는 나를 혼란스럽게 만들기 충분했다. 그래서 나는 나의 유용한 남성성을 아예 버리지 않기로 했고 상황에 따라서 이 둘을 선택하기로 했다. 어떤 사회에도 속해 있지만 어떤 사회에도 속하지 못하는 교란자가 된 것이다. 나는 내가 젠더에 관련 없이 원하는 방식으로 표현되기를 원하지만, 사회는 내 표현을 젠더에 가두어서 억압한다. 여기서 내가 할 수 있는 최선의 선택의 결론이 호르몬 치료까지 온 것이다.
2021년 8월 10일 화요일에 풀 배터리 검사 결과가 나왔고 이에 대해 상담하러 갔습니다. 선생님은 검사 결과를 상세하게 설명해 주셨고, 저에게 호르몬 치료를 진행하고 싶으면 진단서를 발급해 주겠다고 하셨습니다. 저는 F64.9라는 코드가 적힌 진단서를 발급해달라는 얘기를 했고, 진단서를 발급해주셨습니다. 또한, 풀 배터리 검사 기록지의 사본도 같이 가져갔습니다. 총비용은 만원이 조금 넘게 나왔던 것 같습니다. 다음 상담은 9월 2일 목요일이 될 것 같습니다.
2021년 8월 11일 오전에 대전의 민들레의원을 찾아갔습니다. 처음에 전화했고, 호르몬 치료를 하겠다는 의사를 전달하니까 진단서가 있어야 하고, 있으면 가지고 오라는 얘기를 들었습니다. 진단서를 가지고 민들레 의원에 방문했습니다. 저에게 MtF 치료 동의서라는 문서를 주셨고, 해당 문서에는 호르몬 치료가 어떤 것이고, 어떤 질환들이 발생할 수 있으며(호르몬은 간에서 처리되며, 콜레스테롤과 유사한 작용을 하므로 심장 혹은 간에 관련된 질환들이 발생할 수 있습니다), 몸에 어떤 변화들이 생기는지에 대해서 적혀 있었습니다. 또한, 해당 병원에서는 우울증을 포함한 다른 정신질환이 있는 경우에 호르몬 치료를 진행할 수 없다 같은 내용이 있기 때문에, 상대적으로 성별 불일치감을 느끼는 사람에게 흔한 우울증 같은 질병이 있는 경우에는 추가로 얘기가 필요하리라 생각합니다. 저는 동의서에 서명하고, 혈압을 잰 다음에 진료실로 들어갔습니다.
진료실에서는, 호르몬 치료가 어떤 것인지, 진단은 어디서 받아 왔는지 등등을 말해줬고, 제가 호르몬 치료를 받는 만큼 호르몬 치료에 대해서 잘 이해하고 있어야 한다고 말했습니다. 또한, 호르몬 치료를 받게 되면 어떤 일이 일어나는지 등을 상세하게 설명해 주셨습니다. 추가로 성 재지정 수술을 받을 생각은 있는지, 후에 자손을 남길 생각이 있으면 냉동 정자 생각은 있는지, 현재 파트너가 혹시 있고 호르몬 치료를 한다는 내용을 알고 있는지 등등을 물어봤습니다. 저는 추가로 풀 배터리 검사지를 전달해 드렸고, 필요한 내용을 의무기록에 기록한 것 같습니다.
민들레의원에서는 처음에는 매일 안드로쿨을 먹고, 졸라덱스데포주사를 2주에 한 번 맞고, 혈액 검사를 3개월에 한 번 하는 것을 기본으로 하지만, 주기는 예후를 보면서 조절할 수 있다고 했습니다. 현재 프로기노바는 재고가 없어서 제공하지 못하지만, 9-10월 정도에는 다시 재고가 채워질 거라고 하셨습니다. 나중에는 안드로쿨을 먹는 주기나 혈액검사를 하는 주기를 늘린다고 하였습니다. 저 같은 경우는 남성호르몬 레벨이 낮아지는 것을 원치 않아서 안드로쿨을 사용하지 않는 방향으로 호르몬치료를 진행하고 싶다고 말했고, 원하면 그렇게 하면 될 것 같다고 말해주셨습니다.
처음 가면 호르몬제를 바로 투여하지 않고, 소변과 혈액 검사를 진행합니다. 비용은 6만 원 정도가 나왔으며, 혈액 내 호르몬 비율 같은 경우에는 비보험으로 들어가서 가격이 있다고 합니다. 혈액 검사는 5일 정도가 소요된다고 하며, 5일 후에 전화를 주면 예약을 잡거나 방문을 해서 호르몬 치료를 받으면 된다고 합니다.
문제를 요약하면, 원점 $(0, 0)$을 중심으로 하는 반지름 $R$인 원 내부에 들어있는 좌표가 모두 정수인 점의 개수를 세는 문제이다. 단, 원의 경계에 놓인 점은 생각하지 않는다. ($R \le 200\,000$)
풀이는 간단하다. $x$좌표가 $a$인 위치에 대해서 $y$좌표로 가능한 값은 $-\sqrt{x^2-a^2}$ 초과 $\sqrt{x^2-a^2}$ 미만인 값이고($-R < a < R$), 정수점의 개수는 $\sqrt{x^2-a^2}$ 미만인 양의 정수의 개수에다가 1을 곱한 값이다. 구현할 때는 $\sum_{a=-R+1}^{R-1} (\lfloor \sqrt{x^2-a^2-1} \rfloor$)과 같은 식으로 구현할 수 있다. ($x^2-a^2$은 정수이기 때문에, $x^2-a^2$ 미만인 정수는 $x^2-a^2-1$ 이하인 정수와 같다.)
시간복잡도는 $\mathcal{O}(R)$이다.
2. 직8각형
문제를 요약하면, 한 변의 길이가 $K$인 각 변이 축에 평행한 정사각형 5개가 그림처럼 +모양으로 배치되어 있을 때, 외각에 놓인 8개의 점을 길이가 $K$인 직8각형이라고 부른다. 평면 상의 점 8개와 $K$가 주어질 때, 길이가 $K$인 직8각형이 되도록 점을 옮기려고 한다. 여기서, 점의 순서는 중요하지 않다. 이 때, 필요한 점의 이동거리 합의 최소값을 구하는 문제이다. 여기서, 이동거리는 택시거리이다($(a, b)$와 $(c, d)$ 사이의 거리는 $|a-b| + |c-d|$이다.)
어떤 점이 직8각형의 어떤 점에 대응되어야 하는지 알 경우에 필요한 이동거리 합의 최솟값을 구하는 방법을 생각해보자.
첫째로, 택시거리는 $x$좌표와 $y$좌표의 차이의 합이기 때문에, $x$좌표와 $y$좌표를 따로 생각할 수 있다. 그렇기 때문에, $x$좌표와 $y$좌표에 대해 문제를 따로 따로 풀어줄 수 있다.
둘째로, 이동거리가 최소가 되는 $p_0$의 $x$좌표를 편의상 $a$라고 하면, $p_0, p_1$으로 옮기는 점은 $x$좌표가 $a$, $p_2, p_7$로 옮기는 점은 $x$좌표가 $a+K$, $p_3, p_6$으로 옮기는 점은 $x$좌표가 $a+2K$, $p_4, p_5$로 옮기는 점은 $x$좌표가 $a+3K$가 되도록 옮겨야 한다. $p_i$로 옮겨야 하는 점의 $x$좌표를 $x_i$라고 하면, $|x_0 - a| + |x_1 - a| + |x_2 - (a+K)| + |x_3 - (a+2K)| + |x_4 - (a+3K)| + |x_5 - (a+3K)| + |x_6 - (a+2K)| + |x_7 - (a+K)|$ 를 최소화 하는 문제가 된다. 기본적으로 어떤 배열 $v$에 대해, 합 $|v_i-a|$를 최소화하는 문제는 매우 잘 알려진 문제로, $a$를 $v_i$의 중앙값으로 잡으면 된다. 이 경우도 유사하게, $a$를 $x_0, x_1, x_2-K, x_3-2K, x_4-3K, x_5-3K, x_6-2K, x_7-K$의 중앙값으로 설정하면 될 것이다. $y$좌표에 대해서도 문제를 비슷하게 풀어줄 수 있다.
이런 식으로, 어떤 점이 직8각형의 어떤 점에 대응되어야 하는지 알 경우 필요한 이동거리 합의 최솟값은 $\mathcal{O}(8)$에서 $\mathcal{O}(8^2)$ 정도의 시간에 중앙값을 구해서 합을 구하는 방식으로 문제를 해결할 수 있다. 이제 모든 조합을 다 시도해보면 $\mathcal{O}(8! \times 8)$ 에서 $\mathcal{O}(8! \times 8^2)$ 정도 시간에 문제를 해결할 수 있다.
3. 산탄총
문제를 요약하면, $N \times N$ 격자의 각 칸에 (음수일 수 있는) 수가 하나 써 있고, 산탄총의 퍼지는 정도 $K$가 주어진다. 산탄총을 어떤 칸을 중심으로 사격하면 중심과 택시거리가 $K$ 미만인 칸에 대해서, 해당 칸과 중심의 택시거리가 $x$이면 해당 칸에 있는 수에 $K-x$를 곱한 수 만큼의 점수를 얻는다. 여기서, 중심은 격자 밖일수도 있다. 산탄총을 한번 사격해서 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 오른쪽 그림은 $K=3$일때 산탄총을 사격해서 얻을 수 있는 점수의 모양이다. ($1 \le K \le N \le 600$)
모든 칸을 중심으로 해서 산탄총을 쐈을 때, 각각의 점수를 구해서 그 중 최댓값을 구하면 되는 문제이다. 격자의 밖을 중심으로 하는 경우도 물론 고려해야한다. 격자에서 $K$ 이상 떨어진 곳을 중심으로 산탄총을 사격하는 경우에는 점수가 항상 0이므로 고려하지 않아도 되고, 각 좌표가 $-K$ 부터 $N+K$인 곳을 고려해서 사격하면 된다.
이제, 각 칸의 점수를 효율적으로 구하기 위해서, 중심을 오른쪽으로 한 칸 옮길 때 점수 차이를 살펴보자. 두 칸의 경계를 기준으로 왼쪽에 있는 칸의 거리는 1씩 늘어나고, 오른쪽에 있는 칸의 거리는 1씩 줄어든다. 열 번호가 왼쪽 칸 이하이면서, 거리가 $K$미만인 칸(아래 그림에서 주황색 영역)의 수의 합만큼 값이 줄어들고, 열 번호가 오른쪽 칸 이상이면서, 거리가 $K$미만인 칸(아래 그림에서 파란색 영역)의 수의 합만큼 값이 늘어난다.
이제, 파란색 영역과 주황색 영역의 합을 효율적으로 구해보자. 파란색 영역의 중심칸을 아래로 한 칸 옮기면 거리가 $K-1$인 점들이 바뀌게 된다. 여기서 위쪽 칸과 거리가 $K-1$이면서, 열 번호가 위쪽 칸 이상이고, 행 번호가 위쪽칸 이하인 점들(아래 그림에서 빨간색 영역)의 수의 합 만큼 값이 줄어들고, 아래쪽 칸과 거리가 $K-1$이면서, 열 번호가 위쪽 칸 이상이고, 행 번호가 오른쪽 칸 이상인 점들(아래 그림에서 초록색 영역)의 수의 합 만큼 값이 늘어난다. 주황색 영역도 대칭적으로 구할 수 있다.
이제, 우리는 빨간색과 초록색으로 표현된 영역인 대각선 모양의 $K$개의 칸의 합을 효율적으로 구해야하는데, 이는 중심칸이 오른쪽 아래로 내려갔을 때, 왼쪽 끝과 오른쪽 끝의 수가 더해지고 빠지는 것으로 문제를 해결할 수 있다. (그림의 노란색과 보라색 칸) 초록색 영역도 대칭적으로 구할 수 있다.
이 영역들의 합을, 좌표를 섬세하게 계산해주면 문제를 해결할 수 있다. 각 영역은 중심이 한 점에서 다른 점으로 옮겨질 때 상수번의 연산만을 하기 때문에, 시간 복잡도는 $\mathcal{O}(N^2)$이다.
4. 패턴 매칭
문제를 요약하면, 두 문자열 $A$와 $B$가 매칭된다는 것은, $A$와 $B$의 길이가 같고, $A_i = A_j$와 $B_i=B_j$가 동치라는 것을 의미한다. 텍스트 하나와 $K$개의 패턴을 주어질 때, 각 패턴이 텍스트에 등장하는 횟수를 계산하여라. (텍스트의 길이 $2\,000\,000$ 이하, 패턴의 길이 $500$이하, 패턴 길이 합 $30\,000$이하)
Aho-corasik의 패턴 매칭 알고리즘을 사용하자. 우리가 문자열의 각 문자 대신 매칭에 사용할 대상은 이전에 같은 문자가 언제 등장했는지 여부이다. 다음과 같은 관찰을 활용하자.
관찰. 어떤 문자열 $S$의 $f(S)$를 다음과 같이 정의하자.
- $f(S)$는 길이가 $S$와 같은 배열이다. $f(S)$의 $i$ 번째 값은 $S_i = S_{i-L}$을 만족하는 최소인 양수 $L$이다. (조건을 만족하는 $L$이 없을 경우 $f(S)$의 $i$ 번째 값은 0이다.)
문제에서 정의한 문자열 $A$와 $B$가 매칭되는 것은 $f(A)$와 $f(B)$가 동일한 것과 동치이다.
증명. (⇒) $f$를 정의할 때 사용한 연산은, 문자열의 두 값이 같다는 연산 뿐이기 때문에, 문제에서 주어진 $A$와 $B$에 대한 $f(A)$와 $f(B)$의 값은 동일하다.
(⇐) $A_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치를 찾아보자. $f(A)_i$가 0이면, 같은 문자가 등장하지 않는다. $f$의 정의에 따라, $A$의 $i-f(A)_i$ 번째 위치에서 $A_i$와 같은 문자가 등장하고, $i-f(A)_i$ 번째 위치에서 $i$번째 위치 사이에서는 문자가 등장하지 않는다. 이제 $i-f(A)_i$ 번째 위치 이전에서는 $A_i$와 같은 문자가 언제 등장하는지를 살펴보자. $A_{i-f(A)_i} = A_i$이기 때문에, $f(A)$ 배열의 $i-f(A)_i$ 값을 확인하는 것으로 재귀적으로 확인해 줄 수 있다.
$f(A)$와 $f(B)$의 값이 같다는 것은, $A_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치와, $B_i$와 같은 문자가 등장하는 $i$ 번째 이전의 위치의 집합이 같다는 뜻이다. 그렇기 때문에, $A_i = A_j$와 $B_i=B_j$는 동치이다.
이를 직접 사용하려고 하면, 위의 정의가 "길이가 다른 두 문자열"에 대해서는 동작하지 않는다는 것을 알 수 있다. 예를 들면 $S=abaca$와 $T=xyx$가 있다고 하자. $f(S)$는 $[0, 0, 2, 0, 2]$이고 $f(T)$는 $[0, 0, 2]$이다. 위에 정의한 문자열 매칭을 그대로 사용하면, $S$는 $T$의 첫 번째 위치에서만 매칭되는 것으로 생각되지만, 실제로는 세번째 위치에서도 매칭된다. 이는 부분문자열 $aca$와 $xyz$에서 첫번째 $a$에 해당하는 $f$값 $2$가 매칭되는 패턴 $xyz$의 $x$의 인덱스인 $0$보다 커서, $2$칸 전의 문자가 사실 같음에도 매칭할 때는 고려대상이 되지 않기 때문에 발생하는 문제이다. 특정 위치의 함수값이 인덱스보다 큰 경우는 고려 대상에서 제외해서 배열의 값을 $0$으로 바꿔줘야 하고, 이는 Aho-corasik의 failure function을 계산할 때 처리해 줄 수 있다.
이래서, (일반적인) 스트링 $f(T)$에서 패턴 $f(P)$가 언제 등장하는지 개수를 세는 문제로 바뀌었다. 기본적인 Aho-corasik 문제임으로 따로 설명하지는 않는다. 위의 failure function을 계산할 때, 자기보다 길이가 긴 인덱스 값이 등장하는 시점에 유의하자.
시간복잡도는 문자열 길이와 패턴 길이 합의 선형에 비례하는 시간복잡도가 든다.
5. Hanoi Tower
문제를 요약하면, 일반적인 하노이 타워 문제와 같이, 1번 기둥에 있는 원판을 3번 원판으로, 큰 디스크가 작은 디스크 위에 올라가지 않도록 모두 옮기는 문제이다. 단, 기존 하노이 타워는 한 기둥에서 다른 기둥으로 옮길 때, 한 기둥의 첫 번째 원판을 다른 기둥의 첫 번째 원판이 되도록 옮겼다. 하지만, 이번 하노이 타워는 한 기둥의 가운데 원판이 다른 기둥의 "가운데 원판"이 되도록 옮겨야 한다. 여기서 어떤 기둥의 가운데 원판은, 그 기둥에 쌓인 원판의 개수를 $n$이라고 할 때, $1+\left\lfloor\frac{n}{2}\right\rfloor$ 번째 원판을 말한다. 최대 이동 회수 $M = 980403$이 주어졌을 때, 디스크의 개수 $N$을 (코드를 제출하는 사람이) 정하고, 1번 기둥의 $N$개의 원판을 3번 기둥으로 옮기는 문제이다. ($N = 26$인 경우 만점이다.)
여러가지 관찰이 필요한 문제이다. 다음과 같은 관찰을 하나씩 해 보자.
관찰 1. 한 기둥의 가장 위에 있는 원판을 다른 기둥의 가장 위로 옮기려면, 해당 원판을 제외하고는 두 기둥에 다른 어떠한 원판도 존재하지 않아야 한다.
증명. $n=1$인 경우만 $1+\left\lfloor\frac{n}{2}\right\rfloor = 1$이 된다.
편의상 원판의 번호를 작은 것 부터 큰 것 까지 $1$부터 $N$까지의 번호를 붙이자. 여기서 다음과 같은 전략을 사용할 수 있다. 1번 기둥에서 3번 기둥으로 원판을 모두 옮기기 위해서는 $2$번 원판부터 $N$번 원판까지를 전부다 2번 기둥으로 옮긴다음에, 1번 기둥에서 3번 기둥으로 1번 원판을 옮기고, 2번 기둥에 놓인 $N-1$개의 원판을 다시 3번 기둥으로 옮겨야 한다.
일반적인 하노이 타워 문제는 나머지 원판들에 대해 재귀적으로 같은 방식으로 진행했겠지만, 이 문제는 다른 점이 있다. 바로, 1번 원판의 존재때문에 기둥을 빼내는 순서가 다르다는 점이다. 1~5번 원판이 쌓여있을 때 빠지는 순서는 3, 4, 2, 5(, 1)순이다. 하지만 2~5번 원판이 쌓여있을 때 빠지는 순서는 4, 3, 5, 2순이다. 즉, 어떤 기둥 위에 (고정되어서 빠지지 않는) 원판이 $0$개 있는지 $1$개 있는지에 따라서 과정이 다르게 된다. $a$, $b$, $c$번 기둥 위에 고정된 원판이 각각 $x$, $y$, $z$개 있는 상황에서 a번 기둥에서 c번 기둥까지 $N$개의 원판을 옮기는 과정을 $Mabc(N, a, b, c)$이라고 말하자. 가장 처음의 상황은 $M000(N, 1, 2, 3)$이고, $M000(N, a, b, c)$는 $M100(N-1, a, c, b)$를 수행하고, $a$에서 $c$로 1번 원판을 옮기고, $M001(b, a, c)$를 수행하게 된다. 이제 해당 기둥의 "가운데 원판"의 위치가 바뀐다.
관찰 2. 기둥 위에 고정된 원판이 1개 있는 경우, 가운데 원판을 $\left\lfloor\frac{n+1}{2}\right\rfloor$번 원판이라고 생각하면 된다. 또한, 해당 기둥의 가장 아래에 있는 원판을 옮기려면, 해당 기둥에는 고정된 원판과 가장 아래에 있는 원판을 제외하고, 남은 원판이 없어야 한다.
증명. 고정된 원판 1개를 제외하고 원판이 $n$개 있는 경우, 고정된 원판을 포함한 중심 위치는 $1+\left\lfloor\frac{n+1}{2}\right\rfloor$번째이다. 첫 번째인 고정된 원판을 제외하면, 중심 위치는 $\left\lfloor\frac{n+1}{2}\right\rfloor$번 원판이 된다. 여기서 $n \ge 1$ 일 때, 항상 $1 \le \left\lfloor\frac{n+1}{2}\right\rfloor \le n$을 만족하므로, 중심 원판은 항상 옮기려는 원판 중에 존재한다. 가장 아래쪽에 있는 원판을 꺼내려면, $n = \left\lfloor\frac{n+1}{2}\right\rfloor$ 이어야 하고, 이 경우는 $n=1$이다. 옮기려는 원판을 제외하고는 다른 원판이 존재하지 않는다.
이제 해당 과정을 기준으로 $M100(N, a, b, c)$상황을 생각해보자. ($M001$은 $M100$의 역순으로 진행된다.) 가장 아래에 있는 원판을 옮기는 과정을 생각해보자. 이도 마찬가지로, $a$번 기둥의 $N$번 원판을 제외한 원판들을 전부 $b$번 원판에 옮기고 $N$번 원판을 $c$번 원판에 옮긴 이후에, $b$번 기둥의 나머지 원판을 $c$번 기둥으로 옮기면 된다.
여기서, 과정을 잘 살펴보면 $a$번 기둥에서 마지막에 나오는 두 개의 1번 원판과 $N$번 원판을 옮길 때, $b$번 기둥을 거쳐갈 필요 없이 $c$번 기둥으로 두 원판을 차례로 옮길 수 있다는 것을 알 수 있다. ($a$번째 원판과 $c$번째 원판의 "가운데 원판"을 정의하는 홀짝성이 달라서 발생하는 일이다.) 그래서 과정을 바꿔서 $N-2$개의 기둥을 한번에 옮기는 것으로 문제를 풀 수 있다.
이제, 여기서 재귀적인 과정을 하려면 또 역시 자신 위와 아래에 있는 원판이 문제라는 것을 알 수 있다. 하지만 이 경우에는 중심 원판이 바뀌지 않기 때문에, 다음과 같은 관찰을 이용해서 재귀식을 그대로 사용할 수 있다.
관찰 3. 기둥 위에 고정된 원판이 X+K개, 아래쪽에 X개 있는 경우 가운데 원판은 기둥 위에 고정된 원판이 $K$개, 아래쪽에 $0$개 있는 경우와 같다.
증명. 원판이 $n$개 있는 경우, 고정된 원판을 포함한 중심 위치는 $1+\left\lfloor\frac{n+2X+K}{2}\right\rfloor$번째이다. $X+K$개의 고정된 원판을 제외하면, 중심 위치는 $1-K+\left\lfloor\frac{n+K}{2}\right\rfloor$번 원판이 된다. $K=0$일 때는, 위에서 $1+\left\lfloor\frac{n}{2}\right\rfloor$번째, $K=1$일 때는, 위에서 $\left\lfloor\frac{n+1}{2}\right\rfloor$번째 원판이다.
그래서 $1$번과 $N$번 원판을 더 이상 옮기지 않을 생각으로 같이 무시해주어도, 원반의 위치는 변하지 않는다. $M100(N, a, b, c)$는 $M100(N-2, a, c, b)$를 진행하고, $a$ 번 기둥에서 $c$ 번 기둥으로 원판을 두 번 옮기고, $M010(N-2, b, a, c)$를 진행해주면 된다.
이제 $M010$을 살펴보자. $M010$은 $M000$과 유사하지만, 가운데 원판에 따른 홀짝성을 고려해서 $M101(N-1, a, c, b)$를 진행하고 $a$번 기둥에서 $c$번 기둥으로 원판을 옮기고, $M101(N-1, b, a, c)$를 진행하면 된다. 하지만 이것이 최적이 아닌 경우는 위에 논의했던 대로 $a$ 번 기둥에서 $b$ 번 기둥에 홀짝성이 다른 점을 이용하면 한 번에 두 개의 원판을 옮길 수 있기 때문이다. 이를 이용해서 $a$ 번 기둥에서 $c$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기고, $a$ 번 기둥에서 $b$ 번 기둥으로 $1$번과 $N$번 원판을 옮기고, $c$ 번 기둥에서 $a$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기고, $b$ 번 기둥에서 $c$ 번 기둥으로 $1$번과 $N$번 원판을 옮기고 $a$ 번 기둥에서 $c$ 번 기둥으로 $2$번부터 $N-1$번 원판을 옮기면 된다.
이 문제에서 만점을 받으려면, 해당 아티클의 증명의 틀린 부분을 찾으면서 위 문제의 설명에서 간과되어 있는 부분을 찾아야 하는데, $M010(N, a, b, c)$의 과정은 바깥에 있는 고정된 원판을 움직일 수 없는 것을 가정하고 있지만, 사실 고정된 원판을 움직이고 원래 위치로 돌려놓으면 된다!
다음과 같은 과정을 생각하자. $N$번 원판의 위치를 고려하지 않고 $1$번부터 $N-1$번까지의 원판을 $a$ 번 기둥에서 $b$ 번 기둥으로 옮겨놓는다. 그 후 $N$번 원반이 $a$ 번 기둥에 있으면 $c$ 번 기둥으로, $c$ 번 기둥에 있으면 $a$ 번 기둥으로 옮긴 다음에, 다시 $1$번부터 $N-1$번까지의 원판을 위 과정의 역순으로 $b$ 번 기둥에서 $c$ 번 기둥으로 옮겨놓는다. 이 경우 $M010(N, a, b, c)$는 (Notation을 확장해서 관찰 3에서 $K=-1$이라는 의미로) $M(-1)01(N-1, a, c, b)$를 진행하고 $N$번 원판의 $a$, $c$위치를 바꾼 이후에 $M10(-1)(N-1, b, a, c)$를 실행한다고도 볼 수 있겠다. 여기서 $K$가 $0$이나 $1$이 아닐 경우에는, 가운데 원판이 고정된 원판을 가리킬 수 있다는 점이고, 우리는 이 경우를 특별하게 허용하기로 했다.
위쪽에서 고정된 원판을 -로 표현했다. 아래쪽에서 고정된 원판은 +로 표현하자. $1$번부터 $N$번까지의 원판을 빼내는 과정의 마지막은 $2, +, 1$번 원판 순이 되어버렸다. 이 경우에도 $1$번 원판을 빼내려면 나머지 원판을 다 빼내야 하기 때문에, 나머지 $2$번부터 $N$번 원판까지를 생각해보자. 가장 빨리 빼내는 방법은 $2$번부터 $N$번까지의 원판을 한 개 이하를 제외하고 $b$ 번 기둥에 몰아놓은 이후에 1번 원판을 $c$ 번 기둥으로 옮기는 것이다. 여기서 한 개 이하의 원판을 제외하는 이유는, 한 개의 원판이 있어도 1번 원판이 $c$번 기둥으로 들어갈 수 있기 때문이다. 여기서 우리는 1번과 2번 다음으로 빼기 어려운 $N$ 번 원판을 $c$ 번 기둥에 같이 남기는 방식을 사용할 것이다.
$3$번 원판부터 $N$ 번 원판까지를 $c$ 번 기둥에 옮기고, $2$번과 $+$ 번 원판을 $b$ 번 기둥에 옮기다. 그리고 나머지 허용된 하나의 $N$ 번 기둥을 제외한 $3$번 부터 $N-1$번 원판을 $b$ 번 기둥에 옮긴다. 나머지는 재귀적으로 $M(-1)01(N-2, b, a, c)$를 호출해주면 된다.
이를 구현하면 $N=26$일 때 $972\,051$번 연산을 사용해서 원판을 전부 옮길 수 있고, 이는 $980\,403$이라는 제한 안에 들어가는 수이다.
7월 19일 오전 9시 30분 부터 12시 10분경까지 풀배터리 검사 두번째를 했습니다. 이번에도 역시 자세한 검사 내용은 검사가 오염되기 때문에 말 하지 않겠지만, 정답이 있는 검사가 아니라 그냥 본인의 생각을 얘기하면 되는 검사였습니다. 그래서 부담스럽지 않게 제 생각을 말했던 편인 것 같습니다.
10시 50까지 정해진 검사를 하고 쉬었다가 11시 부터 검사를 다시 시작했고, 여기서는 제 과거 일들이라든가, 제가 과거의 어떤것들을 느꼈고 어떠한 계기들이 있었는가, 그리고 현재 제일 고민하고 있는 것은 어떤 것인지 등등에 대해서 말했습니다.
젠더 디스포리아와 관련된 것은 여기서 말 했는데, 제가 호르몬 치료를 받고 싶은지, 제가 검사지에 작성한 여성상과 남성상에 대해서 물어보시면서 제 여성상과 남성상은 사실 양쪽 성별 모두가 이룰 수 있는 것인데, 왜 굳이 다른 성별이 되고 싶은지 등등을 물어봐서 상세하게 대답했습니다. 저는 제가 생각하고 있는 것을 가감없이 말했습니다.
또한, 제가 가지고 있는 것으로 추측되는 다른 종류의 정신질환에 대해서도 길지 않게 물어보았습니다. 이와 관련해서 섹슈얼한 부분의 이야기가 메인이 되어서 저는 이 부분의 이야기를 되게 많이 한 편인데, 말하기 힘든 주제일텐데 자세하게 말해줘서 좋다라는 얘기도 했습니다. 보통 사람들은 이런 이야기를 정신과 의사에게도 말하기 꺼려한다고 합니다.
문제를 요약하면, i 번 정점과 i+Di 번 정점을 연결 할 때, (1≤Di≤N, i+Di가 N을 넘으면 연결하지 않음), 연결 성분의 개수를 계산하는 문제이다. 그래프를 만들어주고 DFS와 같은 방법을 이용해서 연결 성분을 세어 주면 끝나는 문제이다.
이 문제에는 같은 시간복잡도의 좀 더 간단한 풀이가 있는데, i+Di가 N을 넘는 수의 개수가 답이 된다. 이를 증명하기 위해서는 다음과 같은 관찰이 필요하다.
- 이 그래프에는 사이클이 존재하지 않는다.
만약에 이 그래프에 사이클이 존재한다고 하자. 이 때, 이 사이클에 있는 정점중 가장 낮은 번호를 가진 정점은, 자기보다 번호가 큰 정점 두 개와 연결이 되어있다. 정점을 연결하는 규칙은 수가 작은 i 번 정점과 수가 큰 i+Di 번 정점을 연결하는 것이므로 작은 i 번 정점에 두 개의 연결이 있을 수 없어서 모순이다.
이런 관찰을 통해, 최초에 정점이 존재하지 않았던 상태에서 연결 성분의 개수가 N개이고, 한 번 연결할 때 마다 연결 성분의 개수가 1씩 줄어드므로, 답은 N - (i+Di가 N 이하인 수의 개수) = i+Di가 N 초과인 수의 개수이다.
2. 이진수
문제를 요약하면, 길이 N의 0과 1로 이루어진 문자열 B와 어떤 상수 T가 주어지는데, 0과 1로 이루어진 (숨겨진) 길이 N의 문자열 A에 대해서 Ai+T와 Ai-T중 1이 하나 이상 존재하는 경우에만 Bi가 1이 되도록 만들어진 문자열이다. 단, A의 i+T번째 문자나 i-T번째 문자가 존재하지 않는 경우에는 0으로 취급한다. 사전순으로 가장 빠른 A를 찾아서 출력하는 문제이다.
주어진 입력에 해당하는 A가 존재하는지 (문제에서 요구하지는 않았지만) 찾는 알고리즘을 생각하도록 하자.
- Bi-T나 Bi+T중 0이 있다면, Ai는 0이어야 한다.
만약 Ai가 1인 경우, Bi-T와 Bi+T가 (존재한다면) 1이어야 하기 때문에, 만약 이 두 수 중 0이 있으면, Ai는 0이어야 모순이 발생하지 않는다.
- Bi-T와 Bi+T중에 0이 없다면, Ai를 1로 두어도 "상관 없다." 여기서 "상관 없다"의 의미는, A가 만약에 존재한다면, Ai가 1인 답도 존재한다는 의미이다.
만약에 Ai가 0인 답이 존재한다고 하자. 이 Ai를 1로 바꾸게 되면, Bi-T와 Bi+T만 영향을 끼치고, 이 두 숫자는 이미 1이기 때문에, 해당하는 칸에도 영향을 끼치지 않는다. 그래서 Ai가 1이게 되는 답이 존재한다.
이 두 가지 사항을 이용해서, A가 존재하는지 찾는 알고리즘을 만들었으면, 사전순으로 가장 빠른 A를 찾는 알고리즘은, 가장 첫 자리가 0인 A가 존재하는지 확인하고, 존재한다면 가장 첫 자리를 0으로, 존재하지 않는다면 가장 첫 자리를 1로 설정한다. 마찬가지로 (첫 자리가 고정된 A에 대해) 둘째 자리가 0인 A가 존재하는지 확인하고, 존재한다면 가장 첫 자리를 0으로, 존재하지 않는다면 1로 설정한다, 이를 계속 반복하는 것이 문제의 풀이가 될 것이다. 여기까지의 알고리즘을 구현하면 O(N2) 시간 복잡도의 풀이를 얻을 수 있다.
이 알고리즘의 시간을 줄이는 법은, A가 존재하는지 확인하는 알고리즘은 Ai의 값 하나의 변경에 대해서는 작은 영향을 끼친다는 것을 관찰하는 것이다. 주어진 입력에 해당하는 최대의 A를 만들자. 그 후, 앞에서부터 살펴보면서, 1이 있으면 해당 1을 0으로 바꿀 수 있으면 바꾸는 과정을 반복하면 문제를 해결할 수 있다. (이는 Ai가 0인 A가 존재하는지 확인하고, 가능하면 0으로 설정하는 과정과 동일하다.) 1을 0으로 바꿀 수 있는지 여부는 Ai를 바꾸었을 때, B라는 문자열 전체, 특히 Bi-T와 Bi+T가 바뀌지 않을 것을 의미한다. 이를 위해서 추가적으로 Ai-2T와 Ai+2T 칸을 확인 해 줘야 한다. 이 과정을 구현하면 O(N) 시간 복잡도의 풀이를 얻을 수 있다.
3. No Cycle
문제를 요약하면, 그래프가 주어지는데 M개의 간선들은 방향성이 있고, K개의 간선들은 방향성이 없다. 이 때, 방향성이 없는 간선에 적당히 방향을 줘서 사이클이 없도록 해야한다. 단, 답이 여러개 존재하는 경우에 사전순으로 가장 빠른 답을 출력해야한다. 여기서 답은 길이 K의 0과 1로 이루어진 문자열인데, i 번째 방향성이 없는 간선은 두 개의 정점 쌍 (ui, vi)로 주어지며, ui→vi로 방향을 주면 답의 i번째 문자가 0이고, vi→ui로 방향을 주면 답의 i번째 문자가 1이다.
2번 문제와 유사한 종류의 관찰을 요구한다. 일단 답이 존재하는지 아닌지 찾는 알고리즘에 대해서 확인 해 보자. 방향이 주어진 M개의 간선에 대해서는 사이클이 없기 때문에 위상정렬을 실행할 수 있고, 해당 위상정렬에 대해 뒤쪽에 있는 간선을 앞쪽에 있는 간선으로 이어주면 항상 사이클이 없는 답을 찾을 수 있다.
사전순으로 가장 빠른 것을 찾는 알고리즘은 2번 문제에 설명된 대로 가장 첫 자리를 0인 답이 존재하는지 아닌지 확인하고, 존재한다면 0, 존재하지 않는다면 1로 설정한 뒤에, 둘째 자리에 대해서도, 셋째 자리에 대해서도 마찬가지로 같은 방법으로 문제를 해결하는 것이다. 이 문제에서는 이미 방향성이 주어진 간선이 사이클이 존재하지 않는 경우 항상 답이 존재하기 때문에, i 번째 자리를 정하고 있다면 i+1 번째 이후의 모든 간선을 무시하고, i번째 간선을 정방향으로 넣었을 때 지금까지 들어가있는 간선에 사이클이 존재하지 않는지 여부를 확인 해 주는 것으로 문제를 해결할 수 있다. 시간복잡도는 O(MK+K2)이다.
4. 예약시스템
문제를 요약하면, 사람이 2M명 있고 그룹이 N개 있다. 각 사람은 그룹 중 하나에 속해있으며, 스트레스 지수가 있다. 이 2M명의 사람을 2×M 모양의 방에 배치하려고 하는데, 그룹이 다른 두 사람이 인접한 방에 배치된 경우에는 충돌이 발생하고, 두 사람의 스트레스 지수의 합만큼 비용이 발생한다. 방에 사람을 적당히 배치해서 비용의 합을 최소화 하는 문제이다. 단, 같은 그룹끼리는 서로 연결되어 배치되어 있어야 하고, 한 그룹에는 5명 이상의 사람이 속해있다.
문제를 생각하기 용이하게 해주도록 배치의 비용을 다르게 나타내어 보자. 사람을 기준으로 생각했을 때, 해당 사람이 만드는 충돌의 개수는, 그 사람에게 인접한 다른 색을 가진 사람의 개수랑 같다. 그렇기 때문에, 총 비용은 모든 사람의 (해당 사람과 인접한 색이 다른 사람 수)×(해당 사람의 스트레스 지수)의 합이다.
이제 정답이 가질 수 있는 배치를 생각 해 보자, 첫번째로 2×M 모양에서 첫번째 열과 마지막 열은 특수하게 다루어져야 하는데, 그룹의 경계를 생각할 때 가장 왼쪽 혹은 가장 오른쪽 열은 그룹의 경계이지만 충돌이 발생하지는 않는다. 그렇기 때문에, 우리는 이 두 열에 대한 특수한 배치를 증명할 것이다.
- 첫번째 열과 마지막 열의 두 사람이 같은 그룹인 정답이 존재한다.
만약에 첫번째 열을 차지하는 두 그룹이 다른 사람인 정답이 존재한다고 하자. 이 둘은 크기가 더 작은 그룹이 존재한다. 해당 그룹을 A라고 하자. 모든 그룹은 연결되어야 하기 때문에, A는 일직선으로 존재하고 B도 A의 맞은 편 행에 일직선으로 존재하게 된다. (A가 끝난 이후에는 아무렇게나 존재할 수 있다.) 각 사람에 대해서 다음 그림과 같이 번호를 붙이자. (A3가 A의 가장 왼쪽 사람, A2, A1이 A의 가장 오른쪽 사람, A1의 오른쪽 사람이 C이고, B1, B2가 B의 가장 왼쪽 사람, B3가 A1의 맞은편 행에 있는 사람이다.)
여기서 연결관계가 바뀐 사람들의 비용차이를 계산 해 보자. 여기서 B와 C가 같은 그룹일 수 있음에 유의하여라.
* A1: 발생하는 충돌이 1개 줄었다. (B3, C → B2)
* A2: 발생하는 충돌이 1개 늘었다. (B1)
* A3: 발생하는 충돌이 1개 줄었다. (B1)
* B1: 발생하는 충돌이 1개 혹은 0개 늘었다. (A3 → A2, C)
* B2: 발생하는 충돌이 1개 줄었다. (A1)
* B3: 발생하는 충돌이 1개 줄었다. (B1)
* C: 발생하는 충돌이 1개 혹은 0개 줄었다. (B1)
바꿔서 코스트가 가장 커지는 경우는 발생하는 B1에서 발생하는 충돌이 1개 늘고, C에서 발생하는 충돌이 바뀌지 않는, B와 C가 다른 그룹인 경우이다. 이 경우를 상정하자.
최초 배치에서, A1은 충돌이 2개 발생하고, A2는 충돌이 1개 발생했다. 그렇기 때문에 위의 답이 최적이려면 A2의 스트레스 지수는 A1의 스트레스 지수보다 크거나 같아야 한다. 또한, B1과 B2는 모두 충돌이 1개 발생했기 때문에, B1의 스트레스 지수가 B2의 스트레스 지수보다 작거나 같은 답이 존재한다. 이런 사항을 고려해보면, A1과 B1에서 발생하는 비용의 증가는 A2와 B2에서 발생하는 충돌의 감소가 모두 해결해 줄 수 있고, 추가로 A3와 B3 혹은 C에서 발생하는 충돌의 감소가 스트레스 지수를 더 줄여준다. 그렇기 때문에, 첫번째 열과 마지막 열의 두 사람이 같은 그룹인 정답이 존재한다.
위와 같은 증명으로, 우리는 첫번째 열과 마지막 열의 두 그룹을 고정할 수 있다. 해당 그룹 전체에서 발생하는 스트레스 지수에 대해서 생각하자. 해당 그룹의 경계에서는 최소 두 명의 스트레스 지수가 발생한다. 홀수인 경우에는 (가장 작은 스트레스 지수)*2 + (2번째로 작은 스트레스 지수)가 되고, 짝수인 경우에는 (1, 2번째로 작은 스트레스 지수의 합)이 된다.
이제 해당 그룹이 아닌 내부에 존재하는 그룹에 대해서 생각하자.
- 해당 그룹이 두 열 이상에 대해 두 행의 방을 모두 차지하고 있는 경우. (2×2 방을 차지하고 있는 경우)
두 열을 기준으로 왼쪽과 오른쪽으로 분리하게 되고, 왼쪽 경계와 오른쪽 경계에 있는 사람들이 충돌하게 된다. 해당 경계에 두 사람만 존재하는 것이 가능하므로, 왼쪽 경계에 두 사람 오른쪽 경계에 두 사람이 존재하는 경우가 해당 그룹이 가질 수 있는 경계의 최솟값이다.
* 해당 그룹의 크기가 홀수일 경우, 한쪽 경계에는 두 행을 모두 차지하고, 다른쪽 경계에는 한 행만 차지하는 경우가 된다. (사진에 있는 2번째 그룹에 해당된다.) 이 경우, 경계에 스트레스 지수가 낮은 사람을 배치하면 해당 그룹의 스트레스 지수는 (가장 작은 스트레스 지수)*2 + (2, 3, 4번째로 작은 스트레스 지수의 합)이 된다.
* 해당 그룹의 크기가 짝수일 경우, 양쪽 경계에서 두 행을 모두 차지하는 것이 스트레스 지수의 최솟값이다. 이 경우 해당 그룹의 스트레스는 (1, 2, 3, 4번째로 작은 스트레스 지수의 합)이 된다.
* 해당 그룹의 크기가 짝수이지만, 양쪽에 와야하는 사람 수가 홀수라서 양쪽 경계에서 두 행을 모두 차지하지 못하는 경우가 있을 수 있다. 이 경우 그룹의 스트레스의 지수는 (1, 2번째로 작은 스트레스 지수의 합)*2 + (3, 4번째로 작은 스트레스 지수의 합)이다.
- 해당 그룹이 한 열 이하에 대해 두 행의 방을 모두 차지하고 있는 경우.
나머지 양 끝쪽에 존재하는 방에 대해서는, 충돌이 적어도 두 번 이상 일어나고, 칸 하나를 제외한 나머지 칸에 대해서도 충돌이 한 번 이상 일어나게 되기 때문에, 스트레스 지수의 합은 (1, 2번째로 작은 스트레스 지수의 합)*2 + (3, 4번째로 작은 스트레스 지수의 합) 이상이 되게 된다. 그러므로 해당 경우는 스트레스 지수가 위에 말한 경우보다 크게 된다.
이제 위와 같은 상황이 가능한 배치가 존재하는지 확인 해 보자. 홀수 그룹의 방을 항상 두 개씩 인접해서 배치하는 전략을 사용하면, 위에서 말한 모든 그룹의 스트레스 크기를 최소화하는 배치를 할 수 있다. 이렇지 못하는 경우는, 홀수 크기의 그룹이 정확히 2개이며 왼쪽 끝과 오른쪽 끝에 가야하는 경우이고, 이 경우에는 양쪽에 와야 하는 사람 수가 홀수인 짝수 크기 그룹과 같은 형태로 배치할 수 있다.
이 방법으로 오른쪽과 왼쪽 끝에 가야하는 그룹을 정하고, 나머지의 스트레스 지수를 더하는 방식을 사용하면 O(M3) 혹은 O(M2)의 시간복잡도가 발생하게 된다. 이제 이 과정을 최적화 하자.
홀수 크기의 그룹이 정확히 2개이며, 왼쪽 끝과 오른쪽 끝에 가야하는 경우를 제외하고는, 각 그룹의 스트레스 크기는 최소화 되기 때문에 총 비용은 (두 그룹을 제외한 각 그룹의 가운데에서 스트레스 지수) + (두 그룹의 양쪽 끝에서 스트레스 지수)이며, 이를 다시 쓰면, (모든 그룹의 가운데에서 스트레스 지수) - (두 그룹이 양쪽 끝에 왔을 때 줄어드는 스트레스 지수의 양)이 된다. 각 그룹의 양쪽 끝에 왔을 때 줄어드는 스트레스 지수의 양은 고정되어있기 때문에, 이 중 최댓값 두 개를 골라서 전체 스트레스 지수에서 빼주는 방식을 사용하면 총 O(N+M)의 시간복잡도를 얻을 수 있다.
문제의 조건 중에, 각 그룹끼리 연결될 것과, 그룹의 크기가 5이상일 것이라는 조건이 있다. 왜 이런 조건이 존재하는지는 다음과 같은 예제로 알아볼 수 있을 것 같다.
5. 차이
문제를 요약하면, 쿼리가 다음과 같이 두 종류 들어오고, 2번 종류 쿼리에 대해 답을 해야한다.
- 1번: i, j, v가 주어진다. 이는 Xi-Xj=v라는 정보를 의미한다.
- 2번: i, j가 주어진다. 지금까지 1번 쿼리로 들어온 정보들을 토대로 Xi-Xj의 값을 계산해야 한다. 여기서 계산이라고 함은 다음과 같은 과정으로만 재귀적으로 정의된다.
* Xi-Xj=v나 Xj-Xi=-v가 1번 쿼리로 주어졌다면, Xi-Xj=v라고 계산할 수 있다.
* Xi-Xj=v와 Xj-Xk=u라고 계산할 수 있으면, Xi-Xk=v+u라고 계산할 수 있다.
위의 과정을 (유한번) 재귀적으로 사용해서, Xi-Xj의 값을 계산할 수 있는지와, 계산할 수 있다면 계산 결과가 유일한지를 판단하여라. (1번으로 주어진 정보에 모순이 존재할 수도 있다.)
위와 같은 문제에서, Xi-Xj의 값을 계산할 수 있는지를 먼저 살펴보자. 계산에 관한 정보를 빼고 보면, 위의 설명은 i와 j가 연결되어있는지 아닌지에 관한 설명이다. 그렇기 때문에, 잘 알려진 Disjoint-set과 같은 알고리즘을 사용해서 문제를 해결할 수 있다.
이제, 값을 계산해 보자. Disjoint-set알고리즘은, 트리에서 자신의 부모 노드를 가지고 있는 알고리즘이다. 그렇기 때문에, 자신의 부모 노드와 자신과의 차이를 누적하면, 자신과 루트 노드의 차이를 알 수 있다. Disjoint-set알고리즘 상의 트리에서 노드 i의 부모가 p이고 루트가 r인 경우에, Xr-Xp는 재귀적으로 구할 수 있고, Xp-Xi는 Disjoint-set에서 자기 부모를 저장하는 배열에 자기 부모와 자기 자신의 차이를 추가적으로 저장해서 차이를 구할 수 있다. 2번 쿼리가 들어왔을 때, i와 j가 같은 연결성분에 들어있지 않다면, 값을 계산할 수 없다. 하지만 같은 연결성분 안에 있다면, Xr-Xi와 Xr-Xj를 계산해서 (Xr-Xj)-(Xr-Xi)이 답이 된다.
이제, 1번 쿼리를 생각해 보자. 하는 과정에서, 서로 다른 두 연결성분에 들어 있으면, 해당 두 연결성분을 Xi-Xj=v라는 관계로 추가로 연결 해 주면 된다. 하지만, 같은 연결성분에 들어있는 경우 계산 결과에 모순이 발생할 수 있다. 이 때는, Xi-Xj=v가 맞는지 2번 쿼리와 같은 방법으로 실제로 확인해 주고, 모순이 발생한 경우에는 해당 연결성분 전체에서 모순이 발생한다고 생각할 수 있다. i,j를 포함하는 Xi-Xj의 결과로 두 개 이상의 답이 존재하는 경우에는 같은 연결 성분에 속한 a, b에 대해서도 Xa-Xi + Xi-Xj + Xj-Xb = Xa-Xb의 결과가 두 개 이상이 된다. 그렇기 때문에 루트노드 쪽에 해당 연결성분에 모순이 발생하는지 아닌지를 체크해 주면 된다. 시간 복잡도는 Disjoint-set 알고리즘과 같은 O(Mα(M)) 이다.
아래는 문제에 대한 코드이다.
1번
#include <cstdio>
#include <vector>
using namespace std;
int solve(const vector<int>& V)
{
int N = (int)V.size();
int ans = 0;
for(int i=0; i<N; ++i)
if(i + V[i] >= N) ++ans;
return ans;
}
int main()
{
int T; scanf("%d", &T);
for(int t=1; t<=T; ++t)
{
int N; scanf("%d", &N);
vector<int> V(N);
for(int i=0; i<N; ++i) scanf("%d", &V[i]);
printf("Case #%d\n%d\n", t, solve(V));
fflush(stdout);
}
}
2번
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string solve(int T, const string &B)
{
int N = (int)B.length();
string A(N, '1');
for(int i=0; i+T<N; ++i)
{
if(B[i+T] == '0') A[i] = '0';
if(B[i] == '0') A[i+T] = '0';
}
for(int i=0; i<N; ++i) if(A[i] == '1')
if(i-T < 0 || (i-2*T >= 0 && A[i-2*T] == '1'))
if(i+T >= N || (i+2*T < N && A[i+2*T] == '1'))
A[i] = '0';
return A;
}
int main()
{
int TC; cin >> TC;
for(int t=1; t<=TC; ++t)
{
int N, T; cin >> N >> T;
string B; cin >> B;
cout << "Case #" << t << '\n' << solve(T, B) << endl;
}
}
3번
#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;
enum State {WHITE, BLACK, GRAY};
bool dfs(const vector<vector<int>>& conn, vector<State>& visit, int a)
{
if(visit[a] == BLACK) return false;
if(visit[a] == GRAY) return true;
visit[a] = GRAY;
for(int x: conn[a])
if(dfs(conn, visit, x))
return true;
visit[a] = BLACK;
return false;
}
bool hasCycle(const vector<vector<int>>& conn)
{
vector<State> visit(conn.size(), WHITE);
for(int i=0; i<(int)conn.size(); ++i)
if(dfs(conn, visit, i))
return true;
return false;
}
string solve(int N, vector<pair<int, int> > O, vector<pair<int, int> > U)
{
vector<vector<int> > conn(N);
for(auto [u, v]: O) conn[u-1].push_back(v-1);
string ans;
for(auto [u, v]: U)
{
--u; --v;
conn[u].push_back(v);
if(hasCycle(conn))
{
conn[u].pop_back();
conn[v].push_back(u);
ans += '1';
} else ans += '0';
}
return ans;
}
int main()
{
int T; cin >> T;
for(int t=1; t<=T; ++t)
{
int N, M, K; cin >> N >> M >> K;
vector<pair<int, int> > O, U;
for(int i=0; i<M; ++i)
{
int a, b; scanf("%d%d", &a, &b);
O.emplace_back(a, b);
}
for(int i=0; i<K; ++i)
{
int a, b; scanf("%d%d", &a, &b);
U.emplace_back(a, b);
}
cout << "Case #" << t << '\n' << solve(N, O, U) << endl;
}
}
4번
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
long long solve(vector<vector<int>> V)
{
vector<pair<int, int> > O; // stress, lift
vector<tuple<int, int, int> > E; // stress, lift, special
for(auto& x: V)
{
sort(x.begin(), x.end());
if(x.size()%2 == 0)
{
int stress = x[0] + x[1] + x[2] + x[3];
int lift = x[2] + x[3];
int special = x[0]*2 + x[1]*2 + x[2] + x[3];
E.emplace_back(stress, lift, special);
}
else
{
int stress = x[0]*2 + x[1] + x[2] + x[3];
int lift = x[2] + x[3];
O.emplace_back(stress, lift);
}
}
long long ans = 0;
if(O.size() != 2 || E.size() != 0) // handle normal case, careful not to include OE...EO
{
vector<int> lifts;
for(auto [st, li, sp]: E) lifts.push_back(li);
if(O.size() == 2) lifts.push_back(max(get<1>(O[0]),get<1>(O[1])));
else for(auto [st, li]: O) lifts.push_back(li);
sort(lifts.rbegin(), lifts.rend());
for(auto [st, li, sp]: E) ans += st;
for(auto [st, li]: O) ans += st;
ans -= lifts[0] + lifts[1];
}
if(O.size() == 2) // special case
{
long long spc = 0;
for(auto [st, li, sp]: E) spc += sp;
for(auto [st, li]: O) spc += st-li;
if(ans == 0) ans = spc;
else ans = min(ans, spc);
}
return ans;
}
int main()
{
int T; scanf("%d", &T);
for(int t=1; t<=T; ++t)
{
int N, M; scanf("%d%d", &N, &M);
vector<vector<int> >V(N);
for(int i=0; i<N; ++i)
{
int s; scanf("%d", &s);
V[i].resize(s);
for(int j=0; j<s; ++j) scanf("%d", &V[i][j]);
}
printf("Case #%d\n%lld\n", t, solve(V));
}
}
5번
#include <cstdio>
#include <vector>
using namespace std;
struct UFD
{
vector<pair<int, long long> > ufd;
explicit UFD(int N): ufd(N) {
for(int i=0; i<N; ++i) ufd[i] = {i, 0LL};
}
bool isValid(int x)
{
return ufd[Find(x).first].second == 0LL;
}
void setInvalid(int x)
{
ufd[Find(x).first].second = -1LL;
}
pair<int, long long> Find(int a)
{
auto [p, u] = ufd[a]; // x[p]-x[a] = u;
if(a == p) return {p, u};
auto [r, v] = Find(p); // x[r]-x[p] = v;
return ufd[a] = {r, u+v};
}
void Union(int a, int b, int t)
{
auto [pa, va] = Find(a); // x[pa]-x[a] = va
auto [pb, vb] = Find(b); // x[pb]-x[b] = vb
if(!isValid(a) || !isValid(b))
{
ufd[pb].first = pa; setInvalid(pa);
}
else if(pa == pb)
{
if(vb-va != t) setInvalid(pa);
}
else ufd[pb] = {pa, va-vb+t};
}
enum Cases {No, Yes, Any};
pair<Cases, long long> diff(int a, int b)
{
auto [pa, va] = Find(a); // x[pa]-x[a] = va
auto [pb, vb] = Find(b); // x[pb]-x[b] = vb
if(pa != pb) return {Any, 0LL};
else if(!isValid(a)) return {No, 0LL};
else return {Yes, vb-va}; // vb-va = (x[p]-x[b])-(x[p]-x[a]) = x[a]-x[b]
}
};
void solve()
{
int N, Q; scanf("%d%d", &N, &Q);
UFD ufd(N);
while(Q--)
{
int c; scanf("%d", &c);
if(c == 1)
{
int u, v, t; scanf("%d%d%d", &u, &v, &t);
ufd.Union(u-1, v-1, t);
}
else
{
int u, v; scanf("%d%d", &u, &v);
auto [res, val] = ufd.diff(u-1, v-1);
if(res == ufd.No) puts("CF");
else if(res == ufd.Any) puts("NC");
else printf("%lld\n", val);
}
}
return;
}
int main()
{
int T; scanf("%d", &T);
for(int i=1; i<=T; ++i)
{
printf("Case #%d\n", i);
solve();
}
}
내가 가지고 있는 정신 장애가 생각보다 심각한 수준인 것 같은데 고지능에 가려져서 그걸 나도 의사도 주위 사람도 인지하지 못했던 것 같음. 다음 풀 배터리 검사 때 충분히 많이 얘기해 볼 생각임. 호르몬 치료는 받을 수 있더라도 미뤄 둘 생각임. 내가 겪은 우울증이나, 나의 특성 중 하나인 합의에 의한 BDSM과 나를 MtF로 정체화한 이런 것들도 결국에 내가 가지고 있는 한 가지 정신장애가 밖으로 발현되었던 것 중 하나인 것 같음. 원인은 아동기의 학대로 생각되지만, 당연히 장담할 수는 없음. 후에 풀 배터리 검사를 진행하고 정신과 의사와 상담한 후에 근황을 추가적으로 올릴 것 같음. 검사 결과가 어떻게 나오든 나 자신을 재정체화 하는 것은 피할 수 없는 일이라고 생각하고, 남에게 어떻게 보이는 지를 포함한 사회성 필터로 잘 조절해 볼 생각. 솔직히 말하면, 나에 대해서 파면 팔수록 무언가가 나와서 되게 무서움. 나에 대해서 알아간 이후에 이런 점을 이해할 수 있으면 좋겠지만, 나에 대한 완전한 이해라는 건 존재할 수 없는 것 같음... 이 삽을 파기 시작했으면 끝까지 파야 한다고 생각하고, 나는 지금 나에 대해 알아가는 과정에서 매우 혼란스러움. 그 과정에서 원인을 기존에 몰랐던 우울함과 불안감은 많이 해소된 것 같지만, 이제 자아를 찾는 과정에서 다시 혼란을 겪을 것으로 예상함. 내가 아예 다른 내가 되는 건 아니고, 이전의 기억이나 감정을 잃어버리는 것도 아니며, 최소한의 사회성이 없는 것도 아니니, 나를 이전과 같이 대해도 되고 잘 맞출 수도 있음. 하지만 내 선호에 관련된 문제를 처음부터 다 다시 짜 맞춰야 할 것 같고, 무엇보다 지금은 사람과 터놓고 얘기하기 힘듦. 내가 예전에 한 말 중 고지능은 정신병이란 말을 한 적이 있는데, 그냥 생존자 편향인 것 같음. 내 주위에서 정신병자를 사회적으로 만날 수 있으려면, 그 사람은 충분히 고지능 이어야 하고, 솔직히 나도 그런 케이스가 아닐까 하고 생각함. 이전에는 겸손하게 말했지만, 좀 객관적으로 말하면 나는 특정 분야에서 4-5 시그마의 복합적인 능력을 갖추고 있는 것 같고 그냥 그 지능으로 많은 걸 해결하려고 하다가 괴리감이 생긴 것 같음.
여담으로, 일본어 텍스트 및 목소리를 현재 거의 이해할 수 없는 상황인데 내가 겪은 병증과 관련이 있는지 없는지도 확인해 볼 필요가 있을 것 같음. 검사를 할 때 같이 정리해서 전달할 생각임.
7월 9일에 검사지를 작성한 후, 오늘 오전 9시 반부터 정오까지 풀 배터리 검사를 받고 왔습니다. 검사에 대해서 자세하게 기술하게 되면 검사가 "오염"되기 때문에 자세한 검사에 관해서는 서술하지 않을 것이지만, 기본적인 검사와 인지능력 검사 등을 위주로 오늘 검사를 진행했습니다. 7월 19일 오전 9시 반에 추가로 검사를 진행할 예정이고, 오늘 진행한 것과 다르게 부담 가지지 않고 답하는 검사라고 말해주셨습니다.
2021년 7월 6일 화요일에 카이스트 파팔라도 의원을 다시 방문했습니다. 3주간의 정신과적인 상태에 관해 얘기했습니다. 제가 3주간 느꼈던 것을 가감 없이 얘기했습니다.
선생님은 제가 느끼는 Gender Dysphoria가 어떤 것에 관련되어 있는지 자세하게 질문했습니다. 구체적으로 어떤 모습이 되고 싶어 하는지, 가령이면 미소년이 되는 것은 상관이 없는지라든가, 제가 성기에 대해서는 어떤 불일치감을 느끼는지, 그리고 성 재지정 수술을 받을 의향이 있는지 같은 것들을 물어봤습니다.
실제로 호르몬 치료에 대해서는 우호적으로 대답해 주셨으나, 호르몬 치료를 하는 것 자체에 대해서는 절차를 모른다고 하셨습니다. 다른 사람의 호르몬 치료 절차가 어떻게 되는지도 많은 질문을 했습니다.
그래서, F 코드를 받아야 호르몬 검사를 할 수 있다고 말했습니다. 구체적으로 F64.0 코드를 많이 받아서 호르몬 치료를 한다고 전달했고, F64.1 같은 경우에는 잘 호르몬 치료를 지원해주지 않는다고 알고 있다고 얘기를 했으며, 나머지는 잘 모른다고 대답했습니다.
실제로 치료를 어떻게 진행할 거냐고 물어봐서, 사람들은 대전의 민들레의원이나 은평구의 살림 의원을 많이 간다고 말했고, 대전에서 병원에 다닐 것 같다고 말했습니다.
F 코드를 받는데 종합심리검사(풀 배터리 검사)가 필요하지는 않지만, 확실히 하기 위해서, 그리고 서류상의 불편함을 없애기 위해서 풀배터리 검사를 하는 것이 좋다는 의견을 전해주셔서, 종합심리검사를 잡았습니다. 풀배터리 검사는 7월 14일입니다. 결과는 2주 정도 걸린다고 합니다. 일부 작성할 수 있는 검사지를 미리 주셨으며, 7월 14일 이전에 검사지를 작성해서 가야 합니다.