C++ 코딩 문제 풀이/백준113 [Baekjoon] 1012번: 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 해결 과정 착안 상하좌우로 연결된 배추들 사이에는 하나의 배추흰지렁이만 있어도 해충 예방이 가능하므로, 이를 표현하기 위해 편의상 아래와 같은 과정을 주어지는 배추밭 모양에 따라 반복적으로 수행하여 필요한 총 배추흰지렁이의 수를 계산한다. 배추가 심어진 땅이 발견되면 필요한 배추흰지렁이의 수를 1만큼 증가시킨다. 깊이 우선 탐색(depth-first search, DFS) 또는 너비 우선 탐색(bread.. 2023. 8. 24. [Baekjoon] 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 해결 과정 착안 이차원 배열 내에서 $x_1$행 $y_1$열을 좌상단, $x_2$행 $y_2$열을 우하단($x_2 \geq x_1, \space y_2 \geq y_1$)으로 하는 사각형 내의 숫자들의 누적 합을 계산하기 위해, 주어진 이차원 배열과 크기가 같은 배열을 선언하여 동적계획법(dynamic programming)에 활용한다. 이때, 메모.. 2023. 8. 24. [Baekjoon] 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 과정 착안 주어지는 연구소 모양에 대하여 백트래킹(backtracking, 퇴각검색) 알고리즘을 통해 빈 공간에 벽 3개를 세우면서, 바이러스 확산 예상 결과를 너비 우선 탐색(breadth-first search, BFS)을 통해 구하고자 하였다. 구현 편의상 벽의 개수를 파악하기 쉽도록 세우고자 하는 벽의 번호를 3, 4, 5로 정하여 프로그래밍 하였다. 한편 백트래킹 알고리즘에 기반하여 너비 .. 2023. 8. 15. [Baekjoon] 17179번: 케이크 자르기 https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 문제 해결 과정 착안 자르고자 하는 케이크 조각 수를 만족하기 위해 자연수 1부터 $L$까지의 길이 중 가능한 길이의 최댓값을 이진 탐색(binary search, 이분 탐색)을 응용하여 구한다. 구현 편의상 시작 탐색 구간의 우측 끝값을 불가능한 길이인 $L+1$로 설정하여 탐색을 시작하고 아래 코드와 같이 탐색 알고리즘을 구현하였다. [스포 주의].. 2023. 8. 14. [Baekjoon] 16493번: 최대 페이지 수 https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net 문제 해결 과정 착안 이전 포스트에서와 동일한 원리로, 동적계획법(dynamic programming)에 기반하여 문제를 해결하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; struct Chapter { int Days; int Pages; }; Chapte.. 2023. 8. 8. [Baekjoon] 12865번: 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 해결 과정 착안 배낭에 넣고자 하는 물건의 무게의 총합이 $k \space (1 \leq k \leq K)$일 때, 같은 무게로 만들 수 있는 가치의 총합 중 가장 큰 값을 배열에 저장하기 위해 동적계획법을 사용하여 문제를 해결하고자 하였다. $i$번째 물건의 무게를 $w_i$, 가치를 $v_i$라고 하면, $1, 2,\cdo.. 2023. 8. 1. 이전 1 2 3 4 5 6 ··· 19 다음
