반응형 컴퓨터 사이언스/BOJ42 [c++] 백준 #17398 통신망 분할 (190826) 연결된 애를 쪼개는 것에 대해 물어보는 문제였는데, 반대로 쪼개져 있는 애들을 합치는 방식으로 disjoint set으로 구현한다.(신기..) 그래프를 union할 때마다 각 set의 원소의 개수를 서로 곱해서 cost를 더해준 다음에 빼주면 됨. 이때 원소의 개수를 어떻게 count할 지가 고민이었는데 모두 다 1로 초기화한 다음에 union할 때마다 부모(대빵) 노드 기준으로만 자기 밑에 원소 몇 개 있는 지 더해주면 된다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define N_MAX 100010 int p[N_.. 2019. 10. 8. [c++] 백준 #1987 알파벳 (190823) 완전탐색 문제. bfs 식으로 하면서 하면 되겠지? 하고? 코드를 짰는데 메모리 초과가 나왔다. 비트마스크도 써서 메모리 초과가 날 이유가 없는데 질문검색란에 나처럼 bfs식으로 푼 사람의 질문에 대한 답변을 보니 queue가 문제라고 한다. 뭔가 막연히 queue가 커지면 뻑가서 안된다는데 구체적으로 상상이 잘 안가서 직접 써봤다. (https://www.acmicpc.net/board/view/40634 에서 가져온 반례이다.) in: 20 20 ABCDEFGHIJKLMNOPQRST BCDEFGHIJKLMNOPQRSTU CDEFGHIJKLMNOPQRSTUV DEFGHIJKLMNOPQRSTUVW EFGHIJKLMNOPQRSTUVWX FGHIJKLMNOPQRSTUVWXY GHIJKLMNOPQ.. 2019. 10. 8. [c++] 백준 #1561 놀이공원 (190822) 2019/10/08 - [분류 전체보기] - 백준 1939 중량제한 (8.22) 를 풀고 나서 이분 탐색을 어떻게 쓸지 고민하다가 일단 놀이기구의 총 운행시간을 0~max 설정한 후 이분탐색하면서 총 운행시간 안에 탑승하는 어린이들 수를 계산해보고 모든 어린이가 다 탈 수 있는 그런 운행시간을 계산해봤다. 그 이후 운행시간 – 1일 때 어린이 수를 구하고 운행시간을 1 더하고 나서 그 시간에서 나누어 떨어지는 놀이기구가 있으면 어린이 수를 더하고 그 수가 N이 되면 그 때의 인덱스가 마지막 아이가 타는 놀이기구이다. 마지막 아이가 타는 놀이기구를 타기 위해서 계산하는 부분은 내가 알아내진 못했지만 이분 탐색 접근 방법 자체는 잘한 것 같아서 칭찬하자~! 마지막 아이가 타는 놀이기구 = 주어진.. 2019. 10. 8. [c++] 백준 #1939 중량제한 (190822) bfs + 이분 탐색 문제이다. 0~w_max 사이의 중간 값으로 상한을 정한 후, bfs를 계속 돌면서 그 상한보다 더 큰 값의 edge만 지나갈 수 있게 한다. 그때 마지막 점에 도달가능한지 아닌지 확인해보면서 이 상한선을 estimate하면 된다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define MAX_N 100010 int N, M; vector graph[MAX_N]; bool visited[MAX_N]; int start, fin; bool bfs(int limit){ queue q; q.push(star.. 2019. 10. 8. 이전 1 ··· 5 6 7 8 9 10 11 다음 반응형