알고리즘 (30) 썸네일형 리스트형 [Python] 백준 2531 : 회전 초밥 www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 방법 문제 이해 : 초밥을 k개 연속으로 먹었을 때 먹을 수 있는 최대 종류를 구하는 것이다. left부터 right까지 먹을 때, 먹을 수 있는 초밥의 종류를 canEat이라는 딕셔너리에 저장한다. 먹을 수 있는 초밥의 종류의 개수는 cnt에 저장한다. '회전' 초밥이기 때문에 0~k까지 뿐만아니라 n-1~k-1까지 순환할 수 있음을 잊으면 안된다. -> right.. [DP] 가장 긴 증가하는 부분 수열(LIS)의 구현 방법, 활용 백준 문제 모음 가장 긴 증가하는 부분 수열 LIS의 구현 방법 LIS의 구현 방법에는 기본 DP를 활용하는 방법과 Binary Search를 활용하는 방법이 있다. 만약 N이 O(N^2)로 처리할 경우 시간 초과가 날 만큼 크다면 반드시 Binary Search를 이용해서 풀어야 한다. 1. DP로만 풀이 n = int(input()) array = list(map(int, input().split())) dp = [1 for _ in range(n)] for i in range(1,n): for j in range(i): if array[j] < array[i]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) 2. Binary Search로 풀이 import bisect n = int(.. [Python] 백준 1700 멀티탭 스케줄링 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 방법 반복문으로 전기용품을 하나씩 방문하면서 플러그를 빼야하는지 안 빼도 되는지 체크한다. 플러그가 N개 이하로 꽂혀있거나, 현재 확인하려는 전기용품이 이미 꽂혀있다면 뽑지 않아도 된다. 뽑아야할 때, 꽂혀있는 플러그 중에서 이후 가장 나중에 사용되는 전기용품 또는 이후 사용되지 않는 전기용품을 먼저 뽑는다. N과 K모두 100이하 이므로 시간초과에 대해서 생각하지 않아도 된다. 전체 코드 n, k = map(int, input().split()) arr .. [Python] 백트래킹 구현 방법, 관련 문제 모음 백준 백트래킹 문제 모음 9663 N-Queen https://www.acmicpc.net/problem/9663 15686 치킨배달 https://www.acmicpc.net/problem/15686 2580 스도쿠 https://www.acmicpc.net/problem/2580 1062 가르침 https://www.acmicpc.net/problem/1062 1759 암호 만들기 https://www.acmicpc.net/problem/1759 백트래킹 특징 재귀를 이용해야 한다. 반복문이 가지 뻗듯이 많이 생길 것 같은 문제 백트래킹 풀이 방법 재귀 함수의 종료 시점 부터 지정한다. 대체로 종료 시점 지정 후 for문이 등장한다. for문 안에 각각의 경우에 대해 값을 바꿔가며 재귀함수를 호출한다.. [Python] 파이썬 다이나믹(동적) 프로그래밍 구현, 관련 문제 모음 🚜 Dynamic Programming을 사용하는 문제 Dynamic Programming은 입력 크기가 작은 부분 문제 해결 후, 해당 부분의 해를 이용해서 보다 큰 문제를 해결하는 방법입니다. memorization 기법(이전 실행에서 구한 해를 저장해둠)을 사용합니다. 아래는 가장 기본적인 dp 문제 리스트 입니다. 평범한 배낭 (백준 12865) 가장 긴 증가하는 부분 수열 (백준 11053) LCS, 두 수열에서 공통된 가장 긴 수열의 길이 구하기 (백준 9251) 기타리스트 (백준 1495) 가장 높은 탑 쌓기 (백준 2655) 프로그래머스 level2. 가장 큰 정사각형 찾기 🚚 풀이 방법 특징 ✅ 사용되는 문제 유형 : 작은 값부터 구할 수 있는 문제. 즉, 값을 하나하나 쌓거나 채워가는 .. [Python] 백준 3955 캔디 분배 (확장 유클리드 알고리즘) 백준 3955 캔디 분배 🍏 유클리드 호제법 설계 C : 한 봉지의 사탕 개수, K : 사람 수 x = 1 인당 먹을 사탕 개수 y = 구매해야할 사탕 개수 Kx + 1 = Cy 를 만족하는 y를 찾는 것이다. 확장 유클리드 호제법에 맞게 식을 수정하면, Cy - Kx = 1 을 만족하는 y를 찾는 것이다. 유클리드 호제법에서 a = C, b = -K, 1 = g이다. 🍍 예외 처리 g = 1 이어야 하기 때문에 gcd(C, K) == 1 이어야 한다. K와 C의 gcd가 1이 아니라면 IMPOSSIBLE 구한 y가 10^9보다 크면 IMPOSSIBLE C == 1 일 때, 사탕 한 봉지에 사탕 한 개만 들었으니까 사람수 + 1만큼 사탕을 사면 된다. 따라서 답은 K+1 이고, K+1 > 10^9라면 I.. 이전 1 2 3 4 다음
