기술 블로그

https://algospot.com/judge/problem/read/DARPA 비슷한 문제 : https://hsdevelopment.tistory.com/548파라매트릭 서치(Parametric Search) Greedy 그리디 탐색 복습 필수 추천 코테 코딩 계속 오답이길래 봤더니 이분 탐색 시작점(s)을 1로 했었다. 답이 0인 경우도 있는 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include using namespace std; int n, m; bool chk(const vector &v, double mid){..

https://programmers.co.kr/learn/courses/30/lessons/42746# 처음에 백트래킹인줄 알았다. 그런데 vector 요소의 개수가 100,000개임을 보고 이건 아니다 라고 생각하였다. 방법을 몰라서 다른 분들의 코드를 보았는데, 모두들 cmp 함수를 잘 활용하셨다. 왜 백트래킹으로만 생각했는지 모르겠다. 가장 큰 수이므로, 내림차순 정렬을 조금이라도 생각했었으면 접근은 했었을텐데 아쉬웠다. 1234567891011121314151617181920212223242526272829#include #include #include using namespace std; bool cmp(const string & a, const string & b){ return a + b >..

https://algospot.com/judge/problem/read/POLY 이 문제는 그냥 책을 바로 보았다. 도저히, 풀 수가 없는 문제였다. 그리고, 책의 풀이를 보고 충격을 먹었다. 이렇게 풀 수 있구나.. 이 문제 또한 계속해서 다시 풀어볼 문제이다. 참고로, 67번 째출에서 sum을 누적하며 더하면서 1000만이 넘을 수 있기 때문에sum %= MOD를 써줬다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include #include #include #include #inc..

https://algospot.com/judge/problem/read/LIS#c16488 굉장히 정형화된 알고리즘이라서, 이외의 구현은 틀렸다고 봐도 된다. 참고로 BOJ에 이와 관련된 문제들이 많다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #include #include #include #include #include #include #include using namespace std; int main(void){ int T = 0, N = 0, num = 0; scanf("%d", &T); while (T--..

https://algospot.com/judge/problem/read/PI 생각보다 그렇게 어렵지는 않은 내용인 것 같다. 책의 classify 함수를 보고, 놀랐다. 저렇게도 구현을 할 수 있구나.. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include #include #include #include #include #include #include #include #include #include us..

알고스팟 문제 : https://algospot.com/judge/problem/read/TRIANGLEPATH BOJ 문제 : https://www.acmicpc.net/problem/1932 위의 2개 문제는 풀이도 완전히 똑같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include #include #include #include #include #include #include #include using namespace std; int tri[110][110] = { 0, }; int main(void){ int T = 0, n = 0, num = ..

https://algospot.com/judge/problem/read/WILDCARD#c7900 이 코드들은 외울정도로 다시 풀어봐야겠다. 2개의 코드를 올리겠다. 1. 시간 복잡도 n^32. 시간 복잡도 n^2 첫 번째 코드의 40번 째 줄 skip + s

https://algospot.com/judge/problem/read/JUMPGAME 2가지 방법의 코드가 있다. 첫 번째는 내가 푼 BFS 방식이고,두 번째는 책에 나와있는 재귀 호출(동적 계획법, 메모이제이션)로 푼 방식이다. 참고로, 첫 번째 코드(BFS)의 18 ~ 19번 째 줄 dy, dx 배열은 지워도 된다. 안 쓰였음. (왜 안 지웠지?) BFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include #include #include #include #in..