소근소근

#include #include #include #include #include #include #include using namespace std; map genKey; map getCount; vector genNum; vector v[100]; bool comp(const pair&a , const pair&b){ if(a.first == b.first) return a.second > b.second; return a.first < b.first; } vector solution(vector gen, vector plays) { vector answer; int tmp = 0; for(int i=0;i

백준 4195 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구 관계 정보를 받아 친구 네트워크에 속하는 친구 수를 출력하는 문제로, 분리 집합(disjoint set)을 이용하여 풀었다. 숫자가 아니라 문자열을 입력 받으므로 자료구조 map을 이용하여 로 저장하여 정수로 처리했다. union find 설명 글 https://steptoprogrammer.tistory.com/64 [알고리즘/자료구조] 분리 집합( ..

분리 집합이란 교집합이 존재하지 않는 두개 이상의 집합을 뜻한다. 구분해야 하는 데이터 집합들을 다루는 알고리즘에서 사용할 수 있다. 분리집합에서는 자식 노드가 부모 노드를 가리키게 되어 있다. 보통 특정 집합의 대표 노드(루트)를 자식 노드들이 가리키고 있는 형태이다. 분리집합 연산에는 두 가지가 있다. 1. Union(x,y) 합집합 연산이다. 두개의 집합을 합치기 위해서 각 두 집합의 대표(루트)노드를 찾고, A의 대표노드의 부모를 B의 대표 노드로 설정한다. void Union(int x, int y) { int px = Find(x); int py = Find(y); if (px != py) { parent[px] = py; set_size[py] += set_size[px]; } } 합치려고 ..

백준 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번: 게임 개발 첫째 줄에 건물의 종류 수..