Python/백준 문제풀이

나는 이 문제를 DP 알고리즘 중 Tabulation(상향식)을 이용해서 풀었다. DP에 대해 간단히 설명을 하자면 Tablulation(상향식)과 Memoization(하향식)이 있다. Tabulation은 우리가 흔히 아는 DP 알고리즘이다. 중복된 값은 계산하지 않으며 이전에 계산한 값을 바탕으로 새로운 값을 계산한다. 피보나치수열을 예시로 들 수 있다. f[i] = f [i-1] + f [i-2]에서 볼 수 있듯이 이전에 계산한 값을 바탕으로 새로운 값을 계산하는 방법이다. Memoization은 결과값에 접근하려는 시도를 하고, 해당 값에 가까운 값을 DP에서 찾아나가며 탑 다운의 형태로 중복된 값을 사용하거나 메모하는 형태를 띤다. https://www.acmicpc.net/problem/92..

전형적인 큐 문제다. 슬라이딩 윈도우 방법으로 풀 수도 있지만 deque를 블로그에서 설명한 적이 있어서 큐로 설명하겠다! https://solution-is-here.tistory.com/117 백준(G5) 5430번: AC (파이썬, Python3) 및 deque 설명 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 파 solution-is-here.tistory.com deque를 잘 모르시는 분이 계시면 위 글을 보고 오셔야 합니다! deque를 안다고 가정하고 문제를 설명하겠습니다. http..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬 알고리즘을 알고 이 문제를 풀면 완벽히 이해할 수 있다. https://solution-is-here.tistory.com/124 [알고리즘] 위상정렬(topological sorting) 파이썬으로 마스터 하기 위상정렬은 순서가 정해져 있는 작업을 수행할 때 차례대로 수행할 수 있도록 도와주는 정렬 알고리즘의 일종입니다. 위상정렬의 수행과정은 ..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 스택과 그리디 알고리즘을 섞은 문제다. 첫째 줄에 N과 K가 주어지고, 둘째 줄에는 N자리 숫자가 주어진다. N자리 숫자에서 K개의 숫자를 지워서 가장 큰 수를 만드는 것이 이 문제다. 입력과 출력을 비교했을때 앞에 있는 작은 수들을 지워야 숫자가 커지는 것을 알 수가 있다. 나는 리스트를 하나 만들어서 숫자를 넣은 뒤, 뒤에 있는 숫자와 비교해서 더 작으면 제거하는 방식으로 접근했다. 코드와 함께 설명하겠다. 1 2 3 4 5 for n in mission_nu..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 이 문제는 전형적인 그리디 알고리즘 문제다. 그리디 알고리즘은 선택의 순간마다 당장의 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 최적값을 구하는데 사용되는 방법이다. 문제에서는 수를 적절히 묶어 최대 값이 나오게 하는 것이 최적 값이다. 보통 이런 문제는 첫째 줄에 수열의 크기가 주어진다. 둘째 줄부터는 n개의 수가 주어진다. 우리는 이 문제를 풀때 몇 가지 상황을 ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 이 문제는 이렇게 쉽다고?? 이런 생각이 들었던 문제 같다. 첫째 줄에 카드의 개수가 주어진다. 둘째 줄부터는 카드가 주어진다. ex) 카드가 10,20,40 이렇게 주어지면 (10 + 20) + (30 + 40) 이렇게 계산을 한다. 이것을 보고 카드를 오름차순으로 정렬을 하고 리스트를 하나 만든 뒤, 더한 값을 리스트에 추가할 생각을 했다. 1 2 3 4 heap = [] num..