Hyun's_Devlog

https://www.acmicpc.net/problem/17208

동적계획법으로 접근한 문제다.

풀이 방법

2차원 배열 dp를 생성. x열은 소유하고 있는 버거를, y행은 소유하고 있는 감자튀김이다.

따라서 dp[x][y]는 버거 x개와 감자튀김 y개를 가지고 있을 경우 받을 수 있는 최대 주문의 수를 의미한다.

M행 K열의 2차원배열을 생성해야 하는데, 인덱스로 접근하기 편하게 dp[M+1][K+1] 배열로 선언하였다.

입력된 주문이 버거 M개 혹은 감자튀김 K개를 초과한다면 해당 주문은 탐색할 필요가 없다.

dp[M][K]부터 dp[0][0]까지 역순으로 탐색하여 (동일 주문은 하나만 받을 수 있다.)

주문을 받지 않고 남아있는 음식을 아낄 것인지 (dp[x][y]) 혹은

해당 주문을 받을 것인지 (dp[x-현재 주문의 버거 개수][k-현재 주문의 감자튀김 개수]+1)

둘 중 더 큰 값을 선택하여 현재 탐색 중인 곳을 갱신하면 된다.

따라서 현재 보유 중인 버거가 x개, 감자튀김이 y개이며 현재 요청된 주문의 버거 개수가 dx, 감자튀김의 개수가 dy일 경우, 점화식은 다음과 같다.

dp[x][y] = max(dp[x-order.dx][y-order.dy]+1,dp[x][y])

정답 코드

https://www.acmicpc.net/problem/7211

유니온 파인드의 기본 문제다.

풀이 방법

입력되는 간선 정보를 저장한다.

이때 국가소유의 간선인지 아닌지 또한 저장해야 한다.

간선정보를 비용순서로 정렬. 모든 단선을 탐색하며 유니온 과정을 수행한다.

• 해당 간선이 국가소유의 간선이며 최소 스패닝 트리에 포함되어야 하는 간선이라면 비용을 0으로 하여 필요한 비용으로 추가한다.
• 해당 간선이 국가소유의 간선이지만 최소 스패닝 트리에 포함하면 안 되는 간선이라면 해당 간선의 비용을 필요한 비용에서 빼준다.
• 국가소유의 간선이 아니라면, 최소 스패닝 트리에 포함되는지 여부를 확인한 뒤 필요한 비용에 반영하면 된다.

필요한 비용이 0보다 작다면 0을 출력. 그 이상이라면 해당 비용을 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/3271

번역기능으로 문제를 봐도 이해되지 않아 헤맸다. chatGPT를 통해 번역과 설명을 보고 나서 이해하여 정답을 받았다..

기본적인 최소 스패닝 문제.

풀이 방법

B마리의 벌들이 F개의 꽃을 최소 스패닝 트리로 구성하여 각 구역을 분담하여 탐색하게 된다. 이때 각 벌들이 분담받은 이동 경로 중 한 번에 가장 많이 이동한 거리의 최솟값을 출력하라는 얘기.

따라서 크루스칼 알고리즘을 컴포넌트가 B개가 될 때까지 진행하고, 이때까지 가장 많이 이동한 거리를 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/17090

그래프 탐색 문제. 시간초과를 해결하지 못해 결국 풀이를 찾아보았다.

풀이 방법

배열 범위 밖으로 탈출할 수 있는 노드의 수를 반환해야 한다.

단순히 깊이우선으로 모든 노드에 수행하게 되면 시간초과가 일어난다.

미로의 각 칸에서 넘어가는 다음 칸은 지정되어 있다. 따라서 이미 탐색을 수행한 노드의 끝이 맵 밖으로 이어지는지,  아니면 맵을 탈출 하지 못하고 사이클을 형성하는지 미리 저장해 둔다면 시간 내에 정답을 반환할 수 있다.

