문제 링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 설명 한나는 자신의 땅에 배추를 군데군데 심어놓은 상태다. 아래는 현재 한나의 땅 상태고, 1은 배추가 심어져 있는, 0은 배추가 심어져 있지 않은 땅을 나타낸다. 배추를 해충으로부터 보호하기 위해 배추흰지렁이를 놓을 계획이고 배추흰지렁이는 인접한 땅을 옮겨가며 배추를 보호할 수 있다. 최소의 배추흰지렁이 마리 수를 구하자. 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0..
문제링크 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 풀이 한 변의 길이가 2가 아니라면 한 변의 길이를 N/2로 만들어 다시 함수를 호출하는 식으로 분할정복을 이용하여 풀이할 수 있다. 나는 4개의 숫자중 두 번째로 큰 수를 고르기 위해 임시로 vector를 만들어서 넣어주고 algorithm 헤더의 sort함수를 사용하여 정렬해준 뒤 인덱스로 직접 접근하였다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..
문제링크 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 위처럼 입력이 주어졌을 때 아래처럼 변의 길이를 N/2씩 나누어 가며 흰색으로 만들어진 정사각형과 파란색으로 만들어진 정사각형의 개수를 출력해야한다. 문제를 보면 잘 알겠지만 대놓고 분할정복의 방법을 사용하라고 그림까지 주어져있다. 분할정복의 자세한 내용은 알고리즘 카테고리에서 다루도록하고 간단하게 설명하면 하나의 문제를 같지만 더 작은 문제로 나눈다음 작은 문제를 해결하고 결과를 합쳐서 하나의 결과가 나오도록하게 하는 전략이..
문제링크 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2xN 크기의 직사각형을 채우는 방법은 아래와 같이 나눌 수 있다. 2x(N-1)만큼 채우고 2x1 타일을 붙인다. 2x(N-2)만큼 채우고1x2 타일을 두 개 붙인다. 2x(N-2)만큼 채우고 2x2 타일을 한 개 붙인다. 위의 내용을 점화식으로 만들면 dp[n-1] + dp[n-2]*2가 된다. 코드 1 2 3 4 5 6 7 8 ..
문제링크 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 다이나믹 프로그래밍을 사용하기 위해서는 현재 항을 어떻게 이용하여 다음 항을 찾을지에 대한 점화식을 찾는 것이 가장 중요하다. 나의 경우는 직접 그림을 그려보며 점화식을 찾아보았다. n=1 일 경우 → 1가지 n=2 일 경우 → 2가지 n=3 일 경우 → 3가지 n=4 일 경우 → 5가지 n=5 일 경우 → 8가지 인 것..
문제링크 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을..
문제링크 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋..
문제링크 3061번: 사다리 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 두 줄로 구성되어 있다. 첫 번째 줄에는 사다리 세로줄의 www.acmicpc.net 문제 상덕이는 매일 점심시간마다 무엇을 먹어야 할 지 매우 고민에 빠진다. 결국 상덕이는 사다리게임을 하기로 했다. 밥을 같이 먹는 희원이는 상덕이를 놀리고 싶은 마음에, 희원이가 원하는 대로 사다리를 그리고 싶어한다. 희원이는 상덕이를 잘 속이기 위해서, 가장 적은 가로줄로 사다리를 빨리 그리려고 한다. 예를 들어, 아래와 같은 사다리를 보자. 희원이는 이 사다리의 1번 시작점은 2번째 도착점으로, 2번 시작점은 3번째 도착점으로, 3번 시작점은 1번째 도착..
