분류 전체보기101 [백준/C++] #24229 모두싸인 출근길 (Greedy) 문제https://www.acmicpc.net/problem/24229 구상문제를 읽고나서 DP나 greedy 종류의 문제인 것 같았다. 이전에 이동한 곳을 벡터든 변수든 큐든 저장을 해놓고 다음 위치로 이동할 수 있는지 없는지 확인 한 후 이동시키는 거였으니까. 문제는 한 장소에서 이동할 수 있는 유효 거리 안에 판자 여러개가 있을 수 있고, 무조건 가까운 판자를 고르거나 먼 판자를 고르는 것이 정답이 아니라는 점이었다. 그래서 우선순위 큐(max heap)를 사용하여 현재 위치(R)에서 이동할 수 있는 모든 판자를 구하면서 큐에 해당 판자의 R을 넣었다. 그렇게 큐에 원소가 없을 때까지 최종 도달 위치를 가장 먼 곳으로 갱신하다 보면 답이 도출된다. 문제 자체는 쉬웠는데 구현이 좀 빡셌다. 자잘자잘.. 2024. 8. 26. [백준/C++] #2263 트리의 순회 (divide and conquer) 문제https://www.acmicpc.net/problem/2263 구상트리의 전위, 중위, 후위 순회와 관련한 문제였는데, 1년 전에 자료구조를 배웠던게 가물가물해서 다시 찾아서 공부해보았다. 아래 포스팅에 너무 잘 나와있어 풀이에 도움이 되었다. https://ldgeao99.tistory.com/402 챕터7-2. 트리 | 순회방법(전위, 중위, 후위)트리의 순회(Tree Traversal) - 트리도 그래프이기 때문에 DFS와 BFS 방식 모두 가능하다. - 그런데 트리에서만 가능한 아래의 3가지 방법이 있다.(각각의 차이는 루트 노드의 방문을 언제 하냐의 차이)ldgeao99.tistory.com 우선, 세가지 순회의 특성에 대해 간략히 말해보자면, 전위 순회는(Preorder) 루트 -> 왼.. 2024. 8. 24. [백준/C++] #1074 Z (divide and conquer) 문제https://www.acmicpc.net/problem/1074 이전에 풀었던 문제인데, 분할정복 문제를 안푼지 하도 오래돼서 나름 분할정복의 클래식 문제라고 생각하는 'Z' 문제를 다시 풀었다. 2달 전에 왜 파이썬으로 풀었었는지는 모르겠지만..ㅋㅋ C++로 다시금 풀어보니까 감회도 새롭고 좋았다. 구상분할정복 유형이라는 걸 알아서 그랬는지 정말 쉽고 빨리 풀었다. 거의 로직 구상 3분에 구현 2분? 정도 걸렸던 것 같다. 나는 보통 입력값을 보고 로직을 구상하는 편인데, Z모양이 반복되는 횟수(?) N과 행과 열이 주어지니까 N의 크기만큼 반복해서 행과 열을 변화시켜가며 방문 순서를 업데이트하면 되겠다!는 생각을 했다. 우선 가장 큰 틀부터 가장 작은 틀까지 차례로 고려하며 행과 열을 통해 각각.. 2024. 8. 24. [백준/C++] #14938 서강그라운드 (Dijkstra) 문제https://www.acmicpc.net/problem/14938구상수색 범위 때문에 낙하지점마다 갈 수 있는 지역들이 다르고, 각 지역들에서 얻을 수 있는 아이템 수가 다르다. 이때, 어떤 지점에 낙하를 해서, 얼마나의 아이템을 얻을 수 있는지 묻는 문제였다. 즉, 한 지점에서 출발을 하면, 최단거리가 수색 범위 이하인 곳들을 추출하고, 그렇게 갈 수 있는 지역들에서 얻을 수 있는 아이템들을 다 더하면 하나의 출발지에서 얻을 수 있는 아이템 수들을 구할 수 있다. 그래서 결국 이문제의 키 포인트는 최단거리가 수색 범위 이하인 곳들을 추출하는 것이고, 각 길마다 거리가 다르므로, 결국 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 데에 사용되는 Dijkstra 알.. 2024. 8. 21. 이전 1 ··· 10 11 12 13 14 15 16 ··· 26 다음
