문제 링크 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 문제 풀이 - 인접 리스트 사용하여 시간 복잡도 O(V + E) = O(10,000 + 9,999) - 트리이기 때문에 간선의 수 = 노드의 수 - 1 - DFS 방식으로 리프 노드 구하는 문제에서 응용하는 문제로 2차원 배열로 방문 여부에 따라 조건 처리를 하게 된다 - 시작 노드는 1로 해서 최종적으로 DP[1][0], DP[1][1] 중 최대값이 최대 인구에 해당한다 DP..

문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 풀이 스스로 풀지 못하여서 기술 블로그를 참고 하였고, 이번 문제를 통해 DP 기법과 Two Poiner 기법 응용하는 방식에 대해 처음으로 알게 되었다. 풀이 후 몇일 있다가 손으로 그려보고 Top-Down, Bottom-Up 풀이하는데 역시나 쉽지 않은 문제인 것 같다. 가짜문제 정의, 초기화 항목 .. 단순히..

문제 링크 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 풀이 - 시간 복잡도 O(V + E) // 인접 리스트 사용 - 백준 링크에 들어가보면 하단에 친절하게 로직을 설명하고 있어 참고하면 됨 # 입력 트리를 그릴 경우 5번 Root 기준 5 4 6 3 7 8 9 1 2 # subtree 결과 subtree [0, 1, 1, 3, 4, 9, 4, 1, 1, 1] 제출 코드 ..

문제 링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N) - 1,2,3 더하기 문제에서 조금 변형된 문제, 상향식, 하향식 연습하기 좋은 문제 - 단, 같은 숫자를 연속적으로 붙일 수 없기 때문에 이전 숫자에서 무엇이 사용되었는지 상태값을 기록할 필요가 있다 (2차원 배열 사용) - 간단하게 2차원 배열로 해서 1 ~ 3 숫자 사용 여부를 표기하고 동일하게 점화식으로 구하면 됨 - 최대치 long DP[N + 1][4] 2차원 배열 생성 ( DP[N][1..

문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 풀이 - 입력의 경우 int 배열로 100개까지 받으므로 400byte - 연산에 필요한 DP의 경우 행20 * 100 * 8byte = 16KB 정도 메모리 잡음 - 최대치의 경우 출력에 2^63 -1 명시되어 있기 때문에 long으로 처리 시간 복잡도 상향식 (Bottom-Up) 하향식(Top-Down, 재귀 함수) O(N * 20) O(2^n) = O(2^100) - ..

문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 - 시간복잡도 : O(N) - 점화식 DP[N] = DP[N - 2] + DP[N - 1] 형태로 최대 N이 90까지 가능하다 - 피보나치의 경우 46번째만 넘어가도 29억이 넘기 때문에 long (8byte, 64bit)으로 문제 풀이 해야 함 풀이 순서 가짜 문제 정의 - 가짜 문제로 정답을 구할 수 있는가? - 초기항 - 점화식 - 풀이 & 테스트 0 1 2 ..

문제 링크 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 문제 풀이 - 시간 복잡도 O(N) - 메모리 제한 4MB 직접 문제를 풀었을 때 최대 값을 구하는 것은 Bottom-Up방식으로 설명에 따라 그대로 하였기에 구할 수 있었다. 그러나 최소 값의 경우 구할 수 없었고, 기술 블로그를 찾아 본 결과 '메모리 제한', '슬라이딩 윈도우 기법'와 같은 파악하지 못 한 부분에 대해서도 확인할 수 있었다. (최소값의 경우 반대로 선택 가능 범위 내에 최소 값을..

문제 링크 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 경우 직접 풀이하지 못하고, 기술 블로그를 참고하여 풀 수 있도록 하였습니다. 2차원 배열 DP로 풀이시 문제가 되었던게 '0 ~ 9의 숫자를 사용한 여부는 어떻게 알 수 있을까' 였습니다. 3차원으로 변경하여 0 ~ 9 까지 체크했는지 반복문으로 사용해서 할 경우 그거대로 더 복잡해 질거 같은 생각이 들었습니다. 기술 블로그를 찾아본 결과 해당 문제는 '비트 마스킹' 기법을 사용하여 문제 풀이 가능한 것을 알게 되었고 2~3일간 이해가 되지 않아 시간을 보냈고, 지금은 이해한 내용을 ..

문제 링크 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) - 최대치의 경우 9907에 대한 나머지를 구하라 하므로 Integer로 예상 가능 (문제 설명에 나머지 처리 없는 경우 최대치 잘 파악) 2 * 1 일때 0 의 경우 아무것도 없는 경우 1의 경우 왼쪽에 사자가 있는 경우 🦁 2의 경우 오른쪽에 사자가 있는 경우 🦁 2 * 2의 경우 1) 앞에 블록에 빈 우리 더할 경우 : 3가지 🦁 🦁 2) 왼쪽에 사자🦁가 있는 우리를 추가하는 경우 : 2 가지 빈 우리 아래에 추가하거나 🦁 오른쪽에 사자가 있는 우리 밑에 추가 할 수 있다 🦁 🦁 ..

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 풀이 - 시간 복잡도 O(N), 최대치 Integer 범위 내 - 스티커 하나를 뜯을 경우 상하좌우로 찢어져서 사용할 수 없게 됨 - 2 x N열 스티커, 2차원 배열 형태의 DP 문제 초기화 1 DP[0][i] 50 DP[1][i] 30 0번행의 2열 스티커를 뽑을 경우 아래 선택가능한 영역에서 최대치를 뽑아 더해주면 됨 0 1 2 O 스티커 선택 O O 1번행의 2열..

문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 - 시간 제한 0.5초 이므로 완전 탐색으로 풀 경우 시간 초과 발생 - 첫번째 집의 RGB 값으로 초기값을 설정하고, 동적 프로그래밍으로 풀이한다 - 최종적으로 DP[N][1 ~ 3] 값 중 최소값 출력 - 시간복잡도 : O(N) 점화식 DP[i][j] = Math.min(DP[i - 1][x], DP[i - 1][y]) + RGB[i][j] (이때 i..

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net문제 풀이 - 시간복잡도 O(N)- 초기항 구하고, N번째 포도주에 대해 아래 3가지 경우를 비교하여 최대 값 구함  이때 3번 연달아 포도주를 마실 수 없다는 규칙에 따라 DP 테이블을 갱신한다 i번째 포도주를 마시지 않는 경우① DP[i - 1]할당 i번째 포도주를 마시는 경우② i - 1 번째 포도주 먹고 마시는 경우 최대치 (DATA[i - 1] + DP[i - 3])③ i - 2 번째..

문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 풀이 - DFS로 연산자에 대한 순열(Permutation)을 구한 후 연산 결과값 구함 - N(2 ≤ N ≤ 11) 이므로 최대 연산자 개수는 10개, 순열 10! = 3,628,800 - 시간복잡도 O(N! * N ) = O(10! * 11) = 약 3,600만번 이므로 풀이가능 제출 코드 풀이1. 연산자 순열을 구한 후 연..