미로와 같은 크기의 N*M 2차원 visited 배열 생성. 특정 좌표를 아직 탐색하지 않았다면 -1, 해당 좌표가 탈출하지 못하는 좌표라면 0, 미로를 탈출할 수 있는 좌표라면 1을 저장한다.

깊이 우선 탐색을 수행. 다음 좌표가 미로 밖이라면 1 반환. 아닌 경우에는 처음 방문 좌표인지 확인하여 처음 방문 하는 곳이라면 (-1) 다음 좌표로 재귀호출이 이루어지며 해당 좌표에 결괏값이 저장된다. 

탐색을 통해 1의 개수를 정답으로 출력하면 된다.

정답 코드

https://www.acmicpc.net/problem/14923

기본형태의 그래프탐색 문제. 단 지팡이의 사용여부라는 조건이 붙어있다.

풀이 방법

너비 우선 탐색으로 목적지까지 그래프 탐색을 시도한다. 중복 방문을 피하기 위한 visited 배열을 3차원으로 생성.

visited[0][X][Y] -> 지팡이를 사용하지 않은 상태로 x,y 좌표 탐색여부,

visited[1][X][Y] -> 지팡이를 사용한 상태로 x,y, 좌표 탐색여부를 나타낸다.

visited 배열을 통해 좌표 탐색을 수행하여 정답을 출력하면 된다.

목적지에 도달하지 못하면 -1을 반환해야한다는 조건을 까먹지 말고 제출하자.

정답 코드

https://www.acmicpc.net/problem/13397

이분탐색으로 접근했다.

풀이 방법

배열의 크기 N이 최대 5000으로 작은 값에 속한다. 따라서 이분탐색으로 찾게 될 값은 구간의 최대 점수를 찾는 문제로 접근했다.

즉 이분탐색으로 mid값을 고정하고 길이 N의 배열을 순차탐색하면서 탐색 중인 구간의 최댓값 - 최솟값이 mid보다 크다면 구간을 나누어 마지막까지 탐색이 끝났을 때 구간의 개수가 M이하라면 최대 점수를 더 낮은 쪽을 탐색, 개수가 M보다 크다면 최대 점수가 더 큰 쪽으로 이분 탐색을 이어가면 된다.

입력 예제를 기준으로 동작을 그림으로 나타내면 다음과 같다. 이분탐색 mid 값이 3, 5, 4 일 경우 각각의 구간의 개수 조건을 확인. 구간의 최댓값이 5일 경우에 조건을 만족하므로 5가 정답이 된다.

정답 코드

https://www.acmicpc.net/problem/8983

이분탐색으로 접근했다.

풀이 방법

주어지는 사대의 위치를 오름차순으로 정렬한다.

이후 주어진 각 동물의 좌표를 기준으로 사대의 위치 0부터 M-1까지 이분탐색을 통해 사격 거리 L에 포함되는지를 확인하였다.

이때 사격거리 L에 포함되지 않는다면 동물의 위치가 비교한 사대보다 왼쪽이라면 즉 (동물의 x축 좌표 < 사대의 x축 좌표)이라면, 현재 사대보다 더 왼쪽에 위치한 사대를 탐색하면 되고, 그 반대라면 보다 오른쪽에 위치한 사대를 탐색하면 된다.

해당 방법으로 접근한다면 O(100,000 * log100,000) 즉 O(500,000)에 탐색이 가능하다.

정답 코드

https://www.acmicpc.net/problem/17471

조합을 통한 완전탐색 + 유니온파인드로 접근하였다.

접근 방법

입력으로 주어지는 구역의 최대개수는 10이다. 따라서 각 구역이 두 가지 선거구로 선택되는 경우의 수를 계산하면 2^10 즉 1024의 경우의 수가 발생. 이후 각 조건에서 유니온 파인드를 수행한다.

유니온 파인드에서 두 노드가 결합되는 조건은 서로 인접하며 정해진 선거구가 같은 경우만 결합하는 것으로 하였다. 마지막으로 컴포넌트의 수가 2인 경우만 각 선거구의 인구수를 확인하여 정답을 반영하면 된다.

정답 코드