[Python/파이썬] 백준 15989번: 1, 2, 3 더하기 4

문제 풀이 1. 모든 정수(n)는 1만 써서 구할 수 있다. n 경우의 수 0 없음 1 1 2 1 + 1 3 1 + 1 + 1 4 1 + 1 + 1 + 1 5 1 + 1 + 1 + 1 + 1 1의 합으로 정수 n을 나타내는 방법은 1가지 이므로 dp를 전부 1로 초기화한다. dp = [1] * 10001 2. 1, 2의 합으로 정수 n을 나타내는 방법은 (n - 2)를 1의 합만으로 나타낸 방법에 2를 더해주면 된다. n 경우의 수 0 (없음) 1 1 2 1 + 1, (없음) + 2 3 1 + 1 + 1, 1 + 2 4 1 + 1 + 1 + 1, 1 + 1 + 2 5 1 + 1 + 1 +1 + 1, 1 + 1 + 1 + 2 3. 1, 2, 3의 합으로 정수 n을 나타내는 방법은 (n - 3)을 1, 2의..

[Python/파이썬] 백준 1644번: 소수의 연속합

문제 풀이 에라토스테네스의 체, 두 포인터를 사용해 풀면 된다. 구간 합은 선택사항..ㅎㅎ 나동빈님의 강의에 전부 정리되어있다. https://www.youtube.com/watch?v=cswJ1h-How0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9 코드 import sys, math input = sys.stdin.readline n = int(input()) intervalSum = [0] isPrimeList = [True for _ in range(n + 1)] for i in range(2, int(math.sqrt(n)) + 1): if isPrimeList[i]: for j in range(i * 2, n + 1, i): isPrimeList[j] ..

[Python/파이썬] 백준 1781번: 컵라면

문제 풀이 1. 데드라인을 기준으로 오름차순 정렬 문제 배열 데드라인 1 1 2 2 3 3 6 컵라면 7 6 4 5 1 2 1 2. 우선순위 큐에 첫 번째 문제를 넣는다. 우선순위 큐 날짜 1일 2일 3일 4일 5일 데드라인 1 컵라면 7 1일 차, 1문제 우선순위 큐에 문제를 삽입 = 해당 문제를 품 만약 우선순위 큐에 2개의 문제를 삽입했다면, 2일이 지난 셈이다. (한 문제당 하루가 걸리므로) 3. 우선순위 큐에 두 번째 문제를 삽입 우선순위 큐 날짜 1일 2일 3일 4일 5일 데드라인 1 1 컵라면 6 7 2일 차, 2문제 2일차일 때 데드라인이 1일까지인 문제는 풀 수 없다! 또한 동호는 마지막에 삽입된 데드라인보다 많은 문제를 풀 수 없다. 따라서 마지막에 삽입된 문제의 데드라인 < 현재 날짜..

[Python/파이썬] 백준 1202번: 보석 도둑

문제 풀이 가방과 보석을 정렬한 후, 각 가방에 넣을 수 있는 보석 가격의 최대 값을 구한다. 1. 초기 값 보석 무게 1 2 5 가격 65 99 23 가방 무게 2 10 소유한 보석의 가격 0 0 2. 첫 번째 가방(2)에 들어갈 수 있는 보석을 우선순위 큐에 저장 보석 무게 5 가격 23 (배열 보석에서 무게가 1, 2인 값을 빼내어 우선순위 큐에 저장함) 우선순위 큐 (기준 : 가격) 무게 2 1 가격 99 65 (첫 번째 가방의 무게는 2이고, 2보다 작은 보석들을 우선순위 큐에 넣음) 가방 무게 2 10 소유한 보석의 가격 99 0 (가장 큰 값인 99를 가방(2)에 추가) 우선순위 큐 (기준 : 가격), 첫 번재 가방에 가격이 99인 보석을 넣어줬으므로 pop 무게 1 가격 65 3. 남은 보..

[Python/파이썬] 백준 1208번: 부분수열의 합 2

문제 풀이 1. 주어진 수열을 절반으로 나눈다. [-7, -3, -2, 5, 8] -> [-7, -3], [-2, 5, 8] 2. 나눠진 수열의 부분 수열을 구한다. A : [-7, -3] -> [-7], [-3], [-7, -3] B : [-2, 5, 8] -> [-2], [5], [8], [-2, 5], [-2, 8], [5, 8], [-2, 5, 8] 3. A의 부분 수열 중 하나를 선택하고, B의 부분 수열 중 하나를 선택하면 모든 부분 수열을 구할 수 있다. ex) [-7, -3, 5] = [-7, -3] + [5] 4. A, B 부분 수열의 합을 배열에 저장한다. sumA : [-7, -3, -10] sumB : [-2, 3, 5, 6, 8, 11, 13] 5. sumA, sumB 그리고 su..

