본문 바로가기

CS33

파이썬 행렬 곱셈, 거듭제곱 구하기 파이썬 행렬 알고리즘 문제를 풀 때 시간 복잡도를 줄이기 위해 행렬의 거듭제곱을 사용하는 경우가 있습니다. 대표적으로 피보나치 수열의 가장 빠른 시간 복잡도가 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.

백준 1932 파이썬 - 정수삼각형 - 동적 계획법 백준 1932 파이썬 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 가장 상단에서 좌우로만 이동하면서 수의 합이 최대가 되는 경로의 최종 합을 구하는 문제입니다. 해당 문제는 양쪽 끝의 숫자를 제외하고 이전 층에서 인덱스... i-1과 i의 위치를 더한 값을 캐시값으로 저장해서 가장 마지막 층의 최대값을 구하면 된다. 위의 예시에서 메모이제이션을 통해 최종적으로 얻는 캐시값은 아래와 같을 것이다. Python 풀이 1 import sys read = sys.stdin.readline n = int(read()) c.. 2021. 10. 10.

백준 1149 파이썬 - RGB거리 - 동적 계획법 백준 1149 파이썬 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이번 문제는 2차원 배열에서 앞뒤로 인덱스 번호가 다르게해서 합산한게 가장 적은 값을 구하는 문제이다.이런 최소나 최대값을 구하는 문제는 가장 먼저 동적 계획법이 떠오른다. 그런데... 만약... 가장 적은 비용만 저장하겠다는 생각에 중점을 두면... 아래와 같은 예외사항이 발생할 수 있다. 이전에 가장 적은 비용만 고려하면.... 위와 같이 비용이 같은.. 2021. 10. 10.

백준 9461 파이썬 - 파도반 수열 - 동적 계획법 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 피보나치와 비슷하게 규칙이 있는 파도반 수열의 N번째 값을 구하는 알고리즘 문제입니다. 위의 그림을 보면 알 수 있듯이... 정삼각형의 변을 따라 계속 늘려가는데... 정삼각형의 변의 길이가 수열의 값으로 들어간다. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16... 가장 핵심은 파도반 수열의 규칙을 찾는 것이었습니다. 위의 규칙을 기반으로 하고 있습니다. 근데 조건으로 n이 8보다.. 2021. 10. 8.

백준 1904 파이썬 - 01타일 - 동적 계획법, 행렬 백준 1904 파이썬 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 해당 문제는... "00" 타일과 "1" 타일로 만들 수 있는 이진수의 가짓수를 찾는 문제입니다. 이 문제도 결국 1타일과 00타일을 이전의 타입에 붙치는 문제이므로 메모이제이션을 이용한 동적계획법으로 풀 수 있다. 그런데... 직접 손으로 숫자의 패턴을 계산해보니 피보나치 수열과 완젼 동일한 숫자의 패턴을 갖고 있었습니다. 그래서 이 문제는 행렬 멱법을 사용해서 해결할 수 있었습.. 2021. 10. 8.

