소근소근

Lv3 . 프로그래머스 경주로 건설 (2020 카카오 인턴십) 문제 설명 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 그렇게 어려운..

백준 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 어떤 칸에서 출발하여 계속 대나무가 더 많은 쪽으로만 이동할 때, 최대로 움직일 수 있는 칸의 개수를 구하는 문제이다. 처음에 단순 DFS인줄 알고 이중 for문을 돌며 모든 칸에 대해 dfs를 돌려 최대 칸의 개수를 구했더니 시간초과가 났다. 이 문제는 재귀로 dp를 구현해서 풀면 되는 문제였다. 풀이 해법은 https://yabmoons.tistory.com/15..

백준 11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 어떤 수열이 주어졌을 때, 가장 긴 증가하는 부분수열의 길이를 출력하는 문제이다. dp[N] 배열을 선언하고, dp[N]에는 N번째 수를 마지막 원소를 갖는 가장 긴 증가하는 부분수열(lis)의 길이를 저장한다. O(N^2)으로 푼다. 이중 포문을 돌면서, 현재 수보다 1 작..

백준 내려가기 gold 4 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net N*3 배열이 주어지고, 위에서부터 인접한 위치로 내려가며, 최댓값과 최솟값을 출력하는 문제이다. 평범한 dp로 풀면 될 것 같다. 그런데.. 메모리 제한이 4MB이다. 즉, 일반적으로 생각하는 dp배열을 만들어서 푸는 풀이는 메모리 초과가 나게 된다. sliding window기법을 사용한다. 전체 배열 크기만큼 dp배열을 만드는 게 아니라 실질적으로 필요한 데이터만 저장할 수 있게..