알고리즘/BruteForce 썸네일형 리스트형 [BruteForce] 백준 28215, 대피소 이 문제는 생각보다 description이 길다. 가장 주요하게 보아야 할 부분은 무엇보다 변수 n의 범위가 50이라는 점이다. 그렇다면 이 문제는 O($n^4$)까지 시간복잡도를 가져갈 수 있다는 것을 의미한다. 중요하게 깨달아야 할 부분을 기술해 보겠다. 1) O($n^4$)의 시간복잡도가 허용되므로, Bruteforce일 가능성이 크다. 2) 거리가 최소가 될 수 있는 대피소의 위치는 "집"에 설치한다고 명기되어 있다 이 부분을 꼭 잘 캐치해야 한다. 즉, 탐색 도메인이 X, Y의 100,000이 아니라 50개의 집의 위치로 좁아지게 된다. 3) X, Y는 서로 연관이 있기 때문에 완전 독립적으로 풀어서는 안된다. 4) 시간복잡도를 줄이려고 median값으로 푸는 것도 시도해 볼 수 있다. 그런데 .. 더보기 [BruteForce] BJ_1018 체스판 다시 칠하기 알고리즘의 존재 이유이자 최종 목적은 제한시간 안에 얼마나 효율적으로 문제를 계산해 낼 수 있으냐이다. 따라서, 모든 알고리즘 문제에서 수의 입력 범위를 확인하는 것은 중요한 일이다. 입력 범위가 충분히 작다면 굳이 어려운 방법으로 문제를 풀 필요가 없다는 뜻이된다. 컴퓨터는 1초에 1억번 정도의 연산을 해낼 정도로 계산에 최적화된 기계이다. 그렇다면 이 문제에서는 얼마만큼의 연산량이 필요할까? 문제를 읽어보면 확인할 수 있겠지만, 입력으로 주어지는 전체 판의 크기는 50 x 50이다. 여기에서 기준이 되는 매트릭스 좌측 상단의 색깔이 'W', 'B' 두가지 케이스에, 검사해야 하는 maxtrix의 크기인 8x8이다. 총 계산량은 ? 아무리 크게 잡아도 32만을 넘기 어렵다. 그렇다면 우리가 이 문제를 .. 더보기 이전 1 다음
