본문 바로가기

전체 글74

[백준] 1806번 부분합 해당 문제의 원문은 여기서 확인하자. 문제 이해 길이가 N인 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되며 가장 짧은 것의 길이를 구하는 문제이다. 첫째 줄에 N, S가 주어지고 둘째 줄에 공백으로 각 원소를 구분하는 수열이 주어진다. 제한 사항은 다음과 같다. 10 ≤ N < 100,000 1 ≤ S ≤ 100,000,000 1 ≤ 수열의 각 원소 ≤ 10,000 S 이상이 불가능한 경우 0 출력 접근 방식 투 포인터의 개념을 이용해 문제를 해결하였다. 해당 문제에선 합에 추가할 인덱스의 위치를 head, 합에서 제거할 인덱스의 위치를 tail이라 정의하였다. 길이에 대한 탐색 과정을 예시와 함께 알아보자. 배열의 첫번째 인덱스는 시작 지점으로 사용하기 위해 추가한 인덱스로 실제 입력받은 .. 2022. 7. 18.
[백준] 2143번 두 배열의 합 해당 문제의 원문은 여기서 확인하자. 문제 이해 한 배열 A[1], A[2], ..., A[n]에 대해서, 부 배열은 A[i], A[i+1], ...,A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i] + ... + A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 문제이다. 예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다. T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = .. 2022. 7. 17.
[백준] 2110번 공유기 설치 해당 문제의 원문은 여기서 확인하자. 문제 이해 직선 상에 중복되지 않은 좌표를 가진 여러 개의 집이 존재하며, 각 집에는 1개의 공유기만 설치가 가능하다. C개의 공유기를 설치할 때 , 가장 인접한 두 공유기 사이의 거리의 최댓값을 구하는 문제이다. 첫째 줄에는 집의 개수 N, 공유기의 개수 C가 주어지며, 둘째 줄부터는 N개의 줄에 집의 좌표 xi가 한 줄에 하나씩 주어진다. 제한 사항은 다음과 같다. 2 ≤ N ≤ 200,000 2 ≤ C ≤ N 0 ≤ xi ≤ 1,000,000,000 접근 방식 이분 탐색의 개념을 이용해 문제를 해결하였다. 이분 탐색 문제의 경우 대체로 구하고자 하는 대상이 이분 탐색을 수행할 기준이 된다. 이 문제에선 두 공유기 사이의 거리의 최댓값이 구하고자 하는 것이기 때문.. 2022. 7. 15.
[백준] 1021번 유기농 배추 해당 문제의 원문은 여기서 확인하자. 문제 이해 배추를 해충으로부터 보호하는 지렁이가 있으며, 이 지렁이는 인접(상하좌우 4방향)한 배추들로 이동하며 인접한 모든 배추들을 보호할 수 있다. 배추밭에 0을 배추가 심어져 있지 않은 땅, 1을 배추가 심어져 있는 땅이라고 했을 때, 필요한 최소 지렁이의 수를 구하는 문제이다. 첫째 줄에는 테스트 케이스의 개수 T, 둘때 줄에는 배추밭의 가로 길이 M, 배추밭의 세로길이 N, 배추의 위치 개수 K가 순서대로 입력된다. 그 다음 줄부터는 K줄의 배추의 위치 좌표가 입력된다. 제한 사항은 다음과 같다. 1 ≤ M, N ≤ 50 1 ≤ K ≤ 2500 0 ≤ X ≤ M - 1 0 ≤ Y ≤ N - 1 두 배추의 위치가 같은 경우는 없다. 정답은 테스트 케이스의 수만.. 2022. 7. 13.
[백준] 2606번 바이러스 해당 문제의 원문은 여기서 확인하자. 문제 이해 네트워크 망을 통해 연결된 모든 컴퓨터를 감염시키는 바이러스가 있을 때 감염된 컴퓨터의 수를 구하는 문제이다. 위와 같이 연결되어 있을 때 1번이 감염되면 2, 3, 5, 6번이 모두 감염되지만 4, 7번의 경우는 네트워크 망이 달라 영향을 받지 않는다. 첫째 줄에는 컴퓨터의 수, 둘째 줄에는 연결된 컴퓨터 쌍의 수, 이어서 그 수만큼 한 줄에 한 쌍씩 컴퓨터의 번호 쌍이 입력된다. 제한 사항은 다음과 같다. 1 ≤ 컴퓨터의 수 ≤ 100 감염되는 컴퓨터는 항상 1번이다. 컴퓨터의 번호는 1번부터 컴퓨터의 수까지이다. 접근 방식 BFS 개념을 이용해 1번과 연결된 컴퓨터를 감염 시킨 후, 감염된 컴퓨터를 기준으로 다시 연결된 컴퓨터를 탐색하였다. '문제 이.. 2022. 7. 12.
[백준] 2293번 동전 1 해당 문제의 원문은 여기서 확인하자. 문제 이해 가치가 다른 n가지 종류의 동전을 이용해 가치의 합이 k원이 되는 경우의 수를 구하는 문제이다. 이때 동전의 순서는 고려하지 않는다. 첫째 줄에 n, k가 순서대로 입력되며 다음 n개의 줄에는 각 동전의 가치가 입력된다. 제한 사항은 다음과 같다. 1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000 1 ≤ 동전의 가치 ≤ 100,000 결과 < 2^31 접근 방식  DP의 개념을 이용해 해결할 수 있는 문제이다. k + 1 값을 배열의 최대 크기로 정하고 배열의 인덱스를 만들어진 가치의 합, 인덱스의 값을 만들어진 횟수로 정의한다. 다음 예시를 보자. 최상단의 숫자는 인덱스이자 만들어질 수 있는 가치의 합들을 의미한다. 좌측의 'cost 1'은 동전의 가치.. 2022. 7. 12.

티스토리툴바