기록

문제https://www.acmicpc.net/problem/14719이번 글에서는 백준 온라인 저지의 14719번 문제, "빗물" 문제를 다뤄보겠습니다.2차원 세계에 블록이 쌓여있고, 비가 내린 후 고일 수 있는 물의 총량을 계산하는 문제입니다.풀이문제의 핵심 아이디어어떤 칸에 고일 수 있는 물의 양은 다음과 같이 계산할 수 있습니다:해당 칸에서 왼쪽 방향으로 가장 높은 블록과 오른쪽 방향으로 가장 높은 블록 중 더 낮은 값을 찾습니다.그 값에서 현재 칸의 블록 높이를 뺀 값이 고일 수 있는 물의 양입니다.식으로 나타내면:물의 양 = Math.min(왼쪽 최대 높이, 오른쪽 최대 높이) - 현재 칸의 높이위 계산을 모든 칸에 대해 수행한 후, 이를 모두 더하면 전체 고인 물의 양을 구할 수 있습니다.P..

문제 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 1) 분할된 팰린드롬의 최소 개수 문자열 ABACA가 주어졌을 때 해당 위치 안에서 찾은 팰린드롬을 아래처럼 표현할 수 있다. 각 위치에서 분할된 펠린드롬의 최소 개수를 저장하면, 문자열 전체에서 분할된 팰린드롬의 최소 개수를 저장할 수 있다. dp[e] = min(dp[s]+1, dp[e]) 팰린드롬의 최소개수를 dp로 구하는 풀이(시간초과) def isPal(s, e) : whil..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 1) DFS 원점을 옮겨가면서 깊이 우선 탐색을 진행한다. 단순하게 dfs만으로 구현하면, 시간초과를 만나게 된다. 시간을 줄이기 위해 DP를 이용해야 한다. 2) DP 2차원 배열을 선언해 한번 방문한 노드는 다시 방문하지 않도록 처리하면, 시간을 줄일 수 있다. 3) 기타 매번 dfs를 while문을 쓰다보니, 재귀범위를 넓히는 것을 잘 잊어버린다. 자주 써봐서 익숙해지기..

문제 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 DP 위치를 위, 오른쪽, 왼쪽으로 움직이면서 가장 큰 경우를 board에 저장한다. 1. 0번째 행의 경우, 오른쪽으로만 이동이 가능하다. 2. 1번째 ~ N-1번째 행까지, 오른쪽/왼쪽으로 이동이 모두 가능하다. 2-1. 왼쪽과 위쪽을 비교하여 구한 배열과 2-2. 오른쪽과 위쪽을 비교하여 구한 배열을 비교해 해당 위치에서 가질 수 있는 최대값을 board에 저장한다. 코드..

문제https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한programmers.co.kr풀이dp에 해당 위치에서 얻을 수 있는 최대값을 저장한다.dp[i] = max(i-1번째 집을 털때 최대값, i-2번째 집과 i번째 집을 털때의 최대값) 1. -1번째, 1번째 집을 건너뛴다.2. 0번째 집을 건너 뛴다.초기 경우를 둘로 나누어서 최댓값을 구한다.코드def solution(money): answer = list() # -1번..

문제https://programmers.co.kr/learn/courses/30/lessons/12942# 코딩테스트 연습 - 최적의 행렬 곱셈크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 =programmers.co.kr풀이문제 접근하기행렬곱셈에는 결합법칙이 성립하므로 행렬을 곱하는 순서에 따라 곱셈의 횟수가 달라진다.dp를 사용해서 이 문제를 해결할 수 있다. 우선, N*N의 테이블을 작성한다. 테이블의 각 셀에는 아래에 해당하는 값을 적어 넣는다.dp[시작][끝] = (시작~끝) 범위에 있는 행렬을 모두 곱할 ..

문제https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0programmers.co.kr풀이문제 풀이 방식을 간단하게 표현하면 아래와 같다.1. table에서 모든 퍼즐조각을 찾는다.2. game_board에서 모든 퍼즐..

보호되어 있는 글입니다.