공부공간

재귀함수를 통하여 해결할 수 있는 문제이다. 수를 입력받는 행렬을 선언하여 뽑을 수 있는 수를 입력 받고, 재귀 함수를 통하여 독일 로또의 출력 숫자인 6개로 출력 행렬이 채워지면 출력한다.

기본적인 형태의 DFS 알고리즘 문제의 변형이다. 문제 풀이의 접근방식은 다음과 같다. 현재 배열(일반인 시각), 변형 배열(적록 색약자의 시각) 을 선언하여 DFS 알고리즘을 통하여 구역의 개수를 세어주면 쉽게 해결할 수 있다.

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net 서로다른 지점에 공유기를 설치하면서 가장 멀리 떨어지게 설치하는 거리를 구하는 문제이다. 첫번째에 놓았다면, FOR문을 돌면서 나머지와의 거리를 계산해주고 CNT로 그 값을 반환하여서 C와 비교하면서 거리값인 MID를 이분탐색으로 업데이트해준다. 처음에 LEFT 를 배열중 가장작은값으로 초기화 시켰는데 틀렸습니다가 나와..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 이분탐색으로 나무를 자르는 문제이다. 절단기의 H를 설정해주면 나무배열에서 H이상의 값을 가진나무들과 H의 차만큼 가져갈수있는 나무가..

N개의 지방에게 알맞는 예산을 분배하는 문제이다. 입력의 마지막에 돈이 주어지는데, 각자 원하는금액을 최대한 맞추어주면서, 내가가지고있는 금액 한도에서 분배해야한다. 즉, 요청값을 정렬한 후에 이분탐색으로 적절한 예산을 찾아주면된다. 두가지의 예외가 존재하는데, 1. 예산이 너무 많아서 모두 원하는만큼 주어도 되는경우 2. 예산이 너무 적어서 원하는금액중 가장 작은 금액으로도 못주는경우 만 이분탐색 전에 체크해주면된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57..

숫자들의 나열중 연속된 숫자중 부분합이 가장 큰 수를 출력하는 문제이다. 1. 모든 수가 음수인경우 (음수중 가장큰 한개를 선택해서 출력해준다) 2. 음수와 양수가 섞여있는경우 ( DP[N]을 구할때 DP[N-1]이 음수라면은 현재의 값을 DP[N]으로 설정해준다. 음수 + 양수는 그냥 양수보다 항상작기때문에)

삼각형을 내려오면서 가질수 있는 최대의 값을 구하는 문제이다. 내려올때에 이전 층의 대각선 방향만 고려하면 되기때문에, DP[N][N]을 구할때 DP[N-1][N-1] + NOW , DP[N-1][N]+ NOW 의 경우중 큰값을 가지고 업데이트 해준다. 맨처음과 끝은 비교해야할 대상이 한가지이므로 이경우만 처리해주면서 진행하면 된다.

계단을 오르면서 얻을수있는 점수의 최댓값을 구하는 문제이다. 맨 마지막을 꼭 밟으면서 연속된 3개의 계단은 밟지 못하는 규칙이 있으므로 1. 두칸을 오르고 맨마지막 직전의 계단을 밟고 마지막 계단을 밟은경우, 2. 두칸을 오르고 맨마지막 직전 계단 이전을 밟고, 직전계단을 밟고 마지막 계단을 밟은 경우로 나뉜다. 즉 dp[n]값을 구하기위해서 dp[n-2] + num[n] 값과 dp[n-3] + num[n-1] + num[n-2] 값중 큰값으로 업데이트해주면서 진행하면된다.