그냥 하는 노트와 메모장

i번째 엘리베이터를 수식으로 나타낸다면 첫 위치를 그리고 몇칸씩 이동할 수 있는지를 로 표현한다면 i번째 엘리베이터가 갈 수 있는 곳은 아래를 만족하는 모든 층에 갈 수 있다. 하지만 최고층이 N이기 때문에 y는 최대 N까지 밖에 갈 수 없다. 따라서 엘리베이터에 따라 k의 최대값이 달라진다. 모든 엘리베이터를 수식으로 두고, 서로 다른 두 엘리베이터에 대해 i에서 j로 갈 수 있는지를 판단한다. 만약 i 엘베에서 j 엘베로 갈 수 있다면 간선을 연결해준다. 이 때 간선을 연결해줄 알고리즘이 매우 까다롭다. 두 수식에 대해서 만족하는 해와 최대층 N에 대해서 처리를 해줘야하기 때문이다. 우선 두 수식을 아래처럼 나타낸다. 이제 꼴로 나타냈으니 수식의 해가 정수해이기 위해선(정수해인 이유는 엘베에 대해 한..

A에서 B로 갈 수 있는 모든 경로의 차의 수 최대값은 최대 유량으로 충분히 가능하다. 하지만 또 하나가 있는게 이 중에서도 한 경로만 사용했을 때, 최대값을 구해서 앞서 구한 모든 경로의 차의 최대값과 한 경로의 차의 수 최대값의 비율을 계산하라고 한다. 단순 최대유량 문제만 내기엔 부족했나보다. 편의상 A에서 B로 가는 모든 경로의 차의 수 최대값을 X라고 하고, 한 경로의 차의 수 최대값을 Y라고하면 구하고자 하는 값은 Y/X가 된다. X는 단순 최대 유량으로 구해서 계산하며 Y는 backtracking으로 정의하여 계산한다. Y를 구할 때, 기저 사례는 B를 만날 때까지고, 재귀를 돌며 방문했던 정점은 다시 방문하지 않도록 한다. 재귀의 반환값은 현재 정점에서 방문 가능한 정점 중에서 차를 최대한..

완전 그래프에 관한 문제다. 크기가 K인 그래프 내의 clique(클릭) 중에서 구성된 정점의 번호가 제일 작은 것을 찾으려고 한다. 입력 데이터의 규모가 작으니 하나하나 접근해나가며 완전 그래프를 만들 수 있는지 없는지 판단하는 백트래킹 재귀 함수를 만들었다. 재귀 호출하기 전에, for문으로 번호가 작은 친구부터 탐색하도록 한다. 마찬가지로 재귀 내에서도 번호가 작은 친구를 찾도록 유도하여 구성된 정점의 번호가 작은 클릭을 찾을 수 있다. 재귀 함수의 기저 사례는 현재 구성된 완전 그래프의 크기 p와 찾아야 하는 완전 그래프의 크기 k와 같으면 true를 반환..

다소 까다로운 문제다. 문제 내용을 읽으면 우선 트리를 떠올리게 되는데, 문제에 맞는 트리의 속성을 적자면 아래와 같다. 1. 이진 트리다. 2. 자식이 하나만 있는 노드는 없으며, 자식이 있다면 무조건 2개의 자식을 갖는다. 하지만, 트리는 아니다. 이는 훼이크고, 그냥 단순 그래프이나, 노드에 순서성에 대해 트리형태처럼 보일 뿐이다. 정확히는 DAG(Directed acyclic graph)를 나타낸다. 따라서 나는 세 단계를 거쳐 AC를 받게 됐다. 1. MLE 2. TLE 3. AC (만약 단순 솔루션만 보고 싶다면 기본 아이디어 이후, 3.으로 바로 넘어가길 바란다.) * 기본 아이디어 그래프를 배열로 구현하고, 문자열에 대한 것은 string, map을 사용하여 배열에 대한 위치값(또는 포인터..