백준 No.2008 [사다리 게임]
백준 No.2008 [사다리 게임] 문제 2008번: 사다리 게임 (acmicpc.net) 2008번: 사다리 게임 사다리 게임을 할 때 사용되는 사다리가 있다. 세로선은 N개가 있고, 가로선은 M개가 있다. 세로선은 맨 왼쪽 것부터 1, 2, …, N의 번호가, 가로선은 맨 위의 것부터 1, 2, …, M으로 번호가 붙어 있 www.acmicpc.net 설명 * dp 2차원 dp 를 이용하여 풀이가 가능하다. dp[i][k] : i 번째 가로선까지 체크를 했을 때 시작점에서 k 번째 세로선까지 오기까지의 최소비용 위 값을 결정하기 위해선 이전 dp 값의 왼쪽, 현재 위치, 오른쪽 인 dp[i - 1][k - 1], dp[i - 1][k], dp[i - 1][k + 1] 을 고려한다. 1) dp[i - ..
2022. 12. 4.
백준 No.11053 [가장 긴 증가하는 부분 수열]
Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 설명 Dynamic programming 을 이용하여 Memoization 을 통해 풀 수 있다. 아래와 같이 가장 긴 증가하는 부분수열을 구해야 하는 arr 배열이 있다. 정답을 구하기 위해서 arr 의 첫 번째 수 부터 li..
2021. 7. 28.
Programmers [가장 큰 정사각형 찾기]
Programmers [가장 큰 정사각형 찾기] Problem 코딩테스트 연습 - 가장 큰 정사각형 찾기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; int solution(vector board) { int width = board[0].size(); int height = board.size(); int answer = 0; for (int i = 0; i
2021. 2. 1.
