이모저모

정수 삼각형이라는 문제이다. 오랜만에 알고리즘 문제를 풀어보니 c++을 다 까먹었다..... 머리가 너무 나쁜것 같다. 일단 문제는 아주 간단하며 풀이도 간단하다. 메모리는 O(N)이며 시간복잡도는 O(N^2)으로 풀 수 있다. 간단히 대각선 왼쪽 및 오른쪽에서 내려 올 수 있기 때문에 현재 위치가 i라면 i-1, i 중 큰 값을 가져오면된다. 점화식은 A[j][i] = max(A[j-1][i], A[j-1][i-1]) + input value (단 j는 j번째 줄 i는 그 줄의 i번째를 의미) 이렇게 보면 메모리가 N^2이여야 할것 같지만 이 전 값만 가지고 있으면 되기 때문에 2N으로 풀 수 있다. 아래는 풀이이다. 12345678910111213141516171819202122232425262728..

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define MAX_INT 2147483647#define MAX_LLONG 9223372036854775807 /*set을 이용하여 시간복잡도 O(NlogN)에 풀수 있다.*/int main(void){ freopen("sample.txt", "r", stdin); int n;set set; scanf("%d",&n); for(int i=0, x; i

해결방법다이젝스트라를 이용하는 기본적인 문제이다.최단거리 방법을 이용하면서갱신될때 경로의 가짓수를 더하면 최종적인 가짓수를 구할 수 있다.시간 복잡도는 O((E+V)logV) 이다. 시간을 조금 더 줄이기 위해서원하는 노드에 도착하게 되었고, 그 때에 weight 보다 크면 루프를 탈출 한다.(단일 시발점에서 모든 정점을 다 구할 필요는 없다는 뜻이다.) 아래는 소스코드이다.#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000009#define INF 2147483647#defin..

해결방법냅색 문제이다. 점화식dp[p][sum] : p-1까지 sum만큼 구했을 때 앞으로 목표 m에 정확히 도달하기 위한 최소 마나 값dp[p][sum] = min(dp[p+1][sum+life[p]]+mana)로 구해진다. 아래는 소스코드이다.#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 ..

해결방법전형적인 이분탐색을 이용한 방법이다.(수정) value = 0 인 경우를 생각해줘야한다. => 삽질했다...시간복잡도는 O(SlogL) 아래는 소스코드이다.#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;typ..

해결방법다이나믹 프로그래밍이다.점화식dp[i][j] : [i,j]의 부분집합 중에서 팰린드롭의 갯수dp[i][j] = dp[i+1][j] (i를 포함하지 않는 경우) + dp[i][j-1] (j를 포함하지 않는 경우)- dp[i+1][j-1] (i,j 둘 다 포함하지 않는 경우(교집합이 발생하므로 빼준다.))+ str+i==str+j? dp[i+1][j-1]+1:0 (i,j가 같아서 i,j를 포함하는 경우 이때 +1하는 이유는 사이가 부분집합이 포함되어 있지 않으므로)시간 복잡도 O(n^2)초기 해결할때는 O(N^3)으로 풀었는데 풀이가 너무 복잡하여 시간복잡도를 줄인 방법으로 설명한다. 아래는 소스코드이다.#include #include #include #include #include #include ..

해결방법1) SPFA 알고리즘을 활용ㄱ) height 기준으로 정렬ㄴ) 순회하며 SPFA로 돌린다.travel[N][K] : n번째 노드가 k번 이동하였을 때 최소 높이SPFA를 사용한 이유는 다이젝스트라처럼 돌리면 최솟값이 나오지 않는다.(optimal 하지 않다.)단순 bfs를 이용하면 지수복잡도를 가지게 된다.ㄴ-1) 작은 값을 기준으로 순회하기 때문에 해당 노드를 방문하면 이 후 최소값을 가질 일은 없다. 시간복잡도 O(N^2K) 의 복잡도를 가진다. 최대 travel 배열만큼 O(NK)가 큐에 들어갈 수잇고 각각 최대 O(N)만큼 체크하기 때문이다. 2) dp로 풀기점화식은 아래와 같다.dp[n][k] : n번째 노드에서 k번 이동하였을 때 최소 높이dp[n][k] = for n' in edge..

해결방법MST를 이용하면 되며 저는 크루스칼 알고리즘을 사용하였다.MST를 하기 위해서 문제의 조건을 만족하기 위해서서로 성별이 같은 대학의 edge가 들어오면 무시하고 다른 경우에만 받으면 된다.이 후 MST를 만들면 된다.시간 복잡도 O(ElogE) 아래는 소스코드이다.#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 ma..

해결방법단순 다이젝스트라를 사용하는 방법이다.문제 설명이 이해가 어렵게 만들어놔서 매우 틀렸다......단순 a,b 둘다 0개 도달되는 경우 -1그 이외의 경우에는 작은 값을 출력하면 된다. 아래는 소스코드이다. #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_pair#define f first#define s se..

해결방법에라토스테네스의 체를 이용하여 소수를 구함각 조건에 맞게 시뮬레이션이 돌려주면된다.문제의 설명이 조금 이상하긴하다. 아래는 소스코드이다.#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 p..