hyunjin

문제 링크코드 문제주어진 그래프에서 t 단계 별로 인접한 노드와 연결 엣지 지워나감.최초로 사이클 생성되지 않는 t 구하기N,M  풀이 전략사이클이 사라지는 것을 찾긴 어렵다.  → 사이클 생성 여부 확인으로 바꾸면 쉽다.주어진 순서대로 간선을 지우고 사이클 생성 여부를 확인 , 지울때마다 사이클을 판단 → TLE그렇다면 역순으로 판단하자.  마지막에 사라졌던 간선들부터 시작하여 처음 사라진 간선들 순서로 그래프가 복원하자.간선이 지워지는 역순으로 그래프를 생성해나가 보면, 어느 순간 사이클 발생 →  (전체 T - 사이클 생성 되는 t) 가 답 요약간선이 언제 지워지는지는 알겠음 : BFS를 적절히 응용지워지는 역순으로 간선을 연결해나가가다가 사이클이 생기는 시점 판단인풋으로 주어지는 K개 시작 노드를..

문제   1. Top Down, 재귀N에 도달 가능 여부만 판단한다.#include #include #include #define MAX_N 5001using namespace std;int N, K;int e[MAX_N], dp[MAX_N];// top - down// 도달 가능 여부만 확인하면 된다// 갈 수 있으면 바로 끝 // 2중 for 사용 가능int canGo(int target) { int& ret = dp[target]; if (ret != -1) return ret; ret = 0; //0으로 설정, 일단 못간다 세팅 // i -> target으로 이동 for (int i = 0; i > N >> K; for (int i = 0; i > e[i]; ..

문제 풀이좀 조건이 까다로웠다. ( +1) -1로 놓고 생각했다.순차적으로 해당 위치를 반대 괄호를 바꿨을 때 불가능한 경우를 생각해보면 (단, 한번의 오타만 냈다는 조건이 중요하다)양끝단 검사. 맨 앞은 ( , 맨 뒤는 ) 이어야한다.최종적으로 ( ) 개수가 같아야하므로 맨 끝에 합이 0 나와야한다. ( → )  : 해당 위치에서  ~ 맨 끝에 음수가 있는지 확인.  ) → (  : 해당 위치에서 앞 부분에 음수 있는지 확인.( ) ) ( ( )  이 케이스를 생각해보면 된다.  1차 코드#include #define MAX_N 100001using namespace std;string str;int arr[MAX_N];int sum[MAX_N];int len;bool possible(int idx, ..

BOJ 줄어드는 수 문제 풀이 1. 가장 큰 줄어드는 수는 9876543210 이다. 10자리. 2. 기장 큰 수를 알고 있으므로 먼저 9876543210까지의 줄어드는 수를 모두 구한다. 3. 그 다음 정렬 후 n 번째 수를 출력, 범위 넘어가면 -1 출력 소스 코드 #include using namespace std; typedef long long ll; void MakeIncreNum(ll num, int level, vector& v){ if(level > 10) return; v.push_back(num); for(int i = num%10-1 ; i>=0 ;i--){ MakeIncreNum(num*10 + i, level+1, v); } } int main(){ ios::sync_with_s..

BOJ 20117 문제 자체가 어렵지 않다. gold 5 [힌트] 가장 비싸게 팔 수 있는 방법은 가장 비싼 것과 싼 것을 묶어라. [문제 풀이] 짝수 묶음의 경우 (a, b) (a>n; int qual[n]; for(int i = 0 ; i >qual[i++]; sort(qual,qual+n); int max_profit = 0; for(int i = n-1 ; i >= (int)((n+1)/2) ; i-- ){ max_profit += qual[i]; } max_profit = (n%2==0) ? max_profit*2 : max_profit*2 + qual[n/2]; cout

백준 N번째 큰 수 문제 힌트 N*N은 의미가 없다. 우선순위 큐를 사용해 푼다. 메모리 초과 조심 문제 풀이 큰 흐름 : 순서대로 우선 순위 큐에 넣어서 n번째 수 출력 1. 오름 차순 우선 순위 큐에 수 입력 받아 넣는다. 단, n*n 모두 받아 실행하면 메모리 초과 뜬다. 총 n+1개만 남도록 n 초과되면 pop() 한 이후에 입력받은 수를 넣는다. 2. 입력이 끝나면 우선 순위 큐에는 총 n+1개의 원소만 남는다. 하나 팝한 후 top출력 소스코드 #include using namespace std; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n; cin >> n; priority_queue pq;//오름차순 for(int i..

백준 좌표 압축 문제 풀이는 간단하다. 복사해서 정렬 후 작은 것 수 출력하면 된다. 이때 필요한 벡터 복사, 중복 제거, lower_bound 사용법 기억해두자 1. 벡터 복사 //방법1 v2.assign(v1.begin(),v1.end()); //방법2 copy(v1.begin(),v1.end(),v2.begin()); 2. 벡터 중복 제거 방법1. vector v({1,1,1,2,2,2,3,3}); sort(v.begin(),v.end()); //v.erase(unique(v.begin() , v.end() )); //이렇게 하면 전체 중복 제거 못함 v.erase(unique(v.begin() , v.end() ) , v.end()); sort 후에 unique와 erase 통해서 중복 제거 방법..