백준
-
백준 1904번: 01타일다이나믹프로그래밍(DP) 2018. 6. 24. 16:44
https://www.acmicpc.net/problem/1904 1. 문제지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 지원이는 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 N개 수열로 이루어진 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) ..
-
백준 11004번: K번째 수정렬(Sort) 2018. 6. 24. 13:19
https://www.acmicpc.net/problem/11004 1. 문제수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 2. 알고리즘키워드 - 정렬 3. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100#define INF 0x7fffffff /*..
-
백준 11726번: 2xn 타일링다이나믹프로그래밍(DP) 2018. 6. 23. 17:19
https://www.acmicpc.net/problem/11726 1. 문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 2. 알고리즘키워드 - 다이나믹 프로그래밍 피보나치 응용 문제로 보이기도 한다.2 x 1 타일 - 1 개2 x 2 타일 - 2 개2 x 3 타일 - 3 개2 x 4 타일 - 5 개N 개의 타일을 만들위해 DP[N] = DP[N-2] + DP[N-1] 점화식을 세울 수 있다. 3. 코드1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #in..
-
백준 11724번: 연결 요소의 개수깊이우선탐색(DFS) 2018. 6. 23. 16:50
https://www.acmicpc.net/problem/11724 1. 문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 2. 알고리즘키워드 - DFS [ Figure 1 ]1번 TestCase 는 연결 요소가 두 개다. [ Figure 2 ]2 번 TestCase 에서는 모든 정점이 연결되어 있어 연결 요소는 하나다. 3. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include #i..
-
백준 2526번: 싸이클구현(Implementation) 2018. 6. 23. 14:51
https://www.acmicpc.net/problem/2526 1. 문제두 자연수 N과 P를 가지고 다음 과정을 거쳐서 나오는 숫자들을 차례대로 출력해보자. 처음 출력하는 숫자는 N이고, 두 번째 이후 출력하는 숫자들은 N을 곱하고 P로 나눈 나머지를 구하는 과정을 반복하여 구한다. 즉, 먼저 N에 N을 곱하고, 이 수를 P로 나눈 나머지를 두 번째에 출력한다. 다음에는 이 나머지에 N을 곱하고 P로 나눈 나머지를 출력한다. 다음에는 이 나머지에 N을 곱한 후 P로 나눈 나머지를 출력한다. 이 과정을 계속 반복해보면 출력되는 숫자들에는 반복되는 부분이 있다. 예를 들어서, N=67, P=31인 경우를 생각해보자. 처음 출력되는 숫자는 67이고, 두 번째로 출력되는 숫자는 67*67 = 4489를 31..
-
백준 1012번: 유기농 배추(BFS)넓이우선탐색(BFS) 2018. 6. 21. 10:25
https://www.acmicpc.net/problem/1012 1. 문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 ..
-
백준 1978번 : 소수 찾기정수론(Number theory) 2018. 6. 20. 12:07
https://www.acmicpc.net/problem/1978 1. 문제주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 2. 알고리즘소수인지 판별 하여 소수인 수를 카운트를 하여 출력 3. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include #include #include #include #include #include #include #include using namespace std; /** @brief - 소수 판별*/int prime(int n){ if (n == 1) { re..
-
백준 15837번 : 백준 온라인 저지문자열(String) 2018. 6. 20. 10:26
https://www.acmicpc.net/problem/15857 1. 문제백준 온라인 저지 사용에 대한 문제. 2. 알고리즘각 문제 별 답안을 출력한다. 3. 코드1234567891011121314151617181920212223// input your code here#include #include #include #include #include #include #include #include #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string s = " abbcdddc"; cout