코딩하기 좋은날

이 문제는 nCk를 구하는 문제이지만 n이 400만으로 굉장히 큽니다. 이항계수는 보통 n이 작을때 nCk = n-1Ck-1 + nCk-1 다음과 같은식으로 동적계획법을 이용해서 구할 수 있지만 이경우 시간복잡도가 O(N^2)이 걸리게 됩니다. 따라서 이문제는 좀더 빠른 방법을 이용하여야 하는데 바로 nCk = n!/k!(n-k)! 식을 이용하는 겁니다. 페르마의 소정리에 따라 n^p-1 = 1 (mod p) 임을 알고 있습니다. 따라서 n^p-2 = n^-1 (mod p) 가되고 결론적으로 우리는 1 / k!(n-k)! 이라는 식을 k!(n-k)!^p-2라는 식으로 치환 할 수 있습니다. 총 정리를 하면 1. 1~n 까지 각 n! % MOD 를 구합니다. ( fac[] 배열) 2. n의 modular ..

안드로이드에서 Json 파일을 읽어서 사용을 해야 하는데 생각보다 까다로워서 정리겸 글을 쓰려고 합니다. 코드는 아래와 같습니다. Application.streamingAssetsPath, 파일이름 으로 파일에 접근 할 수 있고 파일은 Assets 하위에 StreamingAssets 폴더를 만들고 거기에 넣어두면 됩니다. 파일에 접근한뒤 WWW를 통해서 string 으로 읽어 들이면 됩니다. Json 파일 파싱의 경우 상단에 Serializable을 해준 클래스를 하나 만들어야 합니다. 이때 변수 이름을 key 값과 동일하게 하고 저는 Json 에서 배열을 사용하였으므로 List로 선언하였습니다. 파일을 읽어들인 string을 JsonUtility.FromJson(str) 을 통해서 해당 객체로 변환할 ..

저번 글에 이어서 유니티에서 DB를 어떻게 사용하는지 부터 시작하겠습니다. 간편하게 쓸 수 있는 sqlite를 이용하여서 진행을 하면 됩니다. DB테이블을 만드는 여러가지 프로그램이 있는 걸로 알고있는데 저는 DB browser라는 프로그램을 이용해서 테이블을 만들었습니다. 뭐대충 위와 같습니다. 공격력, hp, jumpcnt, gold 정도로 구성되어 있습니다. 이제 DB를 만들었으니 유니티에서 사용을 하여야 하는데 조금 해줘야 할것들이 있는데 https://m.blog.naver.com/PostView.nhn?blogId=daum7766&logNo=221484452303&categoryNo=29&proxyReferer=https%3A%2F%2Fwww.google.com%2F 유니티와 sqlite 연동..

Unity를 이용하여 게임을 한번 만들어 보고 싶어서 C#이나 유니티에 대해서 전혀 몰랐지만 만들고 싶은 것을 생각하고 필요한 기능들을 배우면서 미흡하게나마 게임은 만들어 보았습니다. 여러 블로그나 유튜브, Unity 매뉴얼들이 자세해서 크게 어려움은 없었던 것 같습니다. 만들면서 느낀점은 결국 기능은 어떻게 된다고 해도 재밌게 만드는 것과 그래픽,bgm 관련 부분들까지 혼자서 한다는 것은 정말 어렵다는 것을 느꼈습니다. C# 같은 경우는 처음 해보았지만 사실 다른 언어들을 꽤 많이 배워 왔기 때문에 크게 어려움은 없었습니다. 저는 물론 그런 능력이 안되므로 사용 된 모든 asset들은 유니티 asset store의 무료 asset과 다른 리소스 사이트의 무료 자료들을 이용하였습니다. 시작하기전에 기본적..

볼록 껍질(convex hull) 알고리즘의 기본 문제입니다. 기하는 역시 이것저것 할게 많아서 어려운 것 같습니다 ㅠㅠ.. 진행 순서는 1. y좌표가 가장 작고 그중 x좌표가 가장 작은 점이 나오도록 먼저 정렬을 해서 시작점을 정합니다. 2. 0번째 원소를 시작점으로 두고 나머지 N-1개의 점들을 0번째 점과 각도가 작은 순으로 다시 정렬을 합니다. 3. 이후 스택에 0,1번째 점을 집어넣고 2번째 점부터 스택의 상위 2개에 있는 점과 CCW를 검사해줍니다. 이때 CCW 값이 > 0 이라면 second 점을 포함하고 그렇지 않으면 넣지 않고 진행 해주면 답을 구할 수 있습니다. 각도 정렬 조건 함수 같은 경우 두점과 시작점과 CCW를 하여 이 값이 > 0 보다 크면 좌회전을 했다는 의미이므로 시작점과의..

이 문제는 각역사간 관계가 주어졌을때 각 사건들의 관계를 파악하는 문제입니다. 각 사건들의 전후관계를 알기 위해서는 결국 이 두사건이 한사건에서 다른사건으로 도달 할 수 있느냐를 알면 됩니다. 따라서 주어진 사건의 관계들을 단방향 그래프로 생각하여 사건노드에서 다른사건노드로 가는 경로의 존재유무를 알면 문제를 해결 할 수 있습니다. N이 400이하이므로 플로이드 와샬 알고리즘을 이용하면 모든 사건에 대한 경로를 파악할 수 있습니다. 이때 a,b가 순서대로 주어진다면 dp[a][b] 의 값이 존재하면 a가 더 빨리 발생한 사건이고 dp[b][a]값이 존재한다면 b가 더 빨리 발생한 사건이고 둘다 존재하지 않는다면 둘은 서로 관련이 없음을 알 수 있습니다. 다음은 코드입니다. #include #include..

0~N까지의 수를 K번 이용하여 N을 만드는 경우를 출력하는 문제입니다. N,K가 모두 j개의 숫자를 써서 i를 만드는 경우로 정의를 하였습니다. 숫자의 중복이 가능하므로 각 함수마다 0~N까지 숫자를 다돌려봐야 하므로 시간복잡도는 O(N^2*K) 정도가 되겠습니다. 아래는 코드입니다. #include #include #define MOD 1000000000 using namespace std; long long dp[220][220]; int N, K; long long sol(int k, int sum) { if (sum > N) return 0; if (K == k) { if (sum == N) return 1; else return 0; } long long &ret = dp[sum][k]; if..

그냥 대놓고 세그트리 문제입니다. 중간중간 값이 업데이트 되고 구간의 합을 구해야 하므로 구간의 합을 구하는 세그먼트 트리를 구현하면 끝입니다. 다음은 코드입니다. #include #include using namespace std; long long tree[300000]; long long arr[100010]; long long init(int node, int start, int end) { if (start == end) return tree[node] = arr[start]; int mid = (start + end) / 2; return tree[node] = init(node * 2, start, mid) + init(node * 2 + 1, mid + 1, end); } void upda..