알고리즘65 백준 15591 MooTube (Silver) 문제 https://www.acmicpc.net/problem/15591 해결방법 주어진 k, v가 있다 k보다 크거나 같은 USADO를 카운팅하는 문제이다. 주어진 예제에서 1 -> 2 일때 3 2 -> 3일때 2 2 -> 4 일때 4이다 예제에서 k :4, v:1일때 0으로 나와있다 왜? 1에서 시작해서 1 -> 2 -> 4로해서 그럼 2 -> 4 값이 4이니 k 2 -> 4는 값이 min(3, 4)로 3이된다. 여기서 좋은 방법은 출발점에서 bfs를 하다가 조건을 다음 cost가 현재보다 클 경우만 queue에 담는 것이다 . 또 ! 이문제는 가장작은 값으로 갱신하지만 최단경로는 아니기에 dfs로도 가능하다. 주의 if (!visited[nx] && k 4로 갈때 비용이 4더라도 usaco이거 때문.. 2021. 10. 2. 백준 6603 로또 (bfs) 이 문제는 죽일 노드를 받고 리프 노도의 갯수를 구하면된다 문제 링크 : https://www.acmicpc.net/problem/6603 풀이법 이문제에서 죽이는 노드 == 탐색하지 않는 노드 이렇게 하면 그 노드를 죽이게 되어서 그 밑으로 내려가지 않게 된다.! 여기서 예외처리에서 루트노드를 죽일 수도있다는 것이다 루튼노트가 죽지 않았으면 루트부터 탐색을 수행하면된다. #include using namespace std; int n, Kill, rootNode, res; vector v[51]; vector ans; bool visited[51]; void bfs(int idx) { queue q; q.push(idx); visited[idx] = 1; while (!q.empty()) { int x.. 2021. 8. 23. 순열과 조합 (로또 : 6603) 백준 순열은 순서가 있고 조합은 순서가 없다 ex : 1 2 3 , 3 2 1은 순열에서 순서가 중요가 하기에 다른 수 지만 조합에서는 뽑았다는 '의미'에서 동일하기에 같은 수로 본다 dfs 재귀 스택프레임 void dfs(int idx) { ans.push_back(v[idx]); if (ans.size() == 6) { for (auto a : ans) cout > a; dfs(0); } return 0; }헷갈린 부분 이 코드에서 로또 번호 6개를 뽑으면 된다 여기서 엄청 헷갈렸던 것이 pop_back()이 두개라서 매우 헷갈렸다. 첫번째 pop_back() 여기서 pop_back()은 수가 1 2 3 4 5 6 7 까지있는데 현재 1 2 3 4 5 6까지 선택했다면 다음은 6을빼고 7을 .. 2021. 8. 23. leetcode , Sliding Window Maximum 문제 출처: https://leetcode.com/submissions/#/1 풀이 방법 슬라이딩 윈도우 각 칸을 [ ] 크기만큼 보면서 이동하면된다. 이때 multiset을 이용하면 가장 큰값을 알 수 있다. 빼야하는 값은 k만큼 이동하기에 num[i-k]이다 다음 원소를 볼때 먼저 k개를 유지하기 위해서 num[i-k]를 지운다. 값을 삽입 내부에서 정렬이 되어서 max값을 찾을 수 있다. 그 max를 정답 배열에 삽입.. for (int i = k; i < nums.size(); i++) { m.erase(m.find(nums[i - k])); m.insert(nums[i]); ans.push_back(*m.begin()); } 2021. 8. 19. 이전 1 ··· 11 12 13 14 15 16 17 다음