기술 블로그

https://www.acmicpc.net/problem/16945 백트래킹 문제이다. 거의 풀렸다고 생각했는데 잘 안 풀렸다. 나는 미리 만들어진 배열을 활용하였기 때문이다.(진작 찾는 방식으로 하였으면 바로 풀렸을텐데 아쉬웠다.) 다른 분의 코드의 힌트를 참고하여 풀었다. 마침 내가 구현한 코드 및 구현 방식 그리고 생각과 거의 유사하여 바로 풀 수 있었다. 난이도는 엄청 어렵지는 않았다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929..

https://www.acmicpc.net/problem/16936 vector 배열을 활용하려고 하였는데, 숫자의 범위가 10^18까지 활용하는 바람에 pair로 구현하였다. 시간 초과 날 줄 알았는데, 안 났다. 다른 분은 two, three 변수를 활용하여 % 3 == 0, % 2 == 0을 활용해 sort하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #include #include #include #include #include #include #include #i..

https://www.acmicpc.net/problem/6087 나중에 다시 풀어 볼 문제이다. 만만하게 봤다가 큰 코 다친 문제이다. 단순히 거울의 개수가 더 적을 때, 갱신만 해주면 되는 줄 알았는데, 그게 아니었다. 우선 신경써야할 것은 while(!q.empty()){}에는 어떠한 종료 조건을 넣어서는 안 되고, 방향을 제대로 활용해야하며(dx, dy, i, direct 등), 88번 째 줄을 조심해야 한다. 또한, 본격적인 BFS 전에 출발지점에서 4가지 방향을 모두 queue에 넣어줘야한다. 계속 예제와 질문게시판의 반례가 해결되지 않아서 다른 분의 코드를 참고하였다. 몇 시간 동안 붙잡고 있었는지 모르겠다. 최소 8시간 인 듯 하다. 88번 째 줄은 아래와 같은 예제 때문에 >=로 써줘야 ..

https://www.acmicpc.net/problem/16932 처음에 2중 for문으로 모든 점을 탐색하여 '0'인 곳을 찾아 '1'로 바꿔 준 후 DFS를 실행하였다. 그런데 시간 초과가 떴고, 생각해보니 미리 DFS로 그룹화 시켜 그 개수를 배열에 저장해 활용하는 것이 시간 단축에 크게 도움 되었다. 코드가 조금 복잡해 보이는 건 착각이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103..

https://www.acmicpc.net/problem/16985 서울대학교 3/1 알고리즘 특강 문제 → https://www.acmicpc.net/contest/view/395 서울대학교 3/2 알고리즘 특강 문제 → https://www.acmicpc.net/contest/view/396 이 문제는 보자마자 Backtracking(next_permutation, 5중 for문), Bruteforce, BFS, Simulation의 짬뽕 문제임을 느꼈다. 우선, 총 5개의 층이 있고, 각각 4가지의 모습(회전)이 가능하므로, 4^5가 가능하다.(4*5 아님.) 그리고 총 5개의 층들을 배치시키는 경우의 수 5! 그리하여, BFS를 돌리면 총 6개의 방향으로 5*5*5의 칸들을 고려하면, 5*5*5*..

https://www.acmicpc.net/problem/13414 #include : https://hsdevelopment.tistory.com/251 어려웠다. 문제를 읽고, 이건 map을 이용할 수 밖에 없는 느낌을 받았고, 계속 map을 요리하면서(insert, erase의 활용 등등..) 그리고 vector도 요리하면서(unique 등등등...) 풀려고 몇 시간 동안 고민하였으나 결국 풀지 못 했다. 그래서 다른 분의 코드를 참고하였다. 참고하니, 내가 놓치는 부분들이 있었다. 1. map의 insert, count, erase 연산은 느리다. 그래서, 배열 형식으로 Key, Value를 저장해줘야한다. 2. K가 vector v의 v.size()보다 클 경우, 같은 경우, 작은 경우 이렇게 ..

#include 자동 정렬 및 중복 제거 그리고 이진트리 구조를 가진다. http://www.cplusplus.com/reference/stl/ 위의 링크에서 각종 STL을 볼 수 있으며, map도 있다. 구조를 가진다. find, erase 등등 많이 있으며, 위의 홈페이지에서 코드도 볼 수 있다. 나는 간단하게만 올리겠다. map은 Key가 중복되면 안 된다. 중복되면, 런타임 에러가 발생하므로, 중복을 허용하려면 multimap을 이용한다. 마지막으로 map.count(key)랑 map[key]를 구분하자. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#in..

https://www.acmicpc.net/problem/1181 C++의 map을 이용하였다. 자동으로 중복 제거 및 정렬을 해주기 때문이다. 위에서 말한 '중복 제거'라는 것은 map은 Key의 중복을 불허하기 때문에 Key값을 string으로 해주었다. 즉, string으로 해주면 다시 추가될 일이 없기 때문이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(d..