1. 문제 https://www.acmicpc.net/problem/23570 23570번: Grid Triangle Your program is to read from standard input. The input is exactly one line containing three integers, $A$, $B$, $C$ ($1 ≤ A, B, C ≤ 10,000,000$). www.acmicpc.net 2. 한 집합에서의 모든 경우의 수 - 삼각형의 세 좌표가 다음과 같을 때 - (0, 0, 0) , (x, y, z), (xx, yy, zz) - 차이들은 다음과 같다. p1 : x, y, z p2 : xx, yy, zz d : x - xx, y - yy, z - zz 문제에서 주어진 조건 - 숫자들의 ..

1. 문제 https://www.acmicpc.net/problem/5419 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net 2. 풀이 - Y 는 감소해야하고 X 는 증가해야한다. - 이 때 생각할 수 있는 가장 간단한 방법은 - 한 축을 기준으로 정렬을 하고 한개씩 앞에서부터 다른 한축과 비교를 통해 가능한 쌍의 개수를 새나가는것이다. - 이경우 O(N^2) 의 시간복잡도로 75000 * 75000 = 5,625,000,000 - 최악의 경우 TLE 가 뜰것이다. 그러므로 O(NlogN) 로 문제를 해결해야한다. - 일단 x축을 기준으로 오름차순으로 정렬, y축은 내림차순으로 정렬해보자. - 그러면 대충 위와 같은 그..

1. 문제 https://www.acmicpc.net/problem/20036 -> - 중력에 의하여 공하나를 제거할 시 공들은 중간으로 모이게 된다. - 그리고 뺀 공은 맨 왼쪽이나 맨 오른쪽에만 넣을 수 있다. - 이때 공을 빼는 최소 횟수를 구해야한다. 2. 풀이 - 먼저 같은 공을 두번이상 손을 대지 않는다는것을 눈치채야한다. (첫번째 공을 뺀 행동의 의미가 없어짐, 그러므로 1번 공을 빼는것이 최소가 된다.) - 한 공마다 최대 1번만 공을 건들 수 있으므로 - 적절히 공을 제거해줘야하는데, - 중간에 삽입 불가능하므로 - 나머지 공들을 "정렬된 부분"으로 만드는 방향으로 제거해줘야한다. - 그러므로 이 문제는 주어진 배열에서 가장 긴 정렬된 부분 수열을 구하는 문제로 변형할 수 있다. 가장 간..

1. 문제 https://www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net 2. 풀이 늦는 시간 T 동안 주어진 그래프에서 이동할 수 있는 길의 경우의 수 구하는 문제. 가중치가 1인 인접 행렬 그래프를 n번 제곱하면 (가중치가 없는) mat[i][j]의 값은 i 에서 j 로가는 경로중 n개의 간선이 있는 경로의 경우의 수 와같다. 따라서 주어진 그래프를 가중치가 1 인 인접행렬 그래프로 변환하고 T 제곱 하면 간선의 개수가 T인 ..

1. 문제 4206번: 피보나치 단어 (acmicpc.net) 2. 간단 풀이 이 문제는 입력의 크기를 제외하면 단순하다. fib[i] = fib[i-1] + fib[i-2] + mid 이 공식을 사용하여 중간에 걸친부분을 조사하여 새로운 패턴이 생기는지 확인만하면된다. 하지만 long long 타입의 크기의 문자열을 처리해야한다는것. 이를 그대로 처리하게되면 당연히 시간 초과 메모리 초과가 일어날것은 뻔하다. 그러므로 피보나치의 성질을 활용하여 다루는 문자열의 크기를 제한하고, kmp알고리즘을 사용하여 효율적으로 처리해야한다. 3. 풀이 피보나치 문자열이 일단 패턴보다 길어야 패턴이 보인다는것은 자명하다. 길이가 같거나 더 긴 첫번째 피보나치 문자열을 first 라고하고 다음 문자열을 second라하자..

1. 문제 11400번: 단절선 (acmicpc.net) 2. 풀이 [백준] [C++] 11266번 단절점 (dfs) (tistory.com) 단절점 문제와 유사하다. dfs 스패닝 트리에서 부모 노드 - 자손 노드 의 간선을 조사할때 자손이 루트인 서브트리에서 부모로 가는 간선을 제외한 역방향 간선을 조사. 만약 서브트리에서 역방향간선이 전부 부모노드를 거슬러 올라가지 못할 경우. 부모노드 -> 자손 노드 의 간선이 단절선이되어 이 선을 제거하면 컴포넌트가 분리된다. 부모 노드로 가는 간선을 제외해야하는 이유 = 자손 노드의 자손들이 이 부모노드와 연결될경우, 현재 부모 - 자손 노드의 간선은 단절선이 될 수 없음. = 만약 부모노드로 가는 간선을 무시안할 경우 최소는 항상 부모노드와 같거나 작은값을 ..