알고리즘 썸네일형 리스트형 1793번 1793번 - 타일링 D[N] 은 2*N 직사각형을 채우는 방법의 수라고 할때 D[N]=D[N-1] + 2*D[N-2] 가 된다. 근데 이 문제의 가장 큰 문제점은 바로 답이 long long의 범위를 벗어난다는 점이다. 따라서 BigInteger 를 구현해야 하는데, 나는 이걸 구현해본적도 없고... 구현 할 생각도 없어서 인터넷에서 긁어왔다. DP부분은 밑으 go() 함수만을 보면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293.. 더보기 15559번 15559번 - 내 선물을 받아줘 처음에 단순히 연결요소의 갯수 문제라고 생각했는데, 한번 더 생각해야 했다. 내가 지금 있는 지점에서 움직일 수 있는 좌표와 내가 지금 있는 지점으로 올 수 있는 좌표를 모두 dfs를 통해서 체크하였다. 그래서 연결 요소가 총 몇개가 나올 수 있는지를 확인하면 되는 문제였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#include#includeusing name.. 더보기 2484번 2484번 - 주사위 네개 은근 헷갈리는 문제였다. 배열을 1~6까지 만들고, 나온 갯수만큼 배열을 ++해준다. 그리고 4개 나온경우, 3개 나온경우, 2개 2개 경우를 체크해준다. 그러면서 1이 나온 값은 계속 sum에 갱신을 한다. 그리고 for문을 빠져나왔을 때 2개 나온 경우를 체크해주고, 최대값과 비교해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include#include#includeusing namespace std; int main(){ //freopen("input.txt", "r", stdin.. 더보기 3665번(다시풀기) 3665번 - 최종 순위 위상정렬을 잊어버리기도 했고, 나에게 꽤나 까다로운 문제였다. 이 문제는 항상 연결리스트로 그래프 문제를 풀던 나한테, 인접 행렬로 푸는게 효과적일 수 있다는 걸 깨닫게 해줬다. 그리고 순위가 뒤바뀔 때, 우선 순위가 통째로 바뀌는 것이 아니라, indegree 값이 ++ 혹은 -- 해줘야 한다는 점이 헷갈렸다. 그리고 마지막으로 답을 구할 때, 평소처럼 while(!q.empty()) 가 아니라 N까지만 돌면서 큐에 들어있지 않다면, 이는 DAG가 아니여서, 즉 싸이클이 생겨서 순위를 구할 수 없다는 점이고. 큐에 두개의 값이 들어있다면, 이는 순위를 정확하게 결정할 수 없기 때문에 ? 를 출력해야 했다. 생각보다 많은걸 얻은 문제인 것 같다. 다음에 또 다시 풀어봐야지 123.. 더보기 10825번 10825번 - 국영수 operator 재정의를 통해서 문제를 해결할 수 있었다. 원래 operator 재정의를 잘 몰랐었는데, 이 문제와 그 외 슬랙에 질문을 통해서 사용할 줄 알게 됐다. 슬랙에 operator 매개변수에 const 를 꼭 사용해야 하는지 물었는데, 갓님들의 답변 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#includeusing namespace std;const int INF = 987654321;typedef struct { int kor; int eng; int mat.. 더보기 5635번 5635번 - 생일 구조체 연습을 해봤다. 단순히 if 문을 쓰는 문제였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include#includeusing namespace std;const int INF = 987654321;typedef struct { int day; int month; int year; string name;}person;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); int n; person old = { INF,I.. 더보기 11066번(다시풀기) 11066번 - 파일 합치기 풀려고 생각하다가 못 풀어서 결국 구글링을 보고 해결했다. 다시 풀어볼 문제 D[i][j] 는 i 에서 j 까지 파일을 합칠 때 가장 최솟값 D[i][j] = D[i][k] + D[k+1][j] + sum[j]-sum[i-1] (i~j까지의 합) 이라는 점화식으로 문제를 풀 수 있었다. 이때 i 와 j 가 같다면, 자기 자신이기 때문에 더할 필요가 없게 되고, i와 j의 차이가 1일때는 두 값의 합을 리턴하게 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778.. 더보기 3124. 최소 스패닝 트리 3124. 최소 스패닝 트리 오랜만에 크루스칼 알고리즘을 사용해서 최소 스패닝 트리 문제를 풀어봤다. 최소 스패닝 트리는 간선을 가중치에 따라 오름차순으로 정렬하고, union-find 를 이용해서 추가할지 말지를 결정하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include#include#includeusing namespace std;int p[100001]; int find(int a){ if (a == p[a]) { return a; } else { return p[a.. 더보기 이전 1 ··· 6 7 8 9 10 11 12 ··· 46 다음
