분류 전체보기 (106) 썸네일형 리스트형 백준 1158 요세푸스 문제 : 큐,벡터로 각각 푸는 2가지 방법 문제 링크 www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 아이디어 규칙성을 찾아 벡터를 이용해 푸는 방법과 큐를 이용해 직접 k-1번씩 앞에 숫자를 빼서 뒤에넣은 후 k번째 숫자를 출력하는 방법이 있다. 어느것으로 풀어도 상관없음. 코드 방법 1. 큐를 이용해 푸는 법 #include using namespace std; queue q; int n,k,temp; int main(void){ cin >> n >> k; for(int i=1; i 백준 2150 strongly connected component 링크 www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 풀이 아이디어 SCC 관련 문제를 처음 풀어보는데 여러 블로그들 글을 참고했다. 자손 9319님 포스팅 jason9319.tistory.com/98 이 가장 깔끔하게 알고리즘을 설명해주신 글 같다. 코사라주 알고리즘을 이용해 문제를 풀었고, 코사라주 알고리즘을 간단히 설명하자면 스택과 역방향 그래프를 만들어 dfs를 2번 탐색함으로써.. 백준 1647 도시 분할 계획 : 전형적인 MST + 부모 동일 유무 파악시 주의할 점 문제 링크 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 풀이 아이디어 오랜만에 mst(minimum spanning tree) 문제를 풀어보았다. MST의 구현 방법의 기본은 union find 이므로 반드시 union find(disjoint set) --> MST 순서대로 공부할 것. 그러면 내가 코드에 쓴 find(),union() 함수의 의미를 알 것이다. 알 것이라 가정하고, 문제는 각 edge의 cost 값.. 백준 1516 게임 개발 - 위상정렬과 dp가 함께 쓰이는 문제(2) 문제 링크 www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 아이디어 백준 2056번 문제와 매우 비슷하다. 입출력 부분만 좀 달라졌다 보면 된다. www.acmicpc.net/problem/2056 풀이는 여기를 보면 된다. hqjang.tistory.com/108 백준 2056 작업 - 위상정렬과 dp가 함께 쓰이는 문제 문제 링크 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ .. 백준 2056 작업 - 위상정렬과 dp가 함께 쓰이는 문제 문제 링크 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 아이디어 작업을 완료하기 위해 어떤 작업이 먼저 수행되어야 하는지를 파악해야 하므로 당연히 위상정렬 문제이다. 친절하게 각 줄의 두번째 int 값으로 indegree(먼저 수행되어야 하는 노드, 즉 조상노드의 개수)가 써져 있으므로 그대로 써먹으면 된다. (numOfancestor) dp는 바로 이 '선행되는 조상노드의 실행 시간의 최댓값' 을 파악하기 위해 사용된다. 쉽게 예를 들어보.. 백준 4195 친구 네트워크 - map과 union-find 혼합 문제 문제 링크 www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 아이디어 줄이 n개일때 최대 2n명의 인물이 나올 수 있음을 인지하고 초기화를 진행하자. 이름을 map의 key로 저장(파이썬에서는 딕셔너리)하고, value로는 각자 고유한 숫자 값을 저장한다. 후에 이 value가 union find를 할 때 node의 index값이 될 것이다. 편의상 앞에 나오는 녀석이 parent가 된다고 가정하고, union을 진행할 때 자식 노드의 친구 개.. 백준 1976 여행가자 - 2차원 array 형태로 데이터 주어질 때 효과적인 union find 문제 링크 www.acmicpc.net/problem/1976 풀이 아이디어 2차원 배열에 메모리를 할당해서 0과 1을 전부 저장할 필요가 없다. 1이 나올 시에는 두 노드를 가지고 disjoint set을 만드는 것이므로, 바로 union find를 때려 버리면 되는 문제였다. 코드 #include using namespace std; int n,m; int node; int root[201]; int find(int x){ if(root[x]==x) return x; else return root[x]=find(root[x]); } void un(int x, int y){ x = find(x); y = find(y); root[x]=y; } int main(void){ cin>>n>>m; for(in.. 백준 2533 사회망 서비스 - 가장 쉽고 자세한 트리 dp로 푸는 방법 문제 링크 www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 풀이 아이디어 이 문제는 각 노드별로 단 2가지 state밖에 없다. 해당 노드가 얼리 어답터이거나, 그냥 일반인이거나. 두 state는 완전히 독립적이므로, 다이나믹 프로그래밍의 적용이 가능하다. dp[node][0] : 해당 노드가 얼리 어답터일 경우, 본인 노드 + 해당 노드의 모든 자식노드 중 문제 조건을 만족하는 최소얼리어답터 수 dp[node][1] : 해당 노드가 일반인일 경우, (.. 이전 1 2 3 4 5 ··· 14 다음
