백준 (22) 썸네일형 리스트형 백준 12003 Diamond collector(silver) : 구간 2개를 구해야 하는 슬라이딩 윈도우 문제 문제 링크 www.acmicpc.net/problem/12003 12003번: Diamond Collector (Silver) The first line of the input file contains \(N\) and \(K\) (\(0 \leq K \leq 1,000,000,000\)). The next \(N\) lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed \(1,000,000,000\). www.acmicpc.net 풀이 아이디어 문제 해석을 간단히 하자면, 케이스 안에 다이아몬드를 넣는데 케이스 안에 들어간 다이아몬드들 끼리는 크기 .. 백준 2213 트리의 독립집합 - 어떤놈인지까지 찾아야 하는 트리dp c++ 문제 링크 www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 풀이 아이디어 트리 dp 문제를 단계로 나눠보자면 1단계는 사회망 서비스 hqjang.tistory.com/104?category=913845 문제를 들 수 있다. 단순히 그 트리 내에서의 요구하는 값의 최댓값 혹은 최솟값을 찾아내면 되는 문제. 이 문제는 2단계 정도에 해당한다. 최댓값/최솟값을 찾고, 그 값을 이루는 노드들을 구해야 한다. 당연히 dfs를 이용한 트.. 백준 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 백준 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 값.. 백준 2056 작업 - 위상정렬과 dp가 함께 쓰이는 문제 문제 링크 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 아이디어 작업을 완료하기 위해 어떤 작업이 먼저 수행되어야 하는지를 파악해야 하므로 당연히 위상정렬 문제이다. 친절하게 각 줄의 두번째 int 값으로 indegree(먼저 수행되어야 하는 노드, 즉 조상노드의 개수)가 써져 있으므로 그대로 써먹으면 된다. (numOfancestor) dp는 바로 이 '선행되는 조상노드의 실행 시간의 최댓값' 을 파악하기 위해 사용된다. 쉽게 예를 들어보.. 백준 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.. 백준 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.. 210106 백준 250문제를 풀고 느낀 점 200124 100문제 달성 200213 150문제 달성 200417 200문제 달성 210106 250문제 달성 50문제 더 푸는데 8달 반정도가 걸렸다. 9~10월 두달 제외하고는 그닥 많이 놀지는 않았었는데, 알고리즘에 소홀했던 건 팩트다. 그래서 요새는 퇴근하고 놀거나 딱히 그러지 않고 백준 붙잡고 파는 중. 4월까지는 솔직히 구현력이나, 풀이 아이디어, 알고리즘 사용능력 폼이 많이 올라온 상태였다. 알고리즘 공부한지 4달도 안된 시기였으나 그 4달을 알고리즘에 많이 시간투자를 한 결과였다. 8달 반 쉬고, 1월 시작한 이후부터 다시 초심잡고 차근차근 해나가고 있다. 쉬어보고 다시 잡아보니, 실버 문제들 중에서도 버거운 문제들이 등장하기 시작. 다행히 예전 짬이 있어서 어떤 문제를 보면 아 무슨 .. 이전 1 2 3 다음
