본문 바로가기

백준

 (10)
[백준 9095] 1, 2, 3 더하기 풀이법 숫자 N은 N-1 에서 +1 되서 만들어질 수 있고, N-2에서 +2를 해서 만들어 질 수도 있고, N-3에서 +3을 해서 만들어 질 수 있다. 이를 정리하면, DP[N] : 숫자 N이 표현될 수 있는 방법의 수 DP[N] = DP[N-1] + DP[N-2] + DP[N-3] 예를 들어, 10이 표현될 수 있는 방법의 수는 = 9( 10 - 1 )가 표현될 수 있는 방법의 수 + 8( 10 - 2 )이 표현될 수 있는 방법의 수 + 7( 10 - 3 )이 표현될 수 있는 방법의 수 #include #define MAX11 using namespace std; int T; int dp[MAX]; int go(int n) { if (n == 0) return 1; else if (n < 0) retu..
[백준 1463] 1로 만들기 주어진 숫자( N )에서 세가지 연산을 하는데, 만약, N이 3으로 나누어 떨어지면 N-3, N이 2로 나누어 떨어지면 N-2 아니면, 언제든지 -1을 빼서 N-1을 만들수도 있다. 예를 들어, N = 10 인 경우, 9 or 5 가 될 수 있고 N = 9 인 경우, 8 or 3 이 될 수 있다. 따라서, 이런 방법으로 주어진 숫자를 1로 만드는 최소연산횟수를 구하는 문제였다. - 풀이법 DP[N] : 숫자 N 인 경우를 기록한다. 그럼, 점화식은 if( N 이 2로 나누어질 경우 ) DP[N] = min(1 + DP[N/2, 1 + DP[N-1]) else if( N 이 3으로 나누어질 경우) DP[N] = min(1 + DP[N/3], 1 + Dp[N-1]) else N 이 2 나 3으로 나누어지지 ..
카테고리 목적 * PS(알고리즘 시험)에서 자주 출제되는(변별력 있는) 문제 중 다이나믹 프로그래밍이 포함된다. * 백준 알고리즘 분류 > 다이나믹 프로그래밍에 포함된 문제 순서대로 풀면서 풀이법 기재
[11724] 연결 요수의 개수 간만에 알고리즘 문제를 풀어본다. 문제요약 - 연결된 요소들의 집합의 개수를 구하라. - 탐색 알고리즘을 통해 쉽게 해결할 수 있다.(DFS, BFS) - DFS 방법을 통해 방문한 노드들을 체크해가며 연결되어진 그룹들을 찾는다. - 시작노드에서 이미 방문한 노드로 체크가 되었다면 무시 - 시작노드에서 방문하지 않은 노드라면 집합의 개수 추가 ...더보기 #include #include #define MAX1000+2 using namespace std; int n, m; bool visited[MAX]; vector v[MAX]; void Search(int start) { for (int i = 0; i < v[start].size(); i++) { int end = v[start][i]; if (!..
[백준 2490] 윷놀이 문제 출처 : https://www.acmicpc.net/problem/2490 문제 요약 윷을 던진다.한 개의 윷은 배(0), 등(1) 으로 표현된다. 즉, 4개의 값이 주어진다.(예. 0 0 1 1 : 개)값이 주어졌을 경우 도, 개, 걸, 윷, 모 중 답을 고르시오.문제 풀이 0의 갯수를 구한다. 그래서 0의 갯수 답 0 모 1 도 2 개 3 걸 4 윷 #include#includeusing namespace std; int main() {for (int i = 0; i > a;if (a == 0) {cnt++;}}if (cnt == 0) {cout
[백준 2167] 2차원 배열의 합 문제 출처 : https://www.acmicpc.net/problem/2167 문제 요약 정보가 담긴 2차원 배열이 주어진다.2차원 배열 내에 주어진 구간의 합을 구하는 문제이다. 문제 풀이 이 문제는 동적 계획법을 사용하여 부분(구간)합을 구하는 문제이다. 여기서 부분합이란 ?? 배열 정보 4 5 1 2 3 4 부분합 배열4 9 10 12 15 19 이와 같이 자신의 위치를 포함하여 이전의 값들의 합(누적합)을 배열에 저장해두는 것이다. 이 원리를 확장하여 2차원 배열에 적용을 한 것이 이 문제의 핵심이다. (0, 0) (a, b) (n-1,m-1) 이와 같은 2차원 배열의 정보를 Dp(i, j) : (0,0) 부터 (i, j) 까지의 합을 저장해두자. 하지만 좌측상단의 시작이 (0,0) 아니라면 ?..
[백준 3055] 탈출 문제 출처 : https://www.acmicpc.net/problem/3055 문제 요약 맵에 고슴도치(S)와 비버(D)가 있다.고슴도치가 비버에게 가야한다 (S -> D)중간에 돌과 물을 피해서 가야한다. 돌은 고정되어 있고, 물은 고슴도치가 움직이기전에 먼저 찬다.물은 비버와 돌을 제외하고 빈 곳에 물을 점점 채운다.문제 풀이 문제는 고슴도치가 비버에게 가는 최단거리이다. 앞서 다룬 BFS 의 조건과 같다. 인접한 노드를 향해 가기 때문에 가중치는 1이다. 따라서, BFS 를 사용하여 답을 찾을 수 있다. 이 문제의 특징은 큐(queue)를 두개를 써야한다는 점이다. 물에 관한 큐, 고슴도치에 관한 큐 1. 물을 채운다. --> 2. 고슴도치가 움직인다. --->>> 2.1 비버를 만나면 끝--->..
[백준 1024] 수열의 합 문제 출처 : https://www.acmicpc.net/problem/1024 문제 정리 N과 L이 주어졌을 때, 합이 N이고, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트 출력N 은 10^9보다 작거나 같은 자연수L 은 2보다 크거나 같고, 100보다 작거나 같은 수문제 풀이 0 ~ 10^9 의 숫자로 시작하는 길이 L의 숫자 리스트의 합을 구하면 된다. 가장 짧은 길이이기에 L을 2부터 시작하면 된다.하지만 10^9 * L 의 시간복잡도를 가지기 때문에 너무 많은 시간이 걸린다.따라서, 0 ~ 10^9 를 이진탐색을 이용하여 구하면 시간초과를 해결할 수 있다. (참고로 숫자 a 를 시작으로 하는 길이 l의 합의 공식은 = l * (2a + l-1) / 2 이다.) 또한 10^9 큰 ..

티스토리툴바