알고리즘 문제풀이
-
[백준/BOJ] 11727번 2×n 타일링 2 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 00:02
www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 11726번과 거의 비슷한 DP 문제입니다. 맨 오른쪽 끝에 하나를 놓는 경우 d[n - 1], 맨 오른쪽 끝에 두개를 놓는 경우 2*d[n - 2]로 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] = d[n - 1] + 2*d[n - 2] /* Bottom-Up */ #include using namespace std; int dp[1001]; int main(void) { ios_base::sync_with_stdio(false)..
-
[백준/BOJ] 11726번 2×n 타일링 (C++)알고리즘 문제풀이/백준 2020. 12. 18. 23:59
www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net DP 유형의 기본 문제입니다. dp[n]은 가로길이가 n개인 바닥을 채울 수 있는 타일의 경우의 수를 의미합니다. 직접 몇개 그려가다보면, 채울 수 있는 타일의 경우가 1x2 직사각형 하나로 끝나는 경우, 2x1 직사각형 두개로 끝나는 경우 두가지입니다. 즉 dp[n]은 가로길이가 n-1개인 바닥을 채울 수 있는 경우의 수 + 가로길이가 n-2개인 바닥을 채울 수 있는 경우의 수입니다. 따라서 다음과 같은 점화식을 도출해낼 수 있습..
-
[백준/BOJ] 17521번 Byte Coin (C++)알고리즘 문제풀이/백준 2020. 12. 18. 01:12
www.acmicpc.net/problem/17521 17521번: Byte Coin 입력은 표준입력을 사용한다. 첫 번째 줄에 요일 수를 나타내는 양의 정수 n과 초기 현금 W(1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000)가 주어진다. 다음 n 개의 줄에서, i번째 줄은 i일의 바이트 코인 가격을 나 www.acmicpc.net 그리디 문제 유형이라고 나오는데, 저는 DFS를 이용한 완전 탐색으로 매수/매도하는 모든 경우의 수를 구하고, 그 중에서 최대값을 구해 문제를 해결했습니다. 이때, 코인의 개수와 현금이 int 범위를 벗어날 수 있으므로 long long을 쓰는 것을 주의해야합니다. #include #include using namespace std; int n, w; long long a..
-
[백준/BOJ] 1463번 1로 만들기 (C++)알고리즘 문제풀이/백준 2020. 12. 18. 00:57
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net BFS 혹은 DP로 해결할 수 있는 문제입니다. DP 풀이는 Bottom-Up 방식으로 1부터 n까지 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우중 최소값을 dp 테이블에 기록하고, 마지막에 dp[n]의 값을 리턴하면 됩니다. #include using namespace std; int dp[1000001]; // i를 1로 만들기 위해 필요한 연산 사용 횟수의 최소값 int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin>>n; for..
-
[백준/BOJ] 18111번 마인크래프트 (C++)알고리즘 문제풀이/백준 2020. 12. 17. 16:55
www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 브루트 포스(완전 탐색) 유형의 문제였습니다. 블록의 높이가 최대 256에 2차원 배열이 최대 500x500이므로 시간복잡도가 256 x 500 x 500 = 64,000,000로 충분히 완전 탐색으로 해결할 수 있습니다. 인벤토리에 블록을 꺼내어 놓기, 블록을 제거하여 인벤토리에 넣기, 아무것도 안하기 세가지 경우를 고려해야하는데, 첫번째 경우에서 인벤토리가 0보다 작은 경우까지 고려하다보니 너무 예외처리가..
-
[백준/BOJ] 14226번 이모티콘 (C++)알고리즘 문제풀이/백준 2020. 12. 15. 21:17
www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net BFS와 DP를 이용한 문제 (다시 풀기) 화면과 클립보드를 가진 2차원 visit 배열을 선언하여 방문 여부를 확인하고 그 값으로 시간을 기록하는 것이 포인트입니다. 또한 클립보드의 내용을 화면에 출력하는 과정에서 '화면 + 클립보드 < 입력값의 최대' 조건을 반드시 만족해야 런타임 에러가 발생하지 않습니다. #include #include #include using namespace std; int visit..
-
[백준/BOJ] 1525번 퍼즐 (C++)알고리즘 문제풀이/백준 2020. 12. 13. 18:01
www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 독특한 유형의 BFS 문제였습니다. (다시 풀기) 메모리 제한이 있기 때문에 3x3 2차원 배열에 입력값을 저장하지 않고 문자열을 이용해서 1차원으로 입력값을 저장하는 것이 포인트입니다. 예를들어 1 0 3 4 2 5 -> 1 0 3 4 2 5 6 7 8 6 7 8 6 위에처럼 2차원 배열을 1차원으로 저장하는 것입니다. 이러한 1차원 문자열과 걸린 시간을 큐에 집어 넣으면서 문자열 처리를 해주면 되는데, 이때 0의 인덱스가 어디 있는지 찾는 것이 중요합니다. 이 인덱스를 통해 3x3 배..
-
[백준/BOJ] 10989번 수 정렬하기 3 (C++)알고리즘 문제풀이/백준 2020. 12. 13. 14:49
www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 입력값이 최대 10,000,000 이라서 시간복잡도가 O(NlogN)인 병합정렬을 이용해서 문제를 먼저 해결했다가 메모리 초과가 발생했습니다. 그래서 시간 복잡도와 공간 복잡도 모두를 만족할 수 있는 방법이 무엇이 있을까 검색을 해본 결과 계수 정렬을 이용하면 이 문제를 해결할 수 있다는 것을 알게 되었습니다. #include #include using namespace std; vector v(10001); int main(v..