전체 글
-
[PS] 백준 2293번: 동전 1, 2294번: 동전 2카테고리 없음 2023. 11. 30. 22:26
동전 1 동전 2 dp연습하며 고른 문제이다. 무엇을 기준으로 dp를 할까 엄청 고민하다 결국 힌트를 봐버렸다. 총 가격으로 dp를 한다는 아이디어를 얻자마자 쉽게 풀 수 있었다. dp는 언제쯤 익숙해질까... 이런식으로 n원을 내기 위한 총 경우의 수를 계산하면 된다. 동전2는 저기서 경우의수가 대신 n원당 내야하는 동전의 수로 업데이트 하도록 바꿔 쉽게 연계해서 풀었다. // 동전 1 #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) for (auto& e : S) int n, k; vector coins; int dp[1000..
-
[PS] 백준 1260번: DFS와 BFS문제해결 2023. 11. 30. 16:27
DFS와 BFS 너무 정직한 DFS, BFS 문제이다. 다만, 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 이 부분 참고하여, DFS, BFS할 때 FIFO, LIFO에 맞춰 저렇게 sort 해준 뒤 push_back 해주면 끝. #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) for (auto& e : S) int N, M, V; vector av[1000]; bool visited[1000]; void dfs() { memset(visited, 0, sizeof(bool) * 1000..
-
[PS] 백준 1629번: 곱셈문제해결 2023. 11. 28. 21:05
곱셈 행렬곱셈 문제 풀며 썼던 분할정복. 처음엔 홀수일 때 long long int ret = (a * ab_2 * ab_2) % C; 이런식으로 했더니 계속 오버플로우가 났고 나는 그냥 어리둥절하고만 있었다. long long int ret = (a * ((ab_2 * ab_2) % C) % C; 사실상 이렇게 했어야 했는데, 아무래도 코드를 잘 정리해 두어야 하는 이유가 아닌가 싶다. #include using namespace std; #define ll long long int ll A, B, C; ll times(ll a, ll b) { if (b == 1) return a % C; ll ab_2 = times(a, b / 2) % C; ll ret = (ab_2 * ab_2) % C; if (..
-
[PS] 백준 11687번: 팩토리얼 0의 개수문제해결 2023. 11. 28. 18:16
팩토리얼 0의 개수 그냥 무작정 1부터 M까지 계수를 셌다. 당연히 시간초과가 뜰거라 생각했는데 AC되었다. M이 1억일 경우 100'000'000번 넘게 연산이 되는데 어떻게 0.5초만에 된거지 #include using namespace std; int M; int get_5(int f) { int fives = 0; while (!(f % 5)) { f /= 5; fives += 1; } return fives; } int main() { cin >> M; long long f = 0, val = 0; while (true) { f += 5; val += get_5(f); if (val == M) { cout
-
[PS] 백준 23253번: 자료구조는 정말 최고야문제해결 2023. 11. 28. 16:56
자료구조는 정말 최고야 스텍들 돌아가며 하나씩 팝 하면 되는 간단한 실버5 자료구조 문제인줄 알았다. 제출하고보니 계속 시간초과가 뜨길래 뭔가 이상함을 느꼈다. 생각해보니 200'000개의 책을 하나씩 200'000개의 더미로 놓은 다음, 200'000 199'999 ... 2 1 이런식으로 배치하면 총 20'000'100'000번 순회해야하니 당연히 시간초과가 날 수밖에 없다. 문제를 다시 읽어보니, 스택이 내림차순인지 확인을 하기만 하면 될 듯 하여 다시 제출하고 AC되었다. #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i < static_cast(N); i++) #define FORL(e, S) f..
-
[드론] PX4 + ros noetic offboard control troubleshooting개발 로그/바코드 드론 2023. 11. 23. 21:02
https://docs.px4.io/main/ko/ros/mavros_offboard_python.html MAVROS Offboard control example (Python) | PX4 오토파일럿 사용자 설명서 (main) MAVROS Offboard control example (Python) This tutorial shows the basics of OFFBOARD control with MAVROS Python, using an Iris quadcopter simulated in Gazebo Classic. It provides step-by-step instructions demonstrating how to start developing programs to co docs.px4.io 이..
-
[PS] 백준 9251번: LCS, 백준 5582번: 공통 부분 문자열문제해결 2023. 11. 20. 19:57
LCS, 공통 부분 문자열 dp는 할때마다 어려운 것 같다. O(N) dp에 좀 적응했다 싶었는데 O(N²) dp가 나와서 애먹었는데, 이번엔 2차원 dp다. 이런식으로 dp를 진행하면 된다. // 9251번: LCS #include using namespace std; #define endl "\n" #define FOR(i, N) for (int i = 0; i > s1 >> s2; if (s2.length() > s1.length()) swap(s1, s2); FOR(i, s1.length()) { ..