Toolofv 님의 블로그

문제체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?입력입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.출력각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다. 필요한 도구  1. BFS 알고리즘..

문제그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호 u, v (u ≠ v)가 빈 칸을 사이에 두고..

군사력은 약해도 경제 강국이었던 송나라  송나라(960~1279)는 5대10국시대 후주(951~960)의 장군 조광윤이 제위를 선양받아 세운 나라다. 송나라 때 거란의 요나라(916~1125), 여진의 금나라(1115~1234), 전 세계를 호령한 몽골의 원나라까지 무력이 강한 나라들과 같이 존속했던 한족의 나라였다. 워낙 강한 나라들과 같이 존재해서 군사적으로 나약한 이미지가 있지만 양쯔강 이남의 강남 지역을 개발하면서 이룬 생산력 증대와 그에 따른 경제, 상업, 무역, 외교가 발달했던 풍요로운 나라였다. 주식회사의 초기 모습은 송나라때 나왔다고 하며, 3대 발명품인 나침반, 화약, 인쇄술도 송의 유산이다. 이러한 송나라는 예전 당나라가 지방의 절도사에게 큰 코를 다쳤던 전례를 피드백하여 문치주의를 강..

문제소설가인 김대전은 소설을 여러 장(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)에 개입해 전리품을 얻고 전연을 지원한다. 이 당시 부견에게는 왕..