본문 바로가기

알고리즘/백준

 (68)
백준 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] : 해당 노드가 일반인일 경우, (..
백준 9205 맥주 마시면서 걸어가기 - c++ 플로이드 와샬 풀이 문제 링크 www.acmicpc.net/problem/9205 풀이 아이디어 dfs bfs 말고 플로이드 와샬로 풀었다. x,y좌표를 한꺼번에 담아야 하므로 pair 꼴의 배열을 준비했다. 코드를 편하게 짜기 위해 갈수 있냐없냐를 bool 함수로 준비했고, 편의점 n개, 시작점 끝점 1개씩을 저장할 수 있는 d 이차원 배열 역시 준비했다. 적당히 큰 값으로 d 배열을 초기화 한 후, 한 포인트에서 다른 포인트로 갈 수 있으면 그 값을 1로 바꾸었다. 그리고 플로이드 와샬을 통해 경로를 최적화 한 후, d[0][n+1] 값을 비교해 (출발-끝 거리) 결과를 뽑아내면 된다. 코드 #include using namespace std; pair point[102]; int t,n; int d[102][102];..
백준 1620 - 나는야 포켓몬 마스터 이다솜 문제링크 www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이 아이디어 백준 풀면서 본 문제중 문제길이 제일 긴듯;;ㅋㅋㅋ 문제 자체는 쉽다. map 자료구조에 key,value쌍, value,key쌍 번갈아서 이렇게 두번 넣고 찾기만 하면 끝. c++로 풀 경우 입출력 속도에 주의하기 위해 반드시 첫 세줄은 넣도록 하자. 안넣으니 시간초과 나더라. 코드 #include using namespace std; int a,b; map..
백준 2565 전깃줄 - 아이디어가 중요한 DP 문제 문제 링크 www.acmicpc.net/problem/2565 풀이 아이디어 아이디어가 되게재밌다. 우선 전기줄이 '겹치게 되는는' 조건이 어떻게 되는지를 한번 생각해 봐야된다. 왼쪽 전봇대에서 위 아래로 시작하는 줄이 오른쪽 전봇대에서 아래 위로 끝나면 겹치게 된다. 근데 이렇게 생각하기 시작하면 개인적으로 좀 어려워 진다고 생각한다. 하나 기준을 정해야 한다. 왼쪽 전봇대로 정하는 것이 편하다. sort가 편하기 때문이다. 그러면 왼쪽 기준으로 정렬 되어있는 상태에서 for문을 돌릴 때, 오른쪽 에서 대소관계의 순서가 유지되면 안겹치는 것이다. 문제의 그림을 예시로 들자면 A를 기준으로 오름차순 정렬을 한 후 탐색을 진행하는 것이다. 1,2에서 시작하는 전기줄은 각각 8,2에서 끝난다. 1,2를 볼 ..

티스토리툴바