소근소근

백준 13711 LCS4 https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net https://steptoprogrammer.tistory.com/60 [백준 BOJ 17218 glod5 - 비밀번호 만들기] Longest Common String (LCS) C++ 백준 17218 https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기..

- C++에서 제공하는 이진탐색 기반의 탐색 함수이다. - 이진 탐색 기반이므로 O(logN)의 복잡도로 탐색이 가능하다. - 배열은 오름차순 혹은 내림차순으로 정렬이 되어 있어야 한다. 1. lower_bound vector num = { 3,4,4,5,6 }; int idx = lower_bound(num.begin(), num.end(), 4) - num.begin(); cout

백준 17218 https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열 www.acmicpc.net 이렇게 두개의 문자열에서 가장 긴 공통 수열을 찾고, 그 수열을 출력해야 하는 문제이다. 2차원 배열을 이용한 dp로 해결할 수 있다. #include #include #include #include #include #include #include #include using namespace std; int alpha[41][41]; char str1[41]; char str..

백준 3665 최종 순위 https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬 문제이다. 2차원 배열에 edge를 저장하는 방식으로 풀었다. int nf, nt; cin >> nf >> nt; /*if (adj[nt][nf] == 1) { adj[nt][nf] = 0; indegree[nf]--; } adj[nf][nt] = 1; indegree[nt]++;*/ if (adj[nf][nt]) { adj[nf][nt] = 0; adj[..

백준 2056 작업 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬 문제이다. 1516 게임개발 문제와 매우 비슷하다. https://steptoprogrammer.tistory.com/57 [백준 BOJ 1516 gold3 - 게임 개발] 위상정렬(topological sort) C++ 백준 1516 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수..

백준 1516 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 어떤 건물을 짓기 전에 먼저 지어야 하는 건물이 있다는 조건에서 위상정렬을 떠올릴 수 있다. #include #include #include #include #include #include #include using namespace std; int N; int period[501]; vector adj[501]; int indegree[501]; int dab..

백준 문제집 1766 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1부터 N까지의 문제를 푸는 순서를 출력한다. 조건은 두가지다. 1. 되도록 쉬운 문제 먼저 푼다.(작은 숫자 문제 먼저 풀어야 한다) 2. 먼저 푸는 문제가 있으면 먼저 풀어야 한다. (두 문제 간에 우선순위가 있다.) 문제 간의 우선순위를 지키면서, 쉬운문제를 풀어야 한다. 1번조건을 충족하기 위해서 우선순위 큐를 사용하고, 2번 조건은 위상..

백준 1715 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 카드 묶음 A와 B를 묶기 위해서는 A+B만큼의 비교가 필요하다. 여러 묶음이 있을 때 다 하나의 묶음으로 만들기 위해 필요한 '최소' 비교 회수를 구해야 한다. 작은 것부터 묶었을 때가 최소가 되는 것을 예제를 보면 쉽게 알 수 있다. priority queue를 사용해서 작은 것부터 묶고, 묶고난 것을 다시 queue에 넣어주면서 반복한다. 처음에 q..