Algorithm2 [프로그래머스] 거리두기 확인하기 (C++) 유형 : DFS/BFS 코멘트 카카오 문제이지만 되게 삼성 같은(?) 문제다. 맨 처음에는 그냥 시뮬레이션처럼 풀었는데, 몇 개의 테스트 케이스가 통과하지 못해서 DFS/BFS로 접근했다. 문제에서 '맨해튼 거리'라고 어렵게 말했지만, 전형적인 BFS로 한 칸씩 이동할 때마다 거리를 +1 해주면 되는 문제이다. 설명 핵심 Idea : 모든 사람이 있는 좌표에서 BFS로 나와의 거리가 2 이하인 좌표가 하나라도 있는지 검사한다. 5개의 대기실마다 각각 아래 과정을 반복한다. 5*5의 모든 좌표마다, 이번 자리에 사람('P')이 앉아있는 경우에만 탐색을 진행한다. ('P'가 아니면 continue) BFS를 돌면서, 나와 다른 모든 사람의 거리를 구한다. (bfs()함수, 파티션('X')은 방문할 수 없음을.. 2021. 7. 17. [백준] 2805. 나무 자르기 (Python) 유형 : 이분 탐색 설명 나무를 아래 그림과 같이 자르는 상황이다. 절단할 높이 H를 기준으로 이분 탐색을 한다. H만큼 나무를 자르고, 위에 남은 윗부분을 다 합친다(tree_sum). 상근이는 이걸 집에 가져가는 거다. tree_sum과 필요한 나무(m)를 비교한다. tree_sum이 m 이상이면 : 상근이가 원하는 조건을 만족한다. 현재까지의 정답 중 최댓값으로 업데이트한다. 하지만 우린 '최적의 값', 여기서는 '최댓값'을 찾아야 하기 때문에 h를 늘려서 다시 이분 탐색을 한다. tree_sum이 m보다 작으면 : 나무가 부족하다. 상근이가 원하는 조건을 만족하지 못한다. 나무를 더 베어야 하므로, h를 줄여서 이분 탐색한다. 코드 (Python) # 입력받기 n, m = map(int, inpu.. 2021. 7. 6. 이전 1 다음
