east-wind 님의 블로그

트리면 간선 개수가 V-1개다. 기억하자... 생각하지 못해서 지피티 도움을 받았다.가중치가 음수가 아닐 때, 가장 거리가 긴 임의의 정점 두개 중 하나는 항상 임의의 정점에서 가장 먼 노드이다. https://psgood.tistory.com/13 [백준 #1967 c++] 트리의 지름, 증명하기https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의psgood.tistory.com이 글의 그림을 보면 이해가 쉬울 것 같다. #include #include #include using namespace std;..

못풀었다... 풀이를 보니 pq, map을 이용해서 풀었다. 비용을 뽑을 때 바로 빼는 것이 아닌, 뒤에 짝이 맞는 수를 뽑을 때 같이 빼주는 형식을 취했다. 이 점에 대해서 나는 뒤를 또 탐색해봐야하나 하는 생각을 했는데 이렇게 후처리를 하는 게 좋은 것 같다. 다음에 그렇게 해보자탐색에 대하여 unordered_map - O(1) map - O(N)#include #include #include #include #include using namespace std;//비용을 바로 빼는 게 아니라, 뒤에거 뽑을 때 같이 2개 빼는 식으로struct Pair{ int Cost; pair PairCard; Pair(int C, pair P) : Cost(C), PairCard(P) {} ..

30분 걸렸다. 이진 탐색으로 풀어 O(NlogN) 걸렸는데 스택을 활용하여 푸는게 맞는 거 같다. erase할 때 모든 원소를 순차적으로 한번씩 접근하기 때문에 시간초과가 안난 것 같다. 스택에 좀 익숙해지자....1. 이진탐색 풀이#include #include#includeusing namespace std;int n,x,y,res = 0;//n v;//고도가 높아지면 유지, 추가//고도가 낮아지면 낮아진 고도 위치찾아서 그보다 높은 애들 싹 제거 - 이진탐색//마지막에 고도 0 아니면 +1int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n; v.push_back(0); for(int i =..

스택을 생각 못하고 이진탐색으로 풀려고 하다가 결국 답보고 풀었다. 스택 사용하니까 너무 쉬웠다.. 이진탐색으로도 사실 nlogn안에 풀리는 건데 구현에 애를 먹은 것 같다. 1~n까지 차례로 정렬된 높이 순 배열에 넣고(log n), 넣은 위치부터 아래에 있는 인덱스에 전부 현재 인덱스값을 할당하는 방식인데.. 그냥 스택으로 푸는게 훨 나은 것 같다. 반복문이 2개 겹쳐져있다 해서 무조건 O(N^2)이 아니다.#include #include #include #include#include#include#include#includeusing namespace std;//오른쪽에서 왼쪽으로 레이저//완전탐색시 시간 초과 50만*50만//8 6 5 7 3//0 1 2 1 4int N;//N v;stack> s..

priority_queue의 사용법을 잘 익히자.... 여기선 비교 조건이 반대라는 사실을 꼭 기억하자. 즉 우선순위가 가장 낮은 아이가 top이다.#include #include #include #include#include#include#includeusing namespace std;struct comp { bool operator()(int a, int b) { if(abs(a)==abs(b)) return a > b; return abs(a) > abs(b); }};priority_queue, comp> q;int N, num;int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0..

30분 걸렸다.백준에서 비슷한 문제를 풀어본 게 도움이 되었다. 스택으로 올바른 괄호 문자열과 균형잡힌 괄호 문자열을 구분하고, 재귀로 구현했다.문제 이해가 빠르게 되고 구현을 빠르게 하면 더 빨리 풀 수 있던 것 같다. 당연한 소리긴한데그리고 확실히 함수를 세분화 하니 실수가 적어졌다. 앞으로 함수를 좀 세분화 해보자.#include #include #include#include#includeusing namespace std;//u는 최소단위 균형 문자열, v는 빈문자열 가능//u가 올바르다면 v 재귀 수행 결과를 u 뒤에 이어붙임//아니라면 ( + v 재귀 수행 결과 + ) + u 첫번째 마지막 문자 제거 후 괄호 방향 뒤집어서 추가//문자열 길이는 1000이하의 짝수bool is_valid(str..