Hello Ocean! 🌼

문제 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 문제를 요약하자면, 정사각형 모양의 board에서 (0, 0)에서 (N-1, N-..

문제 https://www.acmicpc.net/problem/12888 BOJ 나라는 도시와 두 도시를 연결하는 도로로 이루어져 있다. 이 나라의 도로 네트워크는 완전 이진 트리의 형태를 가진다. 수빈이는 BOJ 나라의 도로 네트워크 트리의 높이 H를 알고 있다. 트리의 높이를 안다면, 도시의 개수와 도로의 개수도 구할 수 있다. 트리의 높이가 H인 경우에 도시의 개수는 2(H+1)-1개 이고, 도로의 개수는 2(H+1)-2개가 된다. 아래 그림은 H = 2일 때, 그림이다. 수빈이는 도로 네트워크에 차를 보내려고 한다. 모든 차는 시작 도시와 도착 도시가 있으며, 같은 도시를 두 번 이상 방문하지 않는다. 차의 시작 도시와 도착 도시가 같을 수도 있다. 모든 도시를 방문한 차의 개수가 모두 1개가 되..

문제 배열에서 1로 된 가장 큰 정사각형의 크기를 구해라! www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 DP를 이용하겠다! cache[r][c] = min(min(cache[r + 1][c], cache[r + 1][c + 1]), cache[r][c + 1])+1; cache배열에서 제일 아래 행, 오른쪽 열은 table과 똑같이 채워준다. 그 후에 반복문을 돌면서, table값이 0이면 0으로 채우고 넘어가고, 0이 아니면 아래 그림과 같이 cache[r + 1][c], cache[r + 1][c + 1], cach..

문제 programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 구해보자! 제한사항 이 마을에 있는 집은 3개 이상 1,000,0..

문제 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 유의사항 1+2 와 2+1을 다른 경우로 센다는 것. 0도 사용할 수 있다는 것. 경우의 수를 1000000000으로 나눈 나머지를 출력해야한다는 것 풀이 이 문제는 DP(동적 계획법)을 이용하면 풀 수 있다! 2차원 캐시배열을 이용한 메모이제이션을 적용해야 한다. cache[k][n] : k개의 숫자를 더해서 n을 만들 수 있는 경우의 수 그리고 cache[k][n]은 다음과 같이 구할 수 있다. (점화식) cache[k][n] = cache[k-1][0] + cache[k-1][1] + cacke[k-1][2] + ... + c..

문제 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 처음에는, DP를 어떻게 이용해야할지 떠오르지 않아서 일단 완전탐색으로 구현해보았다. 결과는 너무 당연하게도 시간초과였다! 완전탐색으로 구현하고 나면, DP에 대한 감이 올거라고 생각했는데 전혀 오지 않았다. 결국 검색의 힘을 빌렸는데, 이 문제는 대표적인 "냅색 문제"라고 한다. 냅색 문제(knapsack problem)란? 냅색 문..