■ 알고리즘 문제 풀이/BOJ (48) 썸네일형 리스트형 [BOJ] 백준 2056. 작업 ▶문제설명[BOJ] 백준 2056. 작업 https://www.acmicpc.net/problem/2056 ▶Hint 위상 정렬 문제이다. 주어진 입력을 이용해 DAG를 만들고, 각 작업들의 Indegree 값을 구한다. 각 작업들에 소요 되는 시간도 저장한다. 처음에 Indegree가 0인 정점들을 queue에 push한 뒤 위상 정렬을 수행한다. 주의할 점이 있는데, queue에서 pop된 작업과 연결되어 수행될 작업을 끝내기 위해 소요되는 시간은 최대 값이 되도록 해야한다. 즉, '처음부터 현재 작업까지를 끝내기 위해 소요되는 시간 + 다음 작업 하나를 끝내기 위해 필요한 시간' 값이 최대가 되어야 한다. 예를 들어 작업 A를 수행하기 위해 B와 C를 선행해야 한다고 했을 때, MAX(처음부터 B까.. [BOJ] 백준 2252. 줄 세우기 ▶문제설명[BOJ] 백준 2252. 줄 세우기 https://www.acmicpc.net/problem/2252 ▶Hint 위상 정렬(Topological sort) 문제이다. 위상 정렬은 DAG(Directed Acyclic Graph : 방향성 비 사이클 그래프)에서 쓸 수 있는 알고리즘이다. 학생 N명을 줄 세우려 하는데, 일부 학생들의 키를 비교하여 누가 누구 앞에 있는지에 대한 정보를 입력으로 주고, 그에 맞추어 줄 세운 결과를 출력해야한다. 위상 정렬은 여러 개의 답이 나올 수 있고, 주어진 출력 결과와 다르더라도 위상 정렬이 제대로 되었다면 정답으로 인정된다. DFS를 이용한 방법과 각 정정의 Indegree 값을 이용한 방법이 있는데, Indegree 값을 이용해 풀어보았다. 정점이 3개이.. [BOJ] 백준 3190. 뱀 ▶문제설명[BOJ] 3190. 뱀 https://www.acmicpc.net/problem/3190 ▶Hint 뱀이 사과를 먹었을 경우 꼬리가 길어져서 꼬리 끝의 좌표를 그대로 두면 되지만, 사과를 먹지 못 했을 경우 꼬리 끝의 좌표가 머리를 따라서 한 칸 이동해야한다. 사과를 먹지 못했을 경우를 잘 처리해 주는 게 관건이다. 이차원 배열 map을 만들고, 시간의 흐름에 따라서 1부터 시작해 1씩 증가된 값을 저장하여 뱀을 나타내도록 구현했다. 그리고 꼬리 끝의 좌표와 머리의 좌표를 따로 저장하여 활용했다. 사과를 먹지 못했을 경우 꼬리 끝의 좌표에서 상/하/좌/우를 탐색해 가장 큰 값을 찾고 그 값의 위치로 꼬리의 끝이 이동하도록 구현하면 사과를 먹지 못했을 경우를 적절히 처리할 수 있다. (더 간단한.. [BOJ] 백준 2156. 포도주 시식 ▶문제설명[BOJ] 백준 2156. 포도주 시식 https://www.acmicpc.net/problem/2156 ▶Hint DP 문제이다. [규칙]포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 규칙에 따르면, 하나의 잔 기준으로 세 가지 경우로 나눌 수 있다. 1. 이전 잔의 포도주를 마시고 현재 잔의 포도주를 마시는 경우 : A = dp[N-3] + glasses[N-1] + glasses[N]; [N-3] [N-2][N-1] [N]N-3번째 잔까지의 최대값 이 잔을 마시고이 잔을 마심 2. 이전 잔의 포도주를 마시지 않고 현재 잔의 포도주를 마시는 경우 : B = dp[N-2] + gl.. [BOJ] 백준 1932. 정수 삼각형 ▶문제설명[BOJ] 백준 1932. 정수 삼각형 https://www.acmicpc.net/problem/1932 ▶Hint DP 문제이다. 예시로 주어진 크기가 5인 정수 삼각형은 아래와 같다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 입력으로 주어질 때는 아래와 같이 주어진다.5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 입력으로 주어진 정수 삼각형을 아래와 같이 2차원 배열에 저장할 수 있다.dp[0][1][2][3][4][5][0]0 0 0 0 00 [1]0 7 0 0 00 [2]0 3 8 0 00 [3]0 8 1 0 00 [4]0 2 7 4 40 [5]045265 숫자 7이 저장된 dp[4][2]를 예로 들면, 왼쪽 위에 있는 숫자는 dp[3][1]이 되고 오른쪽 위에 있.. [BOJ] 백준 2579. 계단 오르기 ▶문제설명[BOJ] 백준 2579. 계단 오르기 https://www.acmicpc.net/problem/2579 ▶Hint DP 문제이다. [주어진 계단 오르기 규칙]계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다. 연속해서 세 개의 계단을 밟을 수 없다. 따라서 하나의 계단 기준으로 두 가지 경우로 나눌 수 있다. 1. 이전 계단을 밟은 경우 : A = dp[N-3] + stairs[N-1] + stairs[N]; [N-3] [N-2] [N-1] [N] 출발 지점 여기를 밟고 여기로 도.. [BOJ] 백준 1022. 소용돌이 예쁘게 출력하기 ▶문제설명[BOJ] 1022. 소용돌이 예쁘게 출력하기 https://www.acmicpc.net/problem/1022 ▶Hint 시뮬레이션 & 구현 문제이다. 소용돌이 전체를 배열에 저장하지 않고 필요한 부분만 저장해야 한다는 점과 숫자의 길이가 맞지 않으면 공백을 추가해서 예쁘게 출력해야 한다는 점이 핵심이다. 소용돌이 전체를 배열에 저장하려면 10001x10001 크기의 int형 2차원 배열이 필요한데, 문제의 메모리 제한이 128mb이므로MLE(Memory Limit Exceeded)가 발생한다. 출력해야 할 소용돌이의 숫자 중에서 가장 큰 숫자를 찾고 그 숫자의 길이에 맞춰서 길이가 짧은 숫자의 경우 공백을 추가하여 가장 큰 숫자의 길이와 맞게 '예쁘게' 출력해주면 된다. ▶시간 복잡도 소용돌.. [BOJ] 백준 1654. 랜선 자르기 ▶문제설명[BOJ] 1654. 랜선 자르기 https://www.acmicpc.net/problem/1654 ▶Hint 이분탐색 문제이다. 이분 탐색 문제는 일반적으로 값의 범위는 넓지만 특정 값을 미리 정해놓고 시뮬레이션 해보는 것이 가능한 문제에 적용이 가능하다. ( 1 이전 1 2 3 4 5 6 다음