[Python/파이썬] 백준 15732번: 도토리 숨기기

문제 풀이 입력이 다음과 같을 때, 200 2 5 100 150 10 110 150 15 상자의 번호는 0 ~ 200까지 있다. 우선 중간 값(100)을 구하고, 0번 상자에서 100번 상자까지의 도토리 개수를 구한다. 도토리 개수에 따라 이분 탐색을 수행하면 된다. 코드 import sys input = sys.stdin.readline #도토리 수 구하기 def calAcorn(rules, boxNum): cnt = 0 for start, end, margin in rules: if boxNum < start: continue end = min(boxNum, end) cnt += (end - start) // margin + 1 return cnt def binarySearch(rules, end, ..

[Python/파이썬] 백준 10942번: 팰린드롬?

문제 풀이 dp[i][j] : i ~ j까지의 수열이 팰린드롬인지 저장 ex) dp[1][3] = True : 1 ~ 3까지의 수열이 팰린드롬 수 arr 배열에 전체 수열 저장 1. 원소가 하나인 경우 무조건 팰린드롬 수 dp[0][0], dp[1][1], ... dp[n][n] = True 2. arr[i] == arr[i+1]인 경우 팰린드롬 수 (부분 수열의 길이가 2이고, 원소가 동일한 경우) ex) 11, 22, 33, 44 는 팰린드롬 수 3. a~b까지의 수열에서 arr[a] == arr[b]이고 그 사이의 수열이 팰린드롬인 경우 원소가 4개인 경우, 5개인 경우 ... 반복하면 된다. 코드 import sys input = sys.stdin.readline n = int(input()) a..

[Python/파이썬] 백준 1695번: 팰린드롬 만들기 / 파이썬 메모리초과 해결

문제 풀이 1. 주어진 수열에서 팰린드롬 수열을 구한다. 12342의 부분 수열 중 팰린드롬은 242(12342)이다. 2. 팰린드롬의 정 가운데를 기준으로 수열을 나눈다. 123 4 2 3. 팰린드롬이 아닌 수를 반대편에 추가한다. 123 4 321 수열에서 이미 팰린드롬인 수열을 구했고, 팰린드롬이 아닌 수만 추가하면 되므로 최적의 알고리즘이다. 또다른 예시 팰린드롬을 찾는 과정에서 DP가 이용된다. [수열 A] 12342 [수열 A를 뒤집은 수열 B] 24321 이 있다고 가정해보자. 수열 A와 수열 B의 최장 공통 부분 수열(LCS)이 곧 팰린드롬 수열이다. (수열 A를 뒤집었을 때의 부분 수열 = 수열 A의 부분 수열 이므로, 팰린드롬 수열의 조건을 생각해봐라) 말로 설명하기가 참 어렵다... ..

[Python/파이썬] 백준 17404번: RGB거리 2

문제 풀이 첫 번째 집의 색을 R로 선택하고 DP를 통해 최솟값을 구한다. G, B에 대해 반복 코드 import sys input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] def minPaint(selHouse): dp = [[0] * 3 for _ in range(n)] dp[0] = arr[0] for i in range(3): if i == selHouse: dp[1][i] = 1e9 continue dp[1][i] = arr[1][i] + arr[0][selHouse] for i in range(2, n): dp[i][0] = min(dp[i - 1][1], dp[i..

[Python/파이썬] 백준 14942번: 개미

문제 풀이 1. 주어진 입력은 양방향 간선이므로 단방향 간선으로 만들어줘야함 2. 희소배열 사용 https://hello-capo.netlify.app/algorithm-sparse-table/ 🧩 [Algorithm] 희소 배열(Sparse Table) 알고리즘 | hello-capo! 희소 배열(Sparse Table) 배열 원소의 개수가 무조건 배열의 length 값보다 작은 배열 데이터가 저장되지 않은 경우가 더 많은 희소 행렬과 같이, 희소 배열은 배열의 원소 위치가 연속적이지 않은 배 hello-capo.netlify.app 3. LCA와 유사하게 노드 탐색 https://cyberflower.github.io/2019/07/22/LCA.html LCA(Least Common Ancestor)..