교대최소제곱법

2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 이 문제를 읽자마자 '어 그거다'라는 생각은 들었지만 기억력 이슈로 인해 푸는데 한참 걸렸다... 좌표로 다각형의 면적을 구한다? 처음에는 헤론의 공식을 생각했지만 그건 좌표가 아니라 선분의 길이를 활용한다는 것을 떠올렸고 대신 고등학교 시절 머리 속에 저장해둔 한 공식을 꺼내왔다 React, Spring 하는데 왜 수학을 잘해야 해요? 음 사실 이 포스팅을 쓰는 이유는 이 문제가 엄청 의미있거나 어려운 문제여서는 아니다 그냥 이 문제를 풀면서 개발자에게 수학이란 무엇일까? 라는 생각이 ..

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 이전에 외판원 순회2는 손쉽게 풀었던 경험이 있는데 외판원 순회2의 경우 시간 제한도 2초이고 메모리제한도 256MB라 아주 널널했던 것으로 기억한다. def dfs(depth, start, total): global MIN if depth == N-1 and graph[start][0] != 0: total += graph[start][0] MIN = min(MIN, total) return for i in range(N)..

일단 문제를 보자마자 이진탐색임을 직감은 했지만 이진탐색을 사용하는 방법이 좀 아쉬웠다. 아이디어가 좋은 문제인 것이 가장 인접한 두 공유기 사이의 최대 거리를 구하기 위해서는 최대한 일정한 크기로 잘라야 한다는 점이다 그렇기 때문에 어느정도의 사이즈로 잘라야 일정하게 짤리는가를 찾는 문제로 치환될 수 있다. 따라서 이진탐색을 공유기를 찾는데 활용하는 것이 아니라 잘려지는 길이를 이진탐색으로 찾는 문제였다 구현에서 핵심은 잘려지는 길이를 찾는 것이기 때문에 start와 end를 인덱스로 잡는 것이 아니라 길이로 잡아야 한다 즉, 최소 1 최대는 시작부터 끝까지의 길이로 설정해서 그 사이의 값을 찾도록 구현해야한다 def install_router(seq): start = 1 end = seq[-1] - ..

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문자열 전체를 DP에 저장해서 사용하는 아이디어가 참신했다 공간 복잡도 O(n)로 짠 코드 def lcs(seq, tar): dp = [''] * len(tar) # 배열의 크기는 두 번째로 도는 iter의 크기로 해야한다 ->5번라인으로 for i in range(len(seq)): max_dp = '' for j in range(len(tar)): # 배열의 크기만큼 돈다 if len(max_dp) < len(..

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 다시 한 번 겸손을 배울 수 있었던 문제 핵심은 1. 어떻게 분할정복 문제로 볼 것인가 2. 어떻게 메모이제이션을 활용할 것인가 3. 어떻게 구현할 것인가 무려 3개의 난관을 넘어야 풀 수 있는 문제였다. 1. 어떻게 분할정복 문제로 볼 것인가? ABCDE 행렬이 있을 때 A + BCDE, AB + CDE, ABC + DE, ABCD + E 로 분할하여 최소를 찾을 수 있다가 첫 번째..

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 이번 문제도 위상정렬을 활용하면 최장경로를 구하는 것에는 어려움이 없다. 이번 문제 핵심은 중복되지 않게 도로의 개수를 구해라 중복을 제거하기 위해서 역추적을 통해서 set에 간선을 저장한다 역추적을 하기 위해 노드를 이동할 때 이전 노드를 기억시킬 배열이 필요하고 이는 노드의 최대값이 갱신되거나 같을 때 이전 노드를 기억시킨다. 위상정렬 두 문제를 풀어 보았는데 위상정..

https://www.acmicpc.net/problem/1432 1432번: 그래프 수정 첫째 줄에 정점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 인접행렬 형식으로 입력이 주어진다. 0은 연결되지 않았음을 의미하고, 1은 연결되었다는 것을 의미한다. N은 50보다 작거나 같은 www.acmicpc.net 이번 문제의 핵심은 답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력한다. 사실 중복되는 답을 찾는 것은 위상정렬만 알면 어렵지 않다. 하지만 사전 순이 매우 큰 난관이었다. 핵심적인 아이디어는 1. 반대로 위에서 내려오는 방식으로 생각할 것 2. 최대 힙을 활용해 큰 인덱스부터 찾을 것 1번까지는 스스로 생각했는데 2번을 생각하지 못해 해결하지 못했다. "거꾸로 생각해도 작은 것부..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net BFS로 빠르게 풀었지만 메모리 초과... 기존의 BFS 문제의 경우 상하좌우 최대 4가지 분기로만 나눠졌기 때문에 메모리 초과 문제가 안났지만 이번 문제는 연결된 노드의 개수만큼 큐에 저장되기 때문에 케이스에 따라 메모리 초과가 날 수 있다는 것을 고려해야했다. BFS문제에서 메모리 초과가 날 경우 -> DP를 첨가해서 풀면 맛이 좋다 from collection..