[Algorithm]

시간 복잡도 줄이는 기술 5. +1-1 technique

+1-1 Technique N개의 선분을 2개의 시작, 끝 정점으로 나눠 각각 +1, -1 가중치를 줘서 x가 증가하는 순서대로 정렬하는 방법을 +1 -1 Technique 예시 - 수직선 상 겹치는 구간 문제 - 가장 많이 겹치는 구간 일직선 위에 n개의 구간이 주어졌을 때, 구간이 가장 많이 겹치는 부분에서 몇 개의 구간이 겹치는지를 구하는 프로그램을 작성하세요. 아이디어 먼저, 배열을 생성해서 선분이 있는 구간마다 1을 더해 최댓값을 구하는 식은 시간초과가 났다. → 선분의 구간을 for로 돌며 1을 더하는 것이 문제 선분의 시작점과 끝점에 +1,-1을 한다. 모든 점마다 겹치는 선분을 세줌 코드 n=int(input()) arr= [tuple(map(int,input().split())) for ..

시간 복잡도 줄이는 기술 4. LR 배열

마라톤 중간에 택시타기 마라톤 코스는 N개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 마라톤이 끝납니다. 게으른 개발자 A는 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 한 개를 몰래 건너뛰려 합니다. 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 티가 많이 나기 때문에 이 두 체크포인트는 건너뛰지 않으려고 합니다. 개발자 A가 체크포인트 한 개를 건너 뛰어서 마라톤을 완주하려고 할 때, 최소 거리를 구하는 프로그램을 작성해보세요. 단, 거리 계산은 ∣x1−x2∣+∣y1−y2∣ 로 계산하는 것을 의미합니다. 또한, 체크 포인트의 좌표는 겹쳐져 주어질 수도 있으며, 이 경우 개발자 A가 체크포인트를 건너뛸 때 ..

시간복잡도를 줄이는 기술 3. 전처리 - 숫자들의 합이 7의 배수

문제 N개의 서로 다른 숫자가 차례대로 주어집니다. 이들 중 연속하게 고른 숫자들의 합이 7의 배수가 되게 그룹으로 묶으려 합니다. 이렇게 만든 그룹 중 최대 크기를 구하는 프로그램을 작성해보세요. 아이디어 기록하는 새로운 배열을 만들어 해결하는 것이 포인트 합 배열을 구한다.(Prefix_sum) 맨 뒤 (모든 수의 합)에서 부터(for i range(N,0,-1) - 맨 앞의 수( for j in range(0,i)를 을 빼가며 7의 배수인지 체크한다. 만약 7의 배수가 있다면, for j 를 탈출한다. (앞에서 부터 돌기 때문에, 가장 큰 그룹이다. 뒤에는 돌 필요 X) 코드 N=int(input()) arr= [0] # 합 배열을 구한다. # 맨 뒤에서 부터 for _ in range(N): ar..

시간 복잡도를 줄이는 기술 3. 전처리 - 최소 비용 배열 활용하여 최소 에너지 비용 구하기

이런 유형의 문제 자주 나왔어서 기억해둘 것. 문제 n개의 서로 다른 장소가 일직선상에 주어집니다. 각 장소마다 에너지 1을 채우는데 필요한 비용이 다르며, 장소와 장소를 이동할 때는 에너지를 소모합니다. 각 장소마다 에너지 1을 채우는데 필요한 비용 과 장소와 장소를 이동할 때 소모하는 에너지가 주어질때, 제일 왼쪽 장소에서 제일 오른쪽 장소까지 이동할 때 드는 최소 비용을 계산하는 프로그램을 작성해보세요. 첫 번재 줄에는 장소의 개수를 나타내는 n이 주어집니다. 두 번째 줄에는 장소와 장소를 이동할 때 드는 에너지를 가장 왼쪽부터 차례대로 공백을 두고 주어집니다. 세 번째 줄에는 각 장소마다 에너지 1을 채우는데 드는 비용이 제일 왼쪽 장소부터 차례대로 주어집니다. 아이디어 가장 비용이 적게 드는 충..