DP
-
[프로그래머스] N으로 표현알고리즘/프로그래머스 2021. 8. 17. 21:18
문제 링크 풀이 많은 DP 문제가 그렇듯 점화식만 제대로 세울 수 있으면 어렵지 않은 문제이지만, 꽤 까다로운 문제에 속하는 것 같습니다. 여기에서 d[i]는 solution 함수의 매개변수로 주어지는 N을 i번 사용해서 얻을 수 있는 숫자의 집합으로 정의해 문제를 풀면 수월합니다. 즉 N이 5라면 다음과 같은 점화식을 만들 수 있습니다. d[1] = {5} d[2] = {55, 5+5, 5-5, 5*5, 5/5} d[3] = {555, (5+5) + 5, (5+5) - 5, (5+5) * 5, ... , 55 / 5} 3번째 항부터는 집합의 크기가 커지기 시작합니다. 우리는 규칙을 찾아야 하고요. 일단 N이 i만큼 붙어 있는 숫자 하나는 만들기 쉽습니다. d[4]에는 5555가 있겠지요. d[2]를 보..
-
[백준] 1로 만들기알고리즘/백준 2021. 7. 11. 17:33
문제 링크 풀이 실제로는 10분도 안 돼서 풀었는데, 사소한 실수 하나 사소하지 않은 결과를 만들어 해결까지 거의 30분을 넘게 썼습니다. 처음부터 실수하지 않게 주의하는 것이 중요한 것 같습니다. vs에서는 정적 배열을 백만 개 만들면 경고를 주면서, 프로그램 실행이 되지 않습니다. 동적 배열을 직접 만들거나 벡터를 쓰면 됩니다. 백준에서는 편의성을 위해 스택 공간을 많이 잡아둔 것 같습니다. 정적 배열 백만 개를 만들어도 괜찮네요. 이 문제는 전형적인 DP 문제입니다. d[i]는 i를 1로 만들기 위한 최소 연산 횟수입니다. d[i]는 d[i-1], d[i/2], d[i/3] 중에서 가장 작은 값에 1을 더해주면 되는데, 문제에 나와 있듯이 i가 2의 배수면 2로 나누고, 3의 배수면 3으로 나누는 ..
-
[프로그래머스] 가장 큰 정사각형 찾기알고리즘/프로그래머스 2021. 7. 11. 15:51
문제 링크 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 가로의 길이가 1이거나 세로의 길이가 1인 경우에는, 최대 사각형의 크기가 1을 넘을 수 없으므로 해당 처리만 따로 해줍니다. 이 문제의 풀이법이 명확하게 동적 계획법인지 그리디인지는 잘 모르겠습니다. 현재의 가장 최선인 값을 구해가면서 푸는 것이기도 하고 기존에 구했던 해를 메모이제이션 통해 활용하기도 하기 때문입니다. 둘이 섞였나 봅니다. 이중 반복문을 돌려 board[i][j]를, 그 위치에서 최대 정사각형의 길이값을 넣어줍니다. 예를 들어보겠습니다. board[i][j]가 0이라면 계산하지 않습니다. 계산할 필요도 없고 계산하면 ..