14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 조합(Combination)을 만드는 문제입니다. 2. 접근 방법 조합을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(start: int, depth: int): if depth == M: print(*arr) return for i in range(start, ..
15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다. 2. 접근 방법 순열을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 3 - 1. 재귀함수 이용 from sys import stdin input = stdin.readline n, m = map(int, input().split()) def solution(num: int, arr: list): if num == m: print(..
17611번: 직각다각형 입력의 첫 줄에는 단순직각다각형의 꼭지점의 개수를 나타내는 정수 n(4 ≤ n ≤ 100,000)이 주어지고, 이어지는 n개 줄 각각에 단순직각다각형 꼭지점의 좌표 (xi, yi)가 차례대로 주어진다. 주어지 www.acmicpc.net 1. 문제 요약 다각형의 좌표가 주어지고 수직선과, 수평선에 대하여 해당 다각형의 수직선분과, 수평선분이 가장 많이 교차하는 횟수를 구하라. 2. 접근 방법 백준 - 3020 개똥벌레 [누적합][이모스] 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종 e-room.tistory.com 해당 문제..
3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 1. 문제 요약 장애물의 위치가 주어지고, 해당 장애물을 통과하는 최솟값과 그러한 구간의 수를 출력하라 2. 접근 방법 위와 같은 장애물이 있다고 했을 때, 아래서부터 장애물을 통과하는 수를 세어보면 3, 3, 2, 3 입니다. 이런 식으로 완전탐색으로도 충분히 정답은 구할 수 있습니다만, 시간과 메모리가 한정되어 있기 때문에 다른 방법으로 풀어야 합니다. 이모스법 알고리즘을 알고 있다면 쉽게 풀 수 있습니다. 위 그림과 같이 장애물이 시작되는 위치에 +1, 끝나는..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 N x N의 표가 주어지고 좌표가 주어지면, 그 구간의 합계를 구하는 문제이다. 2. 접근 방법 다이내믹 프로그래밍을 이용하여 각각의 구간별 합을 미리 구해놓는다. (DP 테이블) 예를 들어, DP 테이블의 (2,2)의 위치는 기존테이블의 (2,2) + DP(2,1) + DP(1,2) - DP(1,1)이다 즉, 원하는 위치의 수 + DP테이블의 위 + 좌 - 겹치는 구간이다 DP테이블은 (N+1) x (N+1)로 생성하면 편리하다..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 블록들의 높이가 주어지고 블록들 사이에 고일 수 있는 빗물의 양을 구하는 문제입니다. 2. 파이썬 2 - 1. 접근 방법 백준 - 2304 창고 다각형 [구현] 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내 e-room.tistory.com 이전에 풀었던 문제와 거의..
2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 1. 문제 요약 주어진 좌표와 높이에 맞는 다각형의 넓이를 구하라(단, 오목하게 들어가는 부분은 없어야 한다.) 2. 파이썬 조금 비효율적인 방식으로 처음에 풀었습니다 ...ㅎ 2 - 1. 접근 방법 주어진 좌표와 높이에서 가장 큰 부분에 맞는 이중배열을 생성 현재 높이와 이전의 높이 중 가장 높은 높이로 이중배열을 채워준다 동일한 방식으로 좌표 역순으로 진행 생성된 두 이중배열을 비교하여 둘 다 채워진 경우 넓이를 증가 시킨다 2 - 2. 코드..
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 간단 요약 해당 문제는 수열이 주어지면, 해당 수열의 부분연속수열의 합중 가장 큰 값을 구하는 문제이다. 2. 접근 방법 순차적으로 값을 더한다. 다음에 올 숫자가 이득인지 손해인지를 판단한다. 현재까지의 값 + 수열의 현재 인덱스의 값 vs 수열의 현재 인덱스의 값을 비교하여 더 큰 값을 취한다. 예를 들어 아래와 같은 수가 주어질 경우 -4는 음수이지만 10과 합하면 6이다. 해당 값과 3을 더하면 9이므로, 3보다 크기때문에 손해가 아니므로 취한다. 아래처럼 2..
1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 해당 문제는 주어진 숫자가 소수인지 판별하는 문제입니다. 낮은 난이도이기에 어떠한 방식으로 풀어도 통과가 됩니다. 대표적인 3가지 방법으로 풀어보겠습니다. 1. 일반적인 방법 가장 일반적인 방법으론 2부터 1씩 늘려가며 해당 숫자가 나누어 떨어지는지 보는 방법입니다. // Java static boolean isPrime(int number) { if (number
