목록BOJ (45)
이모저모
해결방법brute force로 3개를 선택하여 최솟값을 구한다.그리디한 방법으로 풀면 안됨. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;typedef pair pll;typedef pair pii; int mai..
해결방법brute force O(N!*2^N)이 된다. 무진장 크다.최소값, 최대값을 구하는 문제는 왠지 DP로 풀어야할 것 같은 느낌이 들었는데 막상 DP로 접근하려고 하니 도저히 점화식이 세워지지 않았다..... 아 너무 어렵다 생각하고 몇일 뒤에 다시 보았다.그래서 n-1개를 유심히 보면서 n개 노드 n-1개 선택.....?? 아 MST!!!!!!!!!!!!!!!!!!!!!!!가 딱 생각이 났다.MST를 이용하여 최소값을 구할수도 최대값을 구할수도 있다.MST를 만드는 알고리즘은 3가지가 있는데 거기서 나는 크루스칼 알고리즘을 사용하였다. 슈도코드1) 노드 N개 edge가 N^2가 있는 graph로 생각하고 모든 edge를 계산한다.(시청률로)2) 정렬을 수행한다.3) 유니온 파인드를 이용하여 크루..
해결방법벡터의 외적을 이용하여 선분의 교점을 판단하는 문제이다.1) 각 선분을 기울기가 작은 값으로 sort2) 레이저도 마찬가지로 기울기가 작은 값으로 sort3) 모든 선분에 대해서3-1) 선분 벡터에서 레이저의 위치를 구한다.(upper_bound)3-2) 위치 이하의 값들에(그 이상의 값에 대해서는 검사를 해봐야 해당사항 없고 다음 레이저가 수행한다.) 대해서 레이저와 외적을 구해
해결방법 bfs를 2번 이용하여 1에서 갈 수 있는 지점(outgoing으로) 및 n에서 갈 수 있는 지점(incoming으로)을 체크한다.즉 1에서 나가는 방향으로 bfs, n에서 들어가는 방향으로 bfs를 돌리면 각각이 모두 가능하면 문제를 해결할 수 있다.시간복잡도 O(V+E)공간복잡도 O(V+E) 아래는 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#de..
해결방법BFS를 이용하여 depth, prev path를 구하면 된다. 소스코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;typedef pair pll;typedef pair pii; int n,k,visit[..
해결 방법우선순위 큐를 이용하여 BFS 하듯이 돌면 된다.조심할 점은 순간이동을 할때는 방문만 확인하는 것이 아니라 값도 비교해봐야한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;typedef pair pll;..
해결방법BFS를 활용하여 쭉 순회하면서 이미 방문한 숫자도 depth가 같은 경우 경우의 수를 추가하면 된다.굳이 depth를 저장할 필요없이 훨씬 간단하게 구현할 수 있는데 안했다.....초심 잃은 것인가.....아 그리고 굳이 범위인 100000 보다 크게 잡을 필요는 없다. 왜냐하면 v*2를 해서 10만 보다 큰 값에서 감소하는 것보다 (v-1) * 2와 같이 감소하고 곱하는 것이 depth가 반가량 감소하게 되기 때문이다.나중에 좀 간소하게 짜도록 노력하자.....시간 복잡도는 O(N) 왜냐하면 중복 숫자는 큐에 집어 넣지 않기 때문에~~공간 복잡도는 O(N) 방문과 숫자를 카운트하기 위해서~~~ #include #include #include #include #include #include #i..
해결방법xor의 성질은 이용한 방법이다.xor을 짝수번하면 안한것과 같고 홀수번하면 한번한것과 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;typedef pair pll;typedef pair pii; in..
벡터를 이용해서 간단히 문제의 쿼리에 맞게 처리만 해주면 되는 문제이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2147483647#define LNF 9223372036854775807#define pb push_back#define mp make_pairtypedef long long ll;typedef unsigned long long ull;typedef pair pll;typedef pair pii; bool cmp(pii lhs, ..
해결 방법1) i in for all vertex2-1) j in for all edges[i]3) k in for all edges[j]4) if(connect(j,k))cycle++;duplication[k]++; 2-2) ret += cycle/2*(cycle/2-1)/2(1,2) (2,1) 중복되게 계산 되므로 2로 나누어 주어야한다.2-3) j in for all vertexret -= duplication[j]*(duplication[j]-1)/2 하나의 겹치는 교점을 정해 놓고.1)길이가 3인 사이클을 모두 찾는다.그러면 모래시계의 조합은 사이클의 갯수가 n일때 nC2가 된다.그런데 겹치는 것이 존재한다. 즉 교점이 1개가 아니라 2개가 되는 경우가 발생한다.!!!그래서 겹치는 것의 모래시계..