2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 1. 분석 및 고찰 전에 포스팅했던 1272문제와 다른 tree dp문제를 경험했던 덕분에 각 노드가 루트가 되고 해당 노드의 상태가 0 혹은 1일때로 나누어 계산하면 된다는 점을 바로 깨달을 수 있었다. 2. 실패 이 문제는 추가적으로 back-tracking 과정을 걷혀야 하는데 이를 dp 업데이트 도중에 갱신하고자 하였으나 $N^2$의 공간 복잡도 문제로 고민하는 데 시간을 많이 소비하였다. 3. 성공 back-trackin..

1272번: 특별 노드 n(1 M; for(int i=1;i> w[i]; for(int i=1;i> x >> y; v[x].push_back(y); v[y].push_back(x); } for(auto&i:v[M]) ans += process(i, M, M); cout

1. 문제설명 N개의 멀티탭 구멍이 존재하며 M번 전자기기를 사용한다. 이 때 멀티탭에서 전자기기를 빼야하는 최소 횟수는 몇 번인지 구해라. ( N , M N){ ans++; pq.pop(); chk[num] = 0;} if(!chk[n]) pq.push(Data{n}); chk[n] = last; } } 처음 생각한 아이디어를 구현한 코드 중 일부이다. 이미 플러그에 해당 전자제품이 꽃혀 있을 경우 그 전자제품을 업데이트하면 되지 않을까? 하여 위와 같이 코드를 작성하였고 멀티탭에 꽃혀있는 전자제품 수를 pq.size() 를 통해 알아낼 수 있지 않을까 생각하여 위 처럼 코드를 짜개 되었다. 하지만 위 코드의 치명적인 실수가 있다. 그것은 바로 중간에 chk[n]을 바꿔도 priority_queue가 ..

우리 컴퓨터는 모든 데이터를 2진수로 저장한다. 그리고 컴퓨터는 "정확하고 빠르다." 일 터.. 가끔 백준의 수학 문제 중 계산 문제가 틀리는 경우도 많고.. 연구 분야에서도 이러한 일로 오류가 발생하곤 한다. 그러면 왜 이런 오류가 발생하고 어떠헥 해결할 수 있는지 소개하고자 한다. 1. 오차 원인 컴퓨터는 수를 이진수로 나타낸다. 이 때 정수 부분은 어느 수준까지 유한하기에 나타낼 수 있지만 그와 달리 소수 부분은 무한 소수처럼 매우 긴 경우... 이를 다 저장할 수 없다. 그리고 안타깝게도 f = 3.145646546228 -> output : 3.1456465721... [소수점 10자리 까지 출력] 위와 같은 예시처럼 그 뒤의 소수점을 날리는 형태가 아니라 그냥 값이 다르다. 이 원인 또한 이진..

1. 문제 설명 N개의 숫자들이 주어진다. 이 숫자를 적절히 나열하여 한 개의 수를 만들 때 최대가 되도록 만들어라. 단, 맨 앞의 수가 0이 될 수는 없으며 그러한 경우 0을 출력해라. N은 1000이하의 자연수이다. 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 출처 : https://www.acmicpc.net/problem/16496 2. 풀이 1) 접근 과정 처음에 보자마자 그냥 그리디로 풀면 되겠다고 떠올렸다... 그렇게 생각한 까닭은 "정렬" 이라는 키워드가 보였..

알고리즘 문제를 풀면서 가끔 어이없는 실수로 인해 시간을 날리기 쉽다. 그 중 내가 가장 많이 했던 실수는 자료형 계산이다. 오류가 뜨진 않지만 값이 달라서 더 짜증나는 실수다. 그래서 가장 많이 하는 실수들의 사례를 가지고 왔다. 1. 예시 #include using namespace std; const int INF = 21e8; const long long int INF2 = 21e8; const float f = 3.56789123; #define ll long long int int main() { ll a = INF + INF; ll b = INF + INF2; printf("%lld\n%lld\n",a, b); printf("%f, %.5f, %.4f, %d, %d, %f, %f, %llf"..

출처 : https://www.acmicpc.net/problem/28220 28220번: 블록 쌓기 첫 번째 줄에 $N$, $L$, $R$이 공백으로 구분되어 주어진다. 두 번째 줄에 $A_1$, $\dots$, $A_N$이 공백으로 구분되어 주어진다. www.acmicpc.net 1. 문제 설명 1~N번 칸이 존재하며 i번 칸에 {A_i}개의 블록이 쌓여있다. 각 칸에 쌓인 블록의 개수가 L이상 R이하가 되면서 {A_i}를 오름차순이 되도록 배치하고자 한다. 블록은 한 번에 양 옆으로 한 개씩만 옮길 수 있다. 블록을 옮기는 횟수의 최솟값을 구하라. 2. 실패 1 1) 접근 과정 이 문제를 처음 봤을 때 해당 조건을 만족하되 {A_i}가 최소이면 될 것이라고 간과하였다. 그래서 그리디로 접근해 보았다..