본문 바로가기

CS/알고리즘29

파이썬 행렬 곱셈, 거듭제곱 구하기 파이썬 행렬 알고리즘 문제를 풀 때 시간 복잡도를 줄이기 위해 행렬의 거듭제곱을 사용하는 경우가 있습니다. 대표적으로 피보나치 수열의 가장 빠른 시간 복잡도가 O(LogN)이 행렬로 구현할 수 있습니다. 피보나치와 행렬에 대한 내용은 자세한 내용은 아래 링크를 참조해주세요. [CS/알고리즘] - 피보나치 파이썬으로 구하는 3가지 알고리즘 피보나치 파이썬으로 구하는 3가지 알고리즘 피보나치 파이썬 3가지 알고리즘 피보나치 수열은 아래의 수식은 만족하는 수열입니다. 바로 이전 숫자와 그 전 숫자의 합을 연속해서 구하는 수열이고 아래와 같이 진행됩니다. 이번 글에서는 myjamong.tistory.com 이렇게 가끔씩 행렬의 곱셈을 사용하는데... 이게 자주 사용하지 않는 3개의 중첩된 for문을 사용하다보니.. 2021. 10. 21.
백준 12865 파이썬 - 평범한 배낭 - 동적 계획법 백준 12865 파이썬 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이번 문제는 가방에 들어갈 수 있는 최대 무게가 정해져 있을 때 넣을 수 있는 물건의 최대 가치를 구하는 문제이다. 일단 최대값을 구하는 문제이기 때문에 가장 먼저 동적 계획법이 떠올랐습니다. 메모이제이션으로 사용할 값을 가방에 들어가는 무게를 중점으로 두고 물건을 확인할 때 가방의 최대 무게부터 물건의 무게.. 2021. 10. 21.
백준 1912 파이썬 - 연속합 - 동적 계획법 백준 1912 파이썬 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 10 -4 -3 1 5 6 -35 12 21 -1 = 33 2 1 -4 3 4 -4 6 5 -5 1 = 14 위의 예시와 같이 연속되는 합의 최대값을 구하는 문제이다. 이 문제에서 현재의 위치가 음수이고 이 음수를 이전까지의 연속된 합에 합했을 때 0보다 큰지 확인하는 것이 핵심이다. 합했는데 0보다 작은 경우.. 최대값이 이어갈 수 없다. 반대로... 합했는데 0보다 큰 수가 나오면... 2021. 10. 19.
백준 9251 파이썬 - LCS - 동적 계획법 백준 9251 파이썬 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이번 문제는 두개의 문자열이 주어졌을 때 LCS(Longest Common Subsequence, 최장 공통 부분 수열)를 구하는 문제다. 예를 들어 ACAYKP CAPCAK LCS는 ACAK 이다. 이전에 풀었던 동적 계획법이랑은 조금 다르게 2차원 배열의 캐시를 만들어서 해결할 수 있고... 누적 값을 구해서 해결할 수도 있다... 2021. 10. 18.
백준 2565 파이썬 - 전깃줄 - 동적 계획법, LIS 백준 2565 파이썬 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 이번 문제는 전깃줄이 서로 교차하지 않게 없애야하는 전깃줄의 최소 개수를 구하는 문제이다. 처음에 문제를 어떻게 접근해야할지 모르겠다고 생각했는데... 역시 알고리즘은 종이에 적어가면서 경우의 수를 찾다보니 규칙을 찾았습니다. 이 문제도 이전에 풀었던 LIS 문제 : [CS/알고리즘] - 백준 11053 파이썬 - 가장 긴 증가하는 부분 수열 - 동적 계획법, LIS 의 연장선 응용.. 2021. 10. 15.
백준 11054 파이썬 - 가장 긴 바이토닉 부분 수열 - 동적 계획법, LIS 백준 11054 파이썬 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이번 문제는 이전에 풀었던 [CS/알고리즘] - 백준 11053 파이썬 - 가장 긴 증가하는 부분 수열 - 동적 계획법, LIS 문제의 응용이다. 바이토닉 부분 수열을 가장 긴 증가하고 감소하는 부분 수열이다. 즉 이전에 풀었던 LIS 문제에서 배열의 각 위치에서의 최대 증가하는 부분 수열을 주어진 배열과 주어진 배열을 뒤집은 배열 2가지를 구해서 해결할 수 있다. Python 풀이 impor.. 2021. 10. 15.
백준 11053 파이썬 - 가장 긴 증가하는 부분 수열 - 동적 계획법, LIS 백준 11053 파이썬 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이번 문제는 수열의 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. LIS(Longest Increasing Subsequence)라고 한다. A라는 수열 {10, 20, 10, 30, 20, 50}이 있다면 {10, 20, 10, 30, 20, 50}이 가장 긴 부분 수열이다. 이번 문제.. 2021. 10. 13.
백준 2156 파이썬 - 포도주 시식 - 동적 계획법 백준 2156 파이썬 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 해당 문제는 주어진 조건에 의해 가장 많은 양의 포도주를 시식하는 방법을 구하는 문제입니다. 포도주의 잔을 선택하면 모두 마셔야한다. 연속으로 놓여 있는 3잔을 모두 마실 수 없다. [CS/알고리즘] - 백준 2579 파이썬 - 계단 오르기 - 동적 계획법 문제와 유사한 문제인데 차이가 있다면 가장 마지막 잔을 꼭 마시지 않아도 된다는 것입니다. 즉, 최대값을 구할 때 조건이 .. 2021. 10. 10.
백준 10844 파이썬 - 쉬운 계단 수 - 동적 계획법 백준 10844 파이썬 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제는 계단 수를 구하는 문제이다. 계단 수는 "45656" 처럼 숫자의 자릿수 마다 하나 씩 줄고 늘어나는 수를 말한다. 0으로 시작할 수 없으며 90은 계단 수가 아니다. 이런 조건으로 아래와 같은 규칙이 만들어 진다. 0 다음에는 1만 올 수 있다. 9 다음에는 8만 올 수 있다. 나머지 숫자에 대해서는 앞뒤 모두 올 수 있다. 동적 계획법으로 숫자의 길이에 따라 만들 수 있는 숫자의 갯수를 저장하는데... 각 숫자의 끝자리를 기준으로 기억할 수 있는 메모이제이션 리스트를 생성.. 2021. 10. 10.
백준 2579 파이썬 - 계단 오르기 - 동적 계획법 백준 2579 파이썬 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이번 문제는 조건에 맞춰서 계단을 오르면서 최대값을 구하는 문제입니다. 계단은 한번에 1~2 계단씩 오를 수 있다. 시작점은 포함하지 않고... 연속된 3개의 계단은 밟을 수 없다. 즉, 최대 2개 계단까지 연속으로 밟을 수 있다. 마지막 계단에는 반듯이 도착해야한다. 동적 계획법을 사용하면 현재 위치의 최대값을 저장하면서 가기 때문에... 3번 째 조건은 크게 걱정할 것 없고... 문제.. 2021. 10. 10.

티스토리툴바