Toolofv 님의 블로그

문제소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오. 예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40..

팔레스타인과 이스라엘, 중동 세계의 갈등은 역사가 깊다. 2023년 하마스가 선전포고없이 이스라엘에 기습침공을 가했다. 중동에서의 역사에 대한 흐름을 보지 않고, 이 사건부터 보면 하마스란 무장정파가 마치 IS같은 테러조직이라고 생각하기 쉽다.(IS는 이슬람에서도 배척당한다.) 실제로 과격한 것은 사실이지만, 전후사정을 알고 보면 이 바닥은 함부로 선악의 판단을 내리면 안되겠다는 생각을 갖게 된다. 도대체 어디서부터 잘못된 건지 싶은 미궁속이다. 또 이 과정이 아직도 꽤 긴 시간동안 지속되리란 점이 안타깝다. 유대인도 사실 그간의 서양 역사를 보면 많은 탄압을 받아왔다. 13세기 몽골이 활약할 때도 백인들은 애꿎은 유대인들을 털었으며, 무슨 일만 터지면 유대인은 쪼이는 닭이었다. 러시아의 포그롬(18..

사람이 살아간다고 한다. 하지만 사실 하루하루 죽어간다는 말이 더 정확한 문장이라 생각한다. 사람이 태어나서 살다가 결국 죽는 것은 과학, 인류사를 들이댈 필요도 없이 자명한 그 누구도 피해갈 수도, 피해가지도 못할 100% 확신할 수 있는 사실이다. 그런데 또 우리는 한번도 죽음을 경험해본 적이 없다. 2024년, 지구에 현재 살고 있는 사람 중, 죽음을 경험한 이는 없다. 이 것도 100% 확신할 수 있다. 그래서인지 우리는 경험해보지도 않은 불확실한 죽음에 대한 생각을 접어두고, 마치 영원히 살 것처럼 죽음에 대한 생각은 예외처리해버리기로 한다. 죽지 않을 것처럼 일을 하고, 돈을 벌고, 즐겁지도 않은 행사에 참여하고, 해도 좋고 안해도 그만인 일들도 열심히 하며 살아가게 된다. 이 것이 해서는 안..

문자열 검색 알고리즘은 우리가 자주 쓰는 'cntl + F'에 대한 알고리즘이다.현재 쓰이는 것은 크게 3가지가 있는 것 같다. 0. 브루트포스 - 한글자, 한글자 매칭해가며 찾는 방법 - $O(nm)$ 1) 라빈-카프 알고리즘에서 해시값이 같을 때, 마지막 검증수단으로 쓰이기도 함.1. KMP 알고리즘(Knuth–Morris–Pratt, KMP) - $O(n+m)$2. 라빈-카프 알고리즘(Rabin_karp) - $O(n+m)$  혹은 $O(nm)$ 3. 보이어-무어 알고리즘(Boyer-Moore) - 일반적 $O(n)$보다 적다고 함. 혹은 최악의 경우 $O(nm)$  [Python] 백준 - 1786 찾기문제워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러..

문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램..

화북지방의 전진  전진의 부견(357~385 )이 부건 사후, 황제에 오른 부생(355~357)을 보내고(?), 황제에 올라 내부를 다지고 영토를 차츰차츰 키워가면서 화북지방의 대세는 전진이 장악한다. 사마씨의 서진 멸망부터 복제된 패턴대로 5호16국시대 각 국가의 최대의 적(?)은 가족 및 친족이었다. 물론 이후에도 이 문제는 근대 이전 국가에서 불거질 경우도 있었지만, 5호16국시기에는 아예 갈등을 조정하거나, 최소화하는 장치가 아예 없었던 듯. 물론 부견부터가 부생을 쳐내고 오른 황제였던 것도 있지만 367년에 전진의 황족들이 대규모 반란(오공의난)을 일으켰다고 한다.  368년에 부견은 반란을 평정하고 전연과 동진의 낙양전투(369)에 개입해 전리품을 얻고 전연을 지원한다. 이 당시 부견에게는 왕..

조지 오웰은 1903년에 인도에서 태어나 영국에서 어린 시절을 보낸 후, 미얀마에서 경찰일을 시작한다. 식민지에서 근무하는 데 염증을 느껴 경찰을 사직하고, 파리와 런던에서 접시닦이, 가정교사 등 온갖 굳은 일을 하고, 영국으로 돌아가 부랑자 생활을 하는 시기를 보낸다. 이 시기의 경험을 토대로 1933년에 을 발표한다.  1934~1935년에 파트타임 서점 점원을 하면서 작가로서의 작업을 이어갔고, 1936년에 아일린 오쇼네시와 결혼한다. 그녀는 스페인 내전에 참전한 조지 오웰을 찾아와 스페인 내전의 바르셀로나 5월 사건의 격랑에 같이 휘말리기도 한다. 1937년 스페인 내전에 참전하여 POUM(Partido Obrero de Unificación Marxista, 통합 마르크스주의 노동자당) 의용군 ..

조지 오웰은 1903년 6월 25일에 인도에서 태어났다. 첫 돌을 맞기 전 영국으로 돌아와 어린 시절을 보내고, 경찰간부로서 미얀마에 근무하였다고 한다(1922~1927). 식민지에서 근무하는 데에 염증을 느껴 경찰을 사직하고, 파리와 런던에서 접시닦이, 가정교사, 서점 점원 등 온갖 굳은 일을 하고, 부랑자 생활을 하는 시기를 보낸다. 1933년에 이 책 이 발표되었고, 1938년에 스페인 내전에 참전했던 시기의 경험을 기술한 를 발표했다. 이후로 (1945), (1949)을 남겼다. 후반기의 조지 오웰의 책들은 이 책과 카탈로니아 찬가에서 느껴지는 유머가 없어진 것 같다.  조지 오웰은 밑바닥에서 부딪히는 온갖 너절한 일들을 겪고, 이 세상에 잠시 와서 그의 여행의 기록을 남겨두었다.밑에서 생동하는 ..

문제N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자. 입력 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 ..