앞선 코테에서 생각 이상으로 다이나믹 프로그래밍이 까다롭고 출제도 자주 된다는 것을 알게 되어 다이나믹 프로그래밍 문제를 열심히 준비하고 있다. 그런데 이전에 풀었던 풀이마저도 가물가물해서 복습도 병행하고 있다. https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 여기서는 어떻게 비용과 확보할 수 있는 메모리를 어떻게 연관짓느냐가 쟁점이다. 이럴 때는 인덱스로 메모이제이션되는 값에 접근하는데, 인덱스를 어떤 걸로 삼아야하는지를 결정하면 된다. 이전의 비용..

https://www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려 www.acmicpc.net 그동안 접했던 다이나믹 프로그래밍보다 훨씬 어려운 문제였다... 처음에는 단순한 문제로만 생각했어서 단순하게 풀려고 했는데 자꾸 예상치 못했던 케이스들이 등장했다. 부분 서열로 구성할 수 있고, 다양한 조건이 있지만 사실 {a,t}, {g,c} 를 매치하고 최대 부분 수열을 만들면 된다는 것으로 귀결된다. 여기까지는 좋았다. 하지만 그 다음부터 조건을 잘못 설정하여 문제를 제대로 ..

https://programmers.co.kr/learn/courses/30/lessons/1835 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 알고리즘 키워드 - 문자열 조작 - DFS 전역 변수를 안 써야 통과할 수 있는 문제다.. 안내에서는 전역 변수를 초기화해서 쓰라했지만, 초기화를 해도 통과가 안된다ㅠㅠ 그래서 걍 안 써버리고 call by reference 스타일로 문제를 풀었다. DFS 식으로 한 명 배치할 때마다 이전에 배치된 애들과 주어진 조건에 위배되는지를 확인하면서 DFS로 탐색을 ..

💚 2343 기타 레슨 블루레이의 크기는 모두 같아야 한다. i번과 j번 레슨을 같은 블루레이에 녹화하려면 i와 j 사이의 모든 레슨도 같은 블루레이에 녹화해야 한다. 블루레이 크기 = 그룹에 속해있는 레슨의 합 블루레이 크기의 최소값을 구한다 = 그룹의 합의 최대값의 최소값 구하기 이분 탐색으로 찾아야 하는 값 : 블루레이의 크기 #include using namespace std; int n, m; int a[100000]; // 크기가 size인 블루레이로 녹화하여 M개 이하의 블루레이가 나오는가? bool go (int size) { int cnt = 1; int sum = 0; for(int i = 0;i size) { cnt..

STP란 스패닝 트리 프로토콜(Spanning Tree Protocol)은 루프를 확인하고 적절히 포트를 사용하지 못하게 만들어 루프를 예방하는 매커니즘이다. 용어 그대로 잘 뻗은 나무처럼 뿌리부터 가지까지 루프가 생기지 않도록 유지하는 것이 스패닝 트리 프로토콜의 목적이다. 스패닝 트리 프로토콜을 이용해 루프를 예방하려면 전체 스위치가 어떻게 연결되는지 알아야 한다. 전체적인 스위치 연결 상황을 파악하려면 스위치 간에 정보를 전달하는 방법이 필요하다. 이를 위해 스위치는 BPDU(Bridge Protocol Data Unit)라는 프로토콜을 통해 스위치 간에 정보를 전달하고 이렇게 수집된 정보를 이용해 전체 네트워크 트리를 만들어 루프 구간을 확인한다. ✨ 왜 루프를 확인해야하는가 대부분 브로드캐스트 ..

이분 탐색 💚 1790 수 이어 쓰기2 #include using namespace std; // 1부터 n까지의 수 길이 구하기 long long calc(int n) { long long ans = 0; for(int start = 1, len = 1;start n) { end = n; } ans += (long long)(end - start + 1) * len; } return ans; } int main() { int n; long long k; cin >> n >> k; if(calc(n) x >> y >> z; a[x].push_back({y, z}); a[y].push_back({x, z}); } cin >> st >> ed; int left = 1; int rig..