어흥

문제 링크: 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 1. 주의할 점 - DFS +DP를 이용하여 메모아이징을 사용해야 한다 2. 구현 - 모든 간선들의 정보를 V[] 배열에 담는다 - 입력 받은 Root를 기준으로 DFS()를 수행하며 메모아이징을 이용해서 해결한다. 또한, Visit[] 배열을 사용하여 해당 Node의 부모를 세지 않도록 한다 #include #inc..

문제 링크: https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWlGyBQqaEgDFASG SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - Check[idx] 배열을 만들어서 값을 기록해놓는다(idx의 경우 최대 몇 번의 Turn이 가능한지) 2. 구현 - 초기에 Check[] 배열을 전부 -1로 초기화하고 한 자리 숫자는 0으로 초기화 한다 - DFS(Sum,Tot,Ss,V)를 통해 해당 Ss를 몇 부분으로 쪼갤 수 있는지 벡터 V에 담는다 - Sum==Tot인 경우, V의 Size가 1..

문제 링크: https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 주의할 점 - DP처럼 진행한다 - 가장 긴 증가하는 부분 수열을 어떤 방식으로 담을 건지 생각한다 2. 구현 - 배열을 입력받으면서, Result[]배열도 초기화 작업을 한다 - i: 1~Num-1, j: 0~i-1까지 반복하면서 Arr[i]>Arr[j]를 만족한다면 Result 배열의 인자를 비..

문제 링크: https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다. 지도 밖으로 나가는 방향의 입력은 주어지지 않는다. www.acmicpc.net 1. 주의할 점 - DP(메모아이제이션) + DFS로 해결한다 2. 구현 - Check[][] 배열을 -1로 초기화 시킨다 - 2중 For문을 돌며 Check[][]값이 -1이면 DFS()를 수행하며, 끝나면 Cnt++를 해준다 - DFS(y,x)에서는 Check[y][x]값이 -1이 아니면..

문제 링크: https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미 www.acmicpc.net 1. 주의할 점 - DP를 통해 해결한다 - 왼쪽, 위, 왼쪽위 대각선을 살핀다(처음엔 오랜쪽으로 했는데 바꿨다) 2. ..

문제 링크: https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직사각형 지도로 나타낼 수 있으며, 1×1크기의 정사각형으로 나누어져 있다. 구사과의 위치는 (1, x)로 나타낼 수 있으며, (1, x)는 왼쪽에서부터 x번째 칸을 의미한다. 지도의 각 칸에는 E, W중의 한 문자가 쓰여져 있는데, 구사과는 이 문자를 이용해서 이동한 www.acmicpc.net 1. 주의할 점 - 메모아이징을 사용한 DFS를 이용한다 (DP문제) 2. 구현 - Check[] 배열을 전..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 조합, DP를 통한 풀이 방법이 있지만, DP(메모아이징)를 통해 해결한다 - 시작 전, DP[][]의 값을 전부 초기화한다 2. 구현 - DP[Idx][Remain] 배열을 통해 해당 Idx의 위치에서 Remain만큼 남은 칼로리가 있을 때, 얻을 수 있는 가장 큰 점수를 저장한다 - Knapsack 알고리즘을 통해 해당 'Idx의 위치에 있는 재료를 추가해서 얻을..

문제 링크: https://www.acmicpc.net/problem/17305 17305번: 사탕 배달 사탕을 좋아하는 아기 석환은, 집에 N개의 사탕이 들어있는 자루를 들여놓았다. 자루에는 두 가지 종류의 사탕이 있는데, 작은 사탕은 3g의 무게를 가지고, 큰 사탕은 5g의 무게를 가진다. 똑똑한 아기 석환은 자루에 있는 모든 사탕에 대해서, 그 사탕의 당도 si 를 계산해 놓았다. si 는 양의 정수로, si 가 클수록 사탕은 달콤하다. shake! 2019 대회에 참가하기 위해 짐을 싸고 있는 아기 석환은, 달콤한 사탕을 최대한 많이 담아가서 대회 도 www.acmicpc.net 1. 주의할 점 - 최대 25만개의 데이터로 인해 Knapsack 알고리즘은 불가능하다 - 가중치/ 무게의 비율 즉, ..