분류 전체보기

문제 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 어떤 문제인가? 입력된 그래프를 탐색해나가며 모든 토마토가 익는데 걸리는 최소 날짜를 출력하는 문제이다. 접근 방법 int tomato[1001][1001]; bool visited[1001][1001]; int n, m; 토마토 상자의 값을 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n과 m을 선언해준다. queue q; 탐색에 필요한 큐를 선언해준다. 이때..

문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어떤 문제인가? 각 위치의 높이가 존재한다. 따라서, 0부터 최대 높이까지 모든 경우를 살펴봐야 한다. 잠기는 높이마다 생기는 연결 요소들의 개수가 바뀌게 된다. 이때, 어떤 높이에서 생기는 연결 요소의 최대 개수를 출력하면 된다. int map[101][101]; bool visited[101][101]; int n; 위치들의 높이를 저장할 이차원 배열과 방문 여부를 저장할 이차원 배열, n을..

문제 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 어떤 문제인가? 그래프를 입력받고 연결 요소의 개수를 출력하면 된다. 이 문제를 풀기위해선 먼저 연결 요소가 무엇인지 알아야 한다. 간단하게 말하면 나누어진 각각의 그래프들을 연결 요소라고 한다. 문제의 첫 번째 예시대로 입력을 받으면 1-2-5, 3-4-6이 연결된 두 개의 연결 요소가 존재하는 것이다. 접근 방법 한 정점을..

문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 어떤 문제인가? n*m 크기의 공간에서 0과 1로 미로를 만든다. 1은 지나갈 수 있고 0은 지나갈 수 없는 곳이다. 이때 왼쪽 위부터 출발해 오른쪽 아래까지 갈 수 있는 최소 거리를 구하면 된다. 접근 방법 이동의 가중치가 없는 그래프에서 최단 경로를 구하는 것이기 때문에 bfs를 통해 접근하였다. int miro[101][101]; bool visited[101][101]; 먼저 미로를 저장할 이차원 배열과 방문처리..

문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 어떤 문제인가? 그래프 탐색 방법인 dfs와 bfs를 통해 그래프를 탐색하는 순서를 출력하면 되는 간단한 문제이다. 접근 방법 bool visited[1001]; vectorgraph[10001]; 먼저 그래프를 저장할 벡터와 정점의 방문 여부를 저장할 배열이 필요하다. int n,m,v; cin >> n >> m >> v; 문제에서 주어진 변수들을 ..

문제 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 어떤 문제인가? https://codegarden-farmjun.tistory.com/55 [백준(BOJ)] 2293번 동전1 C++ 문제 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의..

문제 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 어떤 문제인가? n가지의 동전이 있다. 이 때 n가지 동전을 사용해서 k원을 만드는 경우의 수를 구하는 것이다. 접근 방법 이 문제를 dp를 사용해 접근하였다. 문제의 예시로 알아보자. 1, 2, 5원짜리 동전으로 10원을 만드는 경우의 수다. 1원 1 2원 1 1 2 3원 1 1 1 2 1 4원 1 1 1 1 2 1 1 2 2 5원 1 1 1 1 1 2 1 1 1 2 2 1 5 어떤 규칙..

문제 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 어떤 문제인가? 삼각형의 맨 위부터 대각선으로 이동하며 맨 밑으로 내려왔을 때, 지나온 수들의 합이 최대가 되도록 했을 때 그 합을 출력하는 문제이다. 접근 방법 나는 삼각형을 위에서 아래로가 아닌, 밑에서 위로 올라가면서 합이 최대가 되는 경로를 살펴볼 것이다. int triangle[501][501]; 입력을 저장할 이차원 배열을 선언해준다. n이 500까지 입력될 수 있으므로 이에 맞게 배열의 크기를 설정해준다. for (int i = 1; i trian..

문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 어떤 문제인가? 수열 A 중 가장 긴 증가하는 부분 수열의 길이를 출력하면 된다. 증가하는 부분 수열 = 부분 수열이여야 하고 원소들이 오름차순 이어야 한다. 이 중 길이가 가증 큰 것을 찾으면 된다. 접근 방법 이 문제는 dp를 통해 접근하였다. int arr[1001]; int dp[1001]; n이 100..

문제 : https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 어떤 문제인가? 크기가 n인 정수 배열의 부분 배열 중 각 원소들의 합이 가장 큰 부분 배열을 찾아 그 합을 출력하는 문제이다. 접근 방법 일단 이 문제는 dp의 방식으로 접근했다. 코드를 보자. int t; cin >> t; 테스트 케이스의 수를 입력받는다. while (t--) { int n; cin >> n; int arr[n ..