파이썬 (3) 썸네일형 리스트형 PS. 슬라이딩 윈도우 그리고 투포인터 오늘은 투 포인터 관련 문제를 풀다가, 이전부터 정리하고 싶었던 두 가지 기법을 정리하려고 한다. 간단히 개념만 정리하고 끝내겠다. 먼저 슬라이딩 윈도우란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다. 네트워크에서 사용되던 알고리즘을 문제 풀이에 응용한 경우라고 한다. 투 포인터랑 다른 점은 고정 사이즈의 윈도우를 사용해서 순회를 하는 방식이다. 그리고 투포인터는 보통 정렬 배열을 대상으로 하는데 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다는 차이가 있다. 그리고 투포인터는 꼭 뭐 앞에서 순차적으로 찾을 필요 없이 양쪽에서 다가와도 되고 문제마다 다르다. 물론 슬라이딩 윈도우도 다르긴 하다. 근데 일단 슬라이딩 윈도우는 사이즈를 고정한 점이 가장 큰.. 백준 11049 행렬의 곱셈 순서 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net DP로 접근해서 해결한 문제입니다. 점화식이 쉽게 생각나지 않아서 도움을 많이 받았습니다. 이 문제는 주어진 행렬의 곱셈 순서에 따라 연산 횟수가 달라지는데 그중 최소 연산 횟수를 찾는 문제입니다. 과정은 다음과 같습니다. 값을 저장할 dp 리스트를 이차원으로 만듭니다 dp [i][j] = i행렬부터 j행렬까지의 최소 연산 행렬 간의 곱을 여러 경우로 만들어 낼 수 있어서 시작 .. 백준 13334 철로(python) 문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 우선순위 큐를 활용하여 스위핑 방식으로 접근하였습니다. 집과 사무실 위치를 위치에 맞게 리스트에 저장해 준 다음 오른쪽을 기준으로 오름차순 정렬해주었습니다. 그 뒤 리스트에 주어진 값들을 차례로 순회하면서 주어진 철로 길이 안에 해당되면 큐에 넣어 주었습니다. 큐 최소 힙을 만들며 왼쪽 좌표만을 넣어 주었습니다. 큐에 있는 값들과 순회하면서.. 이전 1 다음