프로그래밍
백준 10815: 숫자카드 해설- python
✏️ 문제 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 풀이 1920 수찾기 문제와 완전하게 동일한 문제였다. 해당 문제의 해설과 이진탐색에 대한 설명은 여기를 참고 (Python) N=int(input()) card=list(map(int,input().split())) card=sorted(card) M=int(input()) target_list=list(map(int,input().split())) def BS(array, target, start, end): if..
Binary Search (이진탐색) 알고리즘
✏️ 이진탐색알고리즘의 작동방식 이진탐색은 정렬된 리스트에서 특정 요소를 찾는 알고리즘이다. 분할(Devide) 리스트를 중간값을 기준으로 두개의 리스트로 분할한다. 정복(Conquer) - 검색할 숫자 중간값 이면 중간값 뒤의 리스트에서 검색할 요소를 찾는다. - 검색할 숫자 == 중간값 이면 값을 리턴한다. ✏️ 이진탐색알고리즘 구현 (Python) 재귀적 구현 def BS(array, target, start, end): if start>end: return None mid=(start+end)//2 if array[mid]==target: return mid elif array[mid]>target: return B..
백준 11053: 가장 긴 증가하는 부분 수열 해설- python
✏️ 문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✏️ 풀이 LIS(Longest Increasing Subsequence)라는 유명한 DP문제이다.만약 A={6, 2, 5, 1, 7, 4, 8, 3} 가 있을때 LIS는 {2, 5, 7, 8}이 된다. 증가하는 수열은 {2, 5}, {2, 7} 등 많지만 그 중 가장 긴 것이 LIS가 된다. - dp[i]를 전부 1로 초기화했다. LIS의 길이는 기본적으로 1은 될 것이기 ..
백준 2579: 계단오르기 해설- python
✏️ 문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ✏️ 풀이 케이스는 두가지로 분리된다. 이전에 두 계단을 연속으로 오른 경우. 그리고 3계단 이전에는 두계단을 오르고 바로 이전에서 현지점까지 연속으로 올라오는 경우. 본 문제에서는 리스트를 두개 만들었다. i번째 계단까지 최대값을 저장하는 dp[] & 문제에서 준 계단점수를 저장하는 arr[] 이를 점화식으로 나타내보면 아래와 같을 것이다. 1. dp[i-2] + arr[i] 2. dp[i-3] + arr[i-1] + arr[i] n=int(input()) ar..
백준 2748번 런타임에러(IndexError)
2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 이건 글 쓸 생각 없었는데 현타가 와서 글을 남긴다. 나같은 사람이 어딘가에 또 있을거라 생각하고 도움이 되고자한다. DP로 간단하게 코드를 적고 제출버튼을 딱 눌렀더니 런타임에러가 떴다. n=int(input()) dp=[0]*(n+1) dp[1]=1 dp[2]=1 dp[3]=2 for i in range(4,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]) 왜 일까 한참을 고민하고보니 3이하의 수를 ..
백준 9095: 1, 2, 3 더하기 해설- python
✏️ 문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✏️ 풀이 늘 그렇듯 규칙을 찾아보자. n=1 일 때, 1n=2 일 때, 1+1, 2n=3 일 때, 1+1+1, 1+2, 2+1, 3n=4 일 때, 1+1+1+1, 1+3, 3+1, 4....어? 이거다. 1+3은 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3). 아까 n=3일 때 해결한 문제를 내포하고 있다.즉 n이 3보다 커지면 그 문제들은 n=1,2,3일 때의 문제를 포함하고 있다.즉 작은 문제(n=1,2,3)를 이용해 큰 문제를 해결하는 동적계획법(Dynamic Programming)을 이용하면 적합하겠다. [Python & A..
백준 11727: 2xn 타일링(2) 해설- python
✏️ 문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ✏️ 풀이 2xn 타일링 문제에서 2x2타일이 추가된 형태의 문제로 점화식만 살짝 수정해주면 된다. 2xn 타일링 문제는 아래에서 다시 풀어보자 백준 11726: 2xn 타일링 해설- python ✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acm duckracoon.tistory.com 이전의 문제에서는 점화식이 c..
백준 11726: 2xn 타일링 해설- python
✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ✏️ 풀이 뭘 어쩔지 모를땐 늘 그렇듯 규칙을 찾아보자. 모든 경우의 수를 한번 생각해보았다. n=1 > size 1 : 1개 n=2 > size 1: 2개 || size 2: 1개 n=3 > size 1: 3개 || size 1: 1개 + size 2: 2개 || size 1: 2개 + size 2: 1개 n=4 > size 1: 4개 || size 1: 2개 + size 2: 2개(L) || size 1: 2개 + size 2: 2개(R) || size 1: 1개 + s..
백준 1463: 1로 만들기 해설- python
✏️ 문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ✏️ 풀이 해당 풀이는 주로 동적계획법 (Dynamic Programming) 을 이용하는 것 같다. 동적계획법에 대한 설명은 아래글을 참고하자. [Python & Algorithm] Dynamic Programming(동적프로그래밍) ✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나 duckracoon.tistory.com 어떻게 시작해야할지 잘 모르겠으니 나는 임의의 X를 가지고 수가 어떻게 변하는지를..
![[Python & Algorithm] Dynamic Programming(동적프로그래밍)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FCOwER%2FbtrrpT1LhQE%2FFZvGVxtmqQdonWjMmTMkR1%2Fimg.jpg)
[Python & Algorithm] Dynamic Programming(동적프로그래밍)
✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나는지 아닌지' 에 차이가 있다. 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어서 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 하지만 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 문제를 풀어낸다. 2) 다이나믹 프로그래밍의 방법 모든 작은 문제들은 한번만 풀어낸다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 3) 다이나믹..