반응형 컴퓨터 사이언스65 [c++] 백준 #2263 트리의 순회 https://www.acmicpc.net/problem/2263 한참을 이게 왜 분할정복 문제인지 고민하면서 보다가 post order의 속성을 이용하면 된다는 것을 깨달았다. 그것이 큐이다! post order의 경우 left right root 순으로 읽기 때문에 post order를 거꾸로 읽으면 root에서부터 root -> right -> left 순이 된다. 즉, post order에서 뒤에서부터 값을 읽으면 root가 무엇인 지 알 수 있고, 이를 통해 in order로 받은 input을 root를 기준으로 그래프를 left와 right로 나눌 수 있다.(분할정복의 의미) 나는 문제를 풀 때 in order와 post order를 보고 그래프가 어떻게 생겼는지 유추하고 나서(...), pr.. 2018. 11. 11. c++ binary_search 1. binary_search(starting point, ending point, value);특정 value가 어떤 container안에 있는 지 없는 지 bool 값으로 return함 // 백준 10815번 문제(숫자카드) 2. equal_range(starting point, ending point, value);특정 value가 어떤 container안에 몇 개 들어가있는지에 대한 정보를 제공 : pair로 lower_bound와 upper_bound를 return사용 예시 : auto a = equal_range(numbers.begin(),numbers.end(), value); // 백준 10816번 문제 (숫자카드 2) 2018. 11. 10. [c++] 백준 #2146 다리만들기 https://www.acmicpc.net/problem/2146 백준문제 #7576 토마토 문제를 풀었다면 비슷하게 풀 수 있다.각 섬에서부터 바다로 뻗어나가면서 섬에서의 거리를 측정하다가, 다른 섬에서 이미 거리를 측정한 부분을 만나는 경우, 두 거리를 더해서 그 합의 최소값을 구하면 된다. 이때 각 섬이 어디있는 지, 사전에 labeling을 해둬야하기 때문에 DFS를 돌리고, 그 다음에 거리를 BFS를 이용해서 구하면 된다. DFS를 이용하여 각 섬에 대해 labeling하는 것은 백준문제 #2667 단지번호 붙이기를 풀었다면 그냥 그때 쓴 코드 재활용하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142.. 2018. 10. 24. [c++]백준 #9466 텀프로젝트 https://www.acmicpc.net/problem/9466 1) DFS를 돌리면서 starting point부터 번호를 하나씩 매김(배열 dist 이용).2) DFS가 시작될 때마다 graph number를 새로 부여(변수 ng) 이용3) DFS를 돌다가 같은 그래프 내의 이미 방문한 점을 만나게 되면 그 점이 나오기 전까지의 노드는 cycle에 속하지 않으므로 cycle이 생기기 전까지의 노드의 개수를 배열 dist에 접근하여 더해줌e.g. 예시에서 1->3->3 순으로 노드를 방문하게 되는 경우 노드 1은 팀을 이루지 못함4) DFS를 돌다가 다른 그래프 내의 이미 방문한 점을 만나게 되면 그 전 노드까지 노드의 개수를 배열 dist에 접근하여 더해줌e.g. 예시에서 이미 1-.. 2018. 10. 24. 이전 1 ··· 13 14 15 16 17 다음 반응형