프로그래머스 땅따먹기 c++ 풀이 Level 2 연습문제 땅따먹기 문제 정리 땅따먹기의 땅은 총 N행 4열 모든 칸에는 점수가 있다. 1행부터 땅을 밟으며 한 행씩 내려오며, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 한다. 단, 한 행씩 내려올 떄, 같은 열을 연속해서 밟을 수 없다. 마지막 행 까지 내려왔을 때, 얻을 수 있는 점수의 최대값으 구하여라. 문제 접근 DP??? 백준의 진우의 달 여행(Large) 문제와 비슷한 방식이라고 생각했습니다. 우선 dfs로 풀어보았습니다. 효율성 테스트도 있어서 시간초과 발생!!! 그래서 이번에는 풀이를 머릿속에 넣고 dp로 접근했습니다. 풀이가 잘 기억이 나지 않아 달 여행 문제 풀이를 보고 손으로 정리해보았습니다. 3차원 배열을 만들어서 [이전 col][현..

BOJ 1463번 1로 만들기 자바(java) 풀이 난이도: 실버3 백준 1463번 1로 만들기 문제 정리 정수 X가 3으로 나누어 떨어지면, 3으로 나눈다 정수 X가 2로 나누어 떨어지면, 2로 나눈다 1을 뺀다 위의 3가지 연산을 이용해 주어진 정수 N을 1로 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 구하여라 1

프로그래머스 가장 큰 정사각형 찾기 자바(java) 풀이 Level 2 연습문제 가장 큰 정사각형 찾기 문제 정리 1과 0으로 채워진 표가 있다. 표 1칸은 1x1의 정사각형으로 이루어져 있다. 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하여라 naive한 문제 풀이 처음에는 정말 naive하게 5중 for문을 이용해서 풀어보았습니다. 정확성은 모두 맞추었지만 역시나 효율성 테스트는 통과하지 못했습니다. 최대 크기의 board에서 우측하단 하나만 0인 경우 이런 경우 터질 것 같습니다. naive한 코드는 아래와 같습니다. public static int solution(int [][]board) { int x_len = board.length; int y_len = board[0].le..

BOJ 9252번 LCS2 문제 자바(java) 풀이 백준 9252번 문제를 풀 수 있으면 백준 9251번 LCS를 풀 수 있기 때문에 9252번 문제를 기준으로 설명드리겠습니다!! 난이도: 골드5 BOJ 9252번 LCS2 문제정리 두 수열이 주어졌을때 모두의 부분 수열이 되는 수열 중 가장 긴 것(LCS)을 찾아라 문자는 대문자로만 이루어지며 최대 1000글자 긴 문자가 여러개 있다면 아무거나 출력하고, 최대 길이도 출력하여라 LCS 이 문제는 문제 이름이 그렇듯이 LCS(Longest Common Subsequence) 알고리즘을 이용해 풀 수 있습니다. subsequence는 보통 알고 있는 substring하고는 다릅니다. subsequence: 연속되지 않은 부분 문자열 substring: 연..

sw expert academy 1260번 화학물질2 문제 자바(java) 풀이 난이도 : D6 sw expert academy 1260번 화학물질2 문제정리 이 문제는 조건이 많으므로 잘 읽어보아야 합니다. 그리고 이 문제를 풀기전에 행렬찾기(1258번) 문제와 금속막대(1259번) 문제를 풀어보시는 것을 추천드립니다. 창고에 n*n 배열 형태로 화학 물질들이 있다. 빈 용기는 0 화학 물질이 들어 있는 용기는 화학 물질의 종류에 따라 1~9 사이의 값을 가짐 화학물질이 담긴 용기들이 사각형을 이루고 있다. 사각형 내부에는 빈 용기가 없다. 화학 물질이 담긴 용기들로 이루어진 사각형들은 각각 차원이 다르다. (열과 행의 개수가 서로 다르다) 2개의 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에는 ..

sw expert academy 3282번 0/1 Knapsack 문제 자바(java) 풀이 난이도 : D3 sw expert academy 3282번 0/1 Knapsack 문제정리 1~N번 까지 번호를 부여 받은 N개의 물건과 최대 K 부피 만큼 물건을 넣을 수 있는 가방이 있다. 각 물건은 부피 Vi와 가치 Ci를 가지고 있다 (각 값은 최대 100) 물건들 중 몇개를 넣어서 가방에 들어간 물건들 가치의 합을 최대가 되게 하려고 한다. (이때 부피의 합이 K를 초과하면 안된다) 문제 풀이 점화식을 세워서 문제를 풀 수 있습니다. 즉 DP 테이블을 만들 것입니다. object의 첫번째 열[i][0]은 물건의 부피를 두번째 열[i][1]은 가치를 나타냅니다. 행 i는 i번째 물건을 넣는경우, 열 j는 ..