피보나치 파이썬으로 구하는 3가지 알고리즘 피보나치 파이썬 3가지 알고리즘 피보나치 수열은 아래의 수식은 만족하는 수열입니다. 바로 이전 숫자와 그 전 숫자의 합을 연속해서 구하는 수열이고 아래와 같이 진행됩니다. 이번 글에서는 시간 복잡도에 따른 피보나치 수열을 구하는 대표적인 3가지 알고리즘에 대해서 알아보도록 하겠습니다. 재귀함수 이용 - 시간복잡도 O(n^2) 동적 계획법 이용 - 시간복잡도 O(n) 행렬 멱법 이용 - 시간복잡도 O(log n) 재귀함수 이용 첫번 째 방법은 재귀함수를 이용하는 방법입니다. def fibo(n): if n in (1,2): return 1 return fibo(n-1) + fibo(n-2) print(fibo(8)) 가장 간단한 방법이지만... 재귀로 두개의 분기가 계속해서 생기기 때문에 시간복잡도가 O(.. 2021. 10. 8.

백준 9184 파이썬 - 신나는 함수 실행 - 동적 계획법 백준 9184 파이썬 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제에서 위와 같은 조건의 재귀함수가 주어지는데... 해당 재귀를 그대로 실행하면 값을 구하는데 너무 오래 걸린다고 한다. 동적 계획법의 기원? 동적 계획법이란 알고리즘이 생겨나게 된 배경이... 분할정복에서 작업들을 쪼개서 할 때 중복되서 하는 작업이 많은 문제를 해결하기 위해 만들어졌다고 합니다. 그래서 재귀함수와 같이 뎁스를 타고 내려가서 값을 구할 때... 계산한 값을 중.. 2021. 10. 7.

백준 1003 파이썬 - 피보나치 함수 - 동적 계획법 백준 1003 파이썬 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 재귀를 통한 피보나치를 구하고 0과 1까지 내려갔을 때 0과 1을 출력해주는 함수가 주어진다. 이때 0과 1을 출력한 횟수를 구하는 알고리즘 문제이다. 피보나치 수열을 재귀로 주로 구현하는데... 동적 계획법으로도 충분히 가능하다. 특히 이번 문제에서는 출력되는 결과를 구하는 것이기 때문에.... 숫자 N에대해서 N-1과 N-2 번째에 출력한 0과 1의 수를 합산하면 결과를 얻을 수 있다. Python 풀이 import sys read = sys.stdin.readline.. 2021. 10. 7.

백준 9095 파이썬 - 1,2,3 더하기 - 동적 계획법, DFS 백준 9095 파이썬 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 알고리즘 문제입니다. 단, 위치의 중복까지 가능한 조건입니다. 예를 들어 4라는 정수를 만들 때 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 이렇게 위치의 중복까지 가능한 조건 입니다. 이 문제는 동적 계획법을 공부하기 위해 풀은 문제인데요... 문제를 해결하는 방법을 고민해 보면서 DFS를 사용하고 싶다는 생각이 많이 들었어요. 순열이나 조합을 구할 때 DFS를 사용해서 .. 2021. 10. 7.

백준 1463 파이썬 - 1로 만들기 - 동적 계획법 백준 1463 파이썬 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X가 주어졌을 때 3으로 나누어 떨어지면 3으로 나누고 2로 나누어 떨어지면 2로 나누고 그 이외는 1을 뺀다. 해당 규칙에 맞춰서 연산 횟수의 최솟값을 구하는 문제이다. 문제를 보고 딱 생각이 난 알고리즘이 동적 계획법이었습니다. 초기값으로 설정할 값이 명확했고 기존에 연산된 값을 재사용하는 메모이제이션이 딱 맞아 떨어졌다. Python 풀이 1 import sys read = sys.stdin.readline N = int(read()) cache = [-1] * (N+3) cac.. 2021. 10. 6.

PKI 란? 공개키 기반 구조 개념 PKI(Public Key Infrastructure) PKI 공개키 기반 구조에 대해서 굉장히 어렵게 설명이 되어 있는 경우가 많아 쉽게 이해할 수 있도록 정리할 겸 글을 작성합니다. 공개키 암호화와 전자서명을 사용할 수 있게 기반을 마련해둔 것이 PKI(Public Key Infrastructure)이다. 이전 글에서 [CS/보안] - 대칭키 / 비대칭키 양방향 암호화 기법 방법에 대해서는 알아봤습니다. 이런 공개키 암호화를 쉽게 사용할 수 있도록 기반을 마련하는게 PKI인데... 이런 기반? 인프라?를 구축하기 위해서 CA라는 개념이 등장하게 됩니다. 공개키 암호화에서 개인키는 오로지 개인이 소유하고 있어야 합니다. 반면 공개키의 경우 다른 사람들도 사용을 해야하는데... 이것을 어떻게 구할 수 있.. 2021. 10. 6.

이전 1 2 다음

티스토리툴바