hyunjin

문제 S - G - H - T 혹은 S - H - G - T 의 경로가 S - T로 가는 최단 경로인지 확인하면 된다. 그래서 S,G,H 각각의 정점을 시작으로 하는 최단 길이를 다익스트라로 구한다. #include #include #include #include #define INF 0x7f7f7f7f #define MAX_N 2001 using namespace std; int N; int S, G, H; int dist[MAX_N][MAX_N], mdist[MAX_N], mdist_g[MAX_N], mdist_h[MAX_N]; bool vis[MAX_N]; void dijkstra(int start, int *d) { memset(vis, 0, sizeof(vis)); d[start] = 0; fo..

BOJ 20922 겹치는 건 싫어 O(N) #include #define MAX_N 200000 #define MAX_A 100001 using namespace std; int N, K; int arr[MAX_N]; int cnt[MAX_A]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; for (int i = 0; i > arr[i]; int ans = 1; int left = 0, right = 0; while (right < N) { int num = arr[right]; if (cnt[num] < K) { cnt[num]++; } else { while (arr[left] !..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 최장 증가 수열 (LIS, Longest Increasing Subsequence) 다이나믹 프로그래밍을 이용한 방법 : O(N^2) - 최장 길이 구하는 방법 앞 순서의 모든 원소에서 끝나는 최장 증가 수열들의 길이 중 가장 긴 것을 골라 1을 더한 것이 곧 현재 수에서 끝나는 최장 증가 수열의 길이이다. 따라서 dp..

문제 1차 코드 #include #include #include #include #include #define MAX_H 30 #define MAX_N 10 using namespace std; int N, H; bool grid[MAX_H+1][MAX_N+1]; vector candi; int ans = 10; bool InRange(int x) { return 0 ans) return; if (Verify()) ans = min(ans, cnt); if (cnt > 3) return; for (int i = start; i < candi.size(); i++) { int y, x; tie(y, x) = candi[i]; //선 겹침 if (InRange(x - 1) && grid[y][x - 1]) ..

15663 set 풀이 set은 키의 중복 허용하지 않고 키값 정렬시킨다. //참고 사이트 https://tooo1.tistory.com/327 #include #include #include #include #define MAX 9 using namespace std; int N,M; int num[MAX]; //input bool visited[MAX]={0,}; int arr[MAX]; set s; void Backtrack(int depth){//depth : depth이자 arr의 index if(depth == M){ vector v; for(auto i = 0; i>N>>M; for(int i = 0 ; i>num[i]; sort(num,num+N); Backtrack(0);//depth 의..

백준 이중 우선순위 큐 문제를 읽고 priority_queue 오름차순, 내림차순 2개를 사용해서 풀었으나 고려해야할 부분이 더 생겼고 결국 틀렸다. priority_queue 처럼 자동으로 정렬되면서 대신 앞 뒤 두 방향으로 다 접근 가능한 container가 set이라는 것을 찾았다. 그런데 set은 중복이 허용되지 않고 중복이 허용되는 것은 multiset이었다. 헤더파일 : #include multiset 사용법 multiset은 기본으로 오름차순 정렬된다. [소스 코드] multiset 사용 // multiset 사용법 #include #include #include using namespace std; typedef long long ll; void Solve(){ int testCase; c..

문제 바로가기 pow를 직접 구현하는 문제이다. 가장 단순하게 for문 돌려서 구현하면 당연히 시간 초과가 나온다. 연산 횟수를 줄여야한다. 예를 들어 $A^{4} = (A^{2})^2 $ : 짝수일때 $A^{5} = A * (A^{2})^2 $ : 홀수일때 이렇게 연산을 줄일 수 있다. 원래대로라면 $A^{4} $는 A*A*A*A로 연산이 총 3번이지만 2번으로 줄일 수 있게 된다. 즉, log2N 으로 연산 횟수가 줄어든다. 이것을 pow함수로 구현해주면 된다. #include using namespace std; typedef long long ll; ll A,B,C; void Input(){ cin >> A>>B>>C; } ll pow(int b){ if(b==0) return 1; ll tmp ..

BOJ 2170 선긋기 [실패 소스코드] 배열을 만들어 해당 구간 방문시 TRUE TREU인 곳에만 길이 구하기 #include using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll len = 2000000010, bias = 1000000000; //2000000010 1000000000 bool line[len]={0,}; int n; ll answer=0; cin >> n; for(int i=0;i>s>>e; for(ll j = s ; j>s>>e; v.push_back({s,e}); } sort(v.begin(),v.end()); int s = v[0].first..