Algorithm
-
[백준][1965번] 상자넣기Algorithm/백준 2020. 3. 29. 21:49
https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 www.acmicpc.net 풀이과정 오름차순 부분배열을 구하는 문제이다. dp[N]은 map[N]을 포함하는 가장 큰 부분배열의 길이이다. map[N]보다 작은 값..
-
[백준][1904번] 01타일Algorithm/백준 2020. 3. 29. 21:45
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 사용언어 C++ 풀이과정 00, 1을 사용하여 만들 수 있는 N자릿수 2진수 갯수를 찾는것이다. dp[N] = N개의 이진수 갯수 EX)..
-
[SWEA][9280번] 진용이네 주차타워Algorithm/SWExpertAcademy 2020. 3. 29. 21:40
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW9j74FacD0DFAUY SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com LEVEL D3 사용언어 C++ 풀이과정 복잡한 알고리즘은 없으며, 들어오는 순서대로 상황에 맞게 처리해주면 되는 시뮬레이션 문제로 판단되었다. 주차장이 꽉차있으면, wait하도록 했으며, 주차장에서 차가 나갈경우 wait 차량이 있으면 바로 주차하도록 구현했다. 소스코드 더보기 #include #include #include using namespace std; int N, M; int R[101..
-
[백준][1699번] 제곱수의 합Algorithm/백준 2020. 3. 26. 22:33
https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 풀이과정 N을 만들 수 있는 제곱수들의 합 중 최소의 항을 구하는 문제이다. 2 = 1^2 + 1^2 2개이며, 4 = 2^2 1개이다..
-
[백준][2133번] 타일 채우기Algorithm/백준 2020. 3. 26. 22:29
https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net 풀이과정 그림이 필요하므로 일단 생략.. 소스코드 더보기 #include #include int dp[31]; int N; int solution(int n) { if (dp[n] != -1) { return dp[n]; } dp[n] = 0; if (n % 2 == 1) { return dp[n]; } ..
-
[백준][11054번] 가장 긴 바이토닉 부분 수열Algorithm/백준 2020. 3. 25. 22:58
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이과정 부분 수열은 1, 2, 3, 2 1 과 같이 오름과 내림이 있는 수열을 말한다. 오름차순 수열과 내림차순 수열을 최대 길이를 구하여 문제를 풀었다. 오름차순은 dp[N] = dp[1]....dp[N-1] 중 map[N] 값 보다 작으면서 젤 긴 수열을 찾아 +1을 해주었다. 내림차순은 뒤에서 시작했다. 특정 K값에서 내림차순으로 수열을 정의해야 K값이 겹치기 때문이다. 이제 dp[K] + dp2[K] 값 중..
-
[백준][1912번] 연속합Algorithm/백준 2020. 3. 25. 22:49
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이과정 연속 된 부분 수열 중 최대값을 구하는 문제이다. dp[N] 에는 map[1] ... map[N]까지의 합 또는 map[N]값중 더 큰 값을 저장시켰다. dp[N-1]이 음수인 경우 map[N]이 더 크기 때문이다. (if map[N] > 0) dp[N] = max((dp[N-1] + map[N]) , map[N]) 과 같은 점화식을 구 할 수 있었다. 소스코드 더보기 #include int dp[..
-
[백준][2579번] 계단 오르기Algorithm/백준 2020. 3. 25. 22:41
https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 풀이과정 계단을 1칸, 2칸 전진 가능하며, 연속해서 3계단을 밟을 수 없다는 조건을 생각해보면, 아래와 같이 2가지 경우가 존재한다. O는 밟은 계단, ..