문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.코드def get_prefix_sum(N, numbers): prefix_sum = [0] * (N + 1) for i in range(1, N + 1): prefix_sum[i] = prefix_sum[i-1] + numbers[i-1] return prefix_sumd..
Koala - 17기/코딩테스트 심화 스터디
https://www.acmicpc.net/problem/1072알고리즘이진탐색을 이용하는 문제이다. Z(승률)이 변하는 최소한의 게임 판수를 구하는데, 이때 승률이 변하지 않는 경우를 확인해주어야 한다.Z 계산시 버림한다고 하였으므로, 99퍼 이상은 아무리 계속 승리를 해도 변하지 않으므로 Threshold를 Z = 99로 잡고 코드를 구성하였다.게임 판수를 이진탐색의 right, 0판을 left로 잡고 이분탐색을 하면서 승률의 변동이 있는지 확인해준다. 승률이 변했다면 판수를 더 줄여서 확인해 보아야하므로 r = mid-1을 통해 다시 이진탐색을 해주고, 승률이 변하지 않았다면 판수를 더 늘려서 확인해 보아야하므로 l = mid+1을 통해 이진탐색을 계속한다.코드import sysinput = sys..
https://www.acmicpc.net/problem/17951입력첫 번째 줄에 시험지의 개수 N과 시험지를 나눌 그룹의 수 K가 정수로 주어진다. (1 ≤ K ≤ N ≤ 105)두 번째 줄에 각 시험지마다 맞은 문제의 개수 x가 정수로 주어진다 (0 ≤ x ≤ 20)출력현수가 받을 수 있는 최대 점수를 출력한다. 코드n, k = map(int, input().split())li = list(map(int, input().split()))left = min(li)right = sum(li)cnt = 0while left = mid: cnt += 1 result = 0 if cnt >= k: left = mid + 1 else: ..
문제 https://www.acmicpc.net/problem/1939 Algorithm도시와 도시 사이에 연결된 다리로 옮길 수 있는 최대 중량값은 DFS로 구하면 될 것 같다.- 이진탐색을 통해 중량이 A에서 B로 이동할 수 있는지 탐색- 가능하면 중량을 더하고 다시 탐색- 가능하면 중량을 줄이고 다시 탐색- 탐색이 종료되면 최대 중량을 출력 Codeimport java.io.*;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Main { static int ans; static List[] list; static boolean[] check; public static void..
2352번: 반도체 설계접근 방법연결선이 꼬이면 안되기 때문에, 가장 긴 증가하는 부분 순열 (LIS) 알고리즘을 사용하기로 결정이때 dp로 접근하게 되면 시간 복잡도가 O(n^2)이기에 시간 초과가 발생했다.여기에서는 시간 복잡도를 O(n log n)으로 줄이기 위해서 이분탐색을 이용하기로 결정한다.vector v(n) -> 연결되어야 하는 포트 번호들을 입력받는 배열vector dp -> 증가하는 부분 수열에 들어갈 수를 최적의 값으로 유지하기 위한 배열int pos -> 반복문을 거치는 현재 원소(v[i])가 dp에 들어갈 위치를 결정하는 역할을 한다.같은 숫자는 존재하지 않기에 binary_search 함수를 구현, dp에 들어갈 위치를 이분 탐색으로 결정, 반환하는 값(ans)이 dp의 사이즈와..
https://www.acmicpc.net/problem/11658알고리즘 유형자료 구조세그먼트 트리누적 합다차원 세그먼트 트리문제N×N개의 수가 N×N 크기의 표에 채워져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 표의 i행 j열은 (i, j)로 나타낸다. (x1, y1)부터 (x2, y2)까지 합이란 x1 ≤ x ≤ x2, y1 ≤ y ≤ y2를 만족하는 모든 (x, y)에 있는 수의 합이다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자. 1234234534564567여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이 된다. (2, 3)을 7로 바꾸고 (2, 2)부터 (3, 4)까지 합을 ..
문제 https://www.acmicpc.net/problem/21608 Algorithm일반적인 구현 문제, 다만 요구 사항이 조금 까다로울 수 있다.요구에 맞춰 자리를 배치 후, 만족도 총합을 구하여 하므로 크게 2파트로 나누어 생각해서 구현하였다. Codefrom collections import dequeinput = __import__('sys').stdin.readlineN = int(input().rstrip())N_list = [list(map(int, input().rstrip().split())) for i in range(N ** 2)]N_map = [[0] * N for i in range(N)]cntN_map = [[0] * N for i in range(N)]def find..
https://www.acmicpc.net/problem/30648알고리즘한 좌표에 두송이의 꽃이 피어있게 되는 시간을 구하는 문제이다.우리가 기억해야 할것은 다음 꽃이 필 자리에 꽃이 존재하는가현재 꽃이 핀 위치와 다음에 꽃이 필 위치를 기억해주고, 반복문을 통해 시간을 구해주는 방식으로 코드를 구성하였다.해당 좌표에 꽃이 있는지 확인할 배열, 다음 꽃이 필 위치 좌표 변수를 통해 해당 위치에 꽃이 존재했다면 반복문을 종료하고 시간을 출력해주었다.해당 위치에 꽃이 존재하지 않았다면 다음 꽃이 필 좌표를 계산해주는데, x+y+2가 r보다 작으면 다음 꽃이 필 위치는 x+1, y+1이고x+y+2가 r보다 크면 다음 꽃이 필 위치는 x%2, y%2이고, 소수점은 버리므로 //로 정수형을 만들어준다.코드imp..
https://www.acmicpc.net/problem/2003문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.출력첫째 줄에 경우의 수를 출력한다.코드def count_subarrays_with_sum(N, M, A): start, end = 0, 0 current_sum = 0..
https://www.acmicpc.net/problem/2842알고리즘 분류그래프 이론그래프 탐색이분 탐색너비 우선 탐색두 포인터문제상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌..
https://www.acmicpc.net/problem/14465입력첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.출력정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다. 코드n, k, b = map(int, input().split())arr = [0 for _ in range(n)]for _ in range(b): arr[int(input())-1] = 1 left = 0right = k-1tmp = sum(arr[0:k])ans = tmpwhile right 풀이 과정1. 고쳐야하는 고장난 신호등을 1로 표시2. K 간격만큼에서 고쳐야하는 신호등 수를 그 1들의 합으..
접근 방법a 배열을 통해 초밥의 가짓수 d(2 ~ 3000)가 k개의 접시를 연속해서 먹을 때 있는지 확인먼저 반복문을 돌려서 0 ~ k-1 접시를 연속으로 먹었을 때 최댓값을 계산(윈도우로 활용)해당 윈도우를 접시를 지우고, 추가하며 연속된 접시를 k 개 먹었을 때, 최댓값을 계산(슬라이딩 윈도우) 코드#include #include using namespace std;int a[3001] = {0, };int main() { int N, d, k, c; cin >> N >> d >> k >> c; vector v(N); for (int i = 0; i > v[i]; int sol = 0, result = 0; for (int i = 0; i
