목록분류 (103)
이모저모
버블소트의 성질이 이용하는 문제이다. 처음 LIS를 활용하여 길이 x일 때 n-x+1로 구할라고 했으나 반례가 있었던것 같다. 위 문제는 버블소트의 성질인 (원래 위치 - 정렬 후 위치) 값 이 가장 큰 값만큼 수행하면 정렬된다.왜냐하면 문제의 버블소트는 가장 큰 값을 끝부터 차곡차곡 쌓아가므로작은 값은 한번 루프를 돌 때 한칸 씩만 이동하기 때문에 차이가 가장 큰 값만큼 루프를 돌아야한다. 소스코드 #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#define INF 2..
위상 정렬을 이용해당 노드의 최소시작 학기는 선수과목의 최대 시작학기 + 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_pairtypedef pair pii;typedef long long ll;typedef unsigned long long ull; int n,m,out[1001],income[1001]..
약수를 구해서 비교만 하면 끝 #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; int main () {freopen("sample.txt", "r", stdin);int t,n,sum,limit;scanf("%d",..
그냥 진법 변환한 뒤양 끝을 기준으로 회문 여부를 확인한다. #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; int main () {freopen("sample.txt", "r", stdin);int i,t,n,r,..
점화식dp[pos][prev step] : 이전 스텝이 pre step 이고 현재 위치가 pos 일때 최대값dp[p][1] = dp[p-1][2] + data[p]dp[p][2] = max(dp[p-2][1], dp[p-2][2]) + data[p]나는 재귀형태로 그냥 풀었다. 소스코드 #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#defi..
테두리에 도달하는 최솟값을 찾는 문제이다. 처음 DP를 생각하였으나 생각이 잘 나지 않아서 4방향으로 연결된 그래프 문제로 다이젝스트라를 이용하여 풀었다.(양의 정수 조건이 붙어 있으므로) 테두리에 도달하면 다이젝스트라의 성질에 의해서 그것이 가장 최솟값이므로 그 값을 출력한다. 아래는 소스 코드이다. #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_..
리프노드의 갯수를 세는 문제이다. 함정이 있다면1. 루트노드를 삭제하는 경우2. 해당 노드를 삭제 후 부모 노드가 리프 노드가 되는 경우 발생 이것을 고려해야 한다. dfs로 리프 부터 쭉 올라와서 카운트 하면 된다. 아래는 소스코드이다. #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..
dp문제로 아직 실력이 부족하여 푸는데 무척 어려웠다.다른사람의 코드를 힌트로 삼아 풀었다. 시도 1DP(I,J) : I ~ J 뭉치를 하나의 뭉치로 합쳤을때 최소 횟수DP(I,J) = MIN(DP(I,K)+DP(K+1,J)+두개를 합치는 횟수)오류가 있다 전체 다를 고려해야 최솟값이 나온다 분할해서 합치면 최소 횟수가 나오지 않는다. 시도 2정렬을 시키고 각 포지션을 DFS로 탐색하여 최솟값을 구한다.지수의 복잡도를 가지므로 안된다. 해결방법총 이동 횟수 = 분할된 조각 수 * 2 - n - 1 이된다.최솟값을 구할려면 분할된 조각 수가 최소가 되는 것을 찾아야 한다.dp[p][prev] : 위치가 p일때 이전 조각의 뭉치 번호가 prev 일때 최소 분할 조각 수라 하자dp[p][prev] = min(..
문제)1 3 4 2 8 7 -1 3 5 ....n개의 숫자가 주어지고, 윈도우 크기 l이 주어졌을 때A(i-l+1) ~ A(i) 범위 내의 최소값 혹은 최댓값을 구하여라 다음과 같은 문제가 주어졌을 때 무식하게 풀면 O(NL)의 복잡도를 가진다. 우리가 생각할 알고리즘은 슬라이딩 윈도우 알고리즘이다. 위의 문제에 대해서 optimal 한 알고리즘이며, 복잡도는 O(N)이 된다. 슬라이딩 윈도우 알고리즘기존의 계산했던것을 최대한 활용하여 다음것을 빠르게 구할 수 있도록 하는 방법이다.문제에 따라서 공간적, 시간적 두가지 방법으로 접근하여 사용할 수 있다. 위의 문제를 생각해 보면N을 2L-1크기로 나누어 보자.A(1) A(2) ... A(L-1) A(L) A(L+1) ... A(2L-1)M(1,L) M(2..
1. 슬라이딩 윈도우 알고리즘을 활용(O(N)복잡도를 가지며 해당 문제에 대해서 optimal algorithm) 2. 입력이 많기 때문에 문자열로 입력받고 숫자로 변환하여 속도를 개선 #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..