본문 바로가기

전체 글292

백준 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.
Docker 이미지 제어, 기본으로 알아야하는 명령과 옵션 Docker 이미지 제어 이 글에서는 Docker 이미지 제어하는데 필수로 알아야할 기본적인 명령과 옵션들을 소개한다. 원하는 프로그램을 실행시키기 위해서는 컨테이너를 생성해야한다. 이런 컨테이너를 생성하기 위해서는 이미지가 필요하다. Docker에서 이미지는 컨테이너를 생성하는데 있어서 사용되는 Base, 설계도, 틀이 된다. Java와 같은 프로그래밍 언어를 사용해보셨다면 클래스와 객체의 관계와 비슷하다. Docker CLI command [DevOps/Docker] - [Docker] Ubuntu 도커 설치 [DevOps/Docker] - [Docker] CentOS 도커 설치 [DevOps/Docker] - [Docker] Windows 도커 설치 Docker를 설치했다면 Docker CLI co.. 2021. 10. 6.