본문 바로가기

알고리즘/백준

 (263)
[백준] 1113번 : 수영장 만들기 1113번: 수영장 만들기 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 🤔 문제분석 높이를 1~9 까지 순회하면서 해당 높이에서 수영장을 만들 수 있는 후보를 찾고, 그 후보중에서 만들 수 있는 가장 작은 높이의 수영장으로 만든다. 가장 작은 높이의 수영장이기때문에 다음 높이의 리터레이션에서 물이 다시 채워진다. 바깥쪽에 있는 숫자들은 땅으로 흡수되기 때문에 미리 방문처리를 해준뒤, 그룹을 찾아 나아간다. 그룹을 찾는 과정은 너비우선 탐색으로 해결하였고 해당 그룹에서 가장 작은 높이..
[백준] 17143번 : 낚시왕 17143번: 낚시왕 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 🤔 문제분석 행과 열을 이동할때 어떤식으로 빠르게 이동하게 만들 것인가의 문제를 찾는 것이 핵심이다. Speed 값이 크기때문에 한바퀴만 돌 수 있는 것을 구하면 된다. 열은 (R-1) * 2 의 나눈나머지 값을 구한다면 한바퀴 미만 값의 가중치가 나온다. 행도 마찬가지로 (C-1) * 2를 나눈 나머지 값으로 갱신시킨다. if direction == UP or direction == DOWN: speed = speed %..
[백준] 1509번 : 펠린드롬 분할 1509번: 팰린드롬 분할 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 🤔 문제분석 팰린드롬의 분할개수의 최소값을 구하는 문제로, 지정된 start와 end에서 팰린드롬인지 아닌지 판별을 우선 해야한다. 아래의 예로 ABBAAB의 최소 팰린드롬의 개수를 구하는 과정을 보면 이전에 구했던 A, AB, ABB, ABBA … 가 최소개수를 가지고 있어야한다. X라고 표기된건 현재 팰린드롬이 아니라 무시한다. 💻 코드 import sys inpu..
[백준] 2056번 : 작업 2056번: 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 🤔 문제분석 위상정렬을 알고 있다면 해당문제를 쉽게 풀 수 있다. 위상정렬을 간단하게 설명하자면, 진입차수를 입력받아 진입차수가 0일때만 방문하도록한다. 여기서 방문할때에 기존에 걸렸던 시간중 가장 큰 시간을 가져와서 가중치에 더하면 된다. 문제에서 선행관계에 있는 작업이 하나도 없는 작업이 하나 이상 존재함으로 처음 루트를 방문 할때에 진입차수가 0인 루트가 여러개가 있다는 말임으로, 초기 진입차수가 0인 루트를 찾아서 모두 방문 해..
[백준] 2169번 : 로봇 조종하기 2169번: 로봇 조종하기 🤔 문제분석 이 유형 또한 다이나믹 프로그래밍 응용 문제로, 왼쪽, 오른쪽, 아래쪽으로만 이동 할 수 있는 것을 잘 분석하여 문제를 해결하는 것이 Key Point 이다. 맨위의 행에서는 오른쪽으로만 이동 할 수 밖에 없다, 그 이후의 행에서는 위에서 온경우, 오른쪽에서 온경우, 왼쪽에서 온경우 모두 다 따져봐야한다. 각각의 왼쪽, 오른쪽, 위쪽에서의 값은 항상 최대값을 갖게 만들어야한다. 💻 코드 import sys INF = -int(1e10) input = sys.stdin.readline N, M = map(int, input().split()) table = [list(map(int, input().split())) for _ in range(N)] dp = [[INF..
[백준] 15486번 : 퇴사 2 15486번: 퇴사 2 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 🤔 문제분석 1차원 dp 테이블을 가지고 문제를 해결 할 수 있다. 시간과 금액을 순회하는데 i번째 순회에서의 dp값을 갱신하는 방법은 dp[i+t] = 현재까지의 최대가치 + p로 표현할 수 있다. 해당문제는 현재까지의 최대 가치를 생각해내는 것이 제일 중요한 포인트이다. 예를들어 아래의 표를 살펴보자, i가 5일때 생각해보면, dp[5+5일의시간] = 5일까지 최대 갖을 수 있는 금액 + 5일의 금액 으로 ..
[백준] 13398번 : 연속합 2 13398번: 연속합 2 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 🤔 문제분석 dp 테이블을 2개로 나누어 문제를 해결한다. 하나라도 빠지지않는 테이블과 그렇지 않는 테이블을 나눈다. 하나라도 빠지는 테이블을 구할때에는 이전에 하나라도 빠진 테이블에서의 최대값과, 현재 값을 제외한 누적합 중의 최대값을 선택하면 최대 하나가 빠지는 값의 최대 누적합을 구할 수 있다. 점화식은 아래와 같이 표현 할 수 있습니다. dp[0] 테이블은 일반적인 누적합의 최대값이고 dp[1] 테이블이 최대 하나가 빠지는 누적합 테이..
[백준] 1256번 : 사전 1256번: 사전 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 🤔 문제분석 해당문제는 다이나믹 프로그래밍을 역추적 하는 방법으로 문제를 해결 할 수 있습니다. 경우의 수 점화식은 아래와 같이 만들 수 있습니다. 앞에 ‘a’ 가 추가된경우, 앞에 ‘z’가 추가된경우를 둘다 더한값입니다. 여기서 알 수 있는것은 dp[N-1][M]은 ‘a’를 앞에 추가한 것 이고, dp[N][M-1]은 ‘z’를 추가한 것 입니다. dp[N][M] = dp[N-1][M] + dp[N][M-1] 따라서 재귀 함수를 아래와 같이 선언 할 수 ..

티스토리툴바