전체 글 (171) 썸네일형 리스트형 [BOJ] [Python] 2630 : 색종이 만들기 분할정복 알고리즘을 이용했다. 분할정복 알고리즘의 로직은 다음과 같다. 1. 문제가 분할이 가능하면, 2개 이상으로 나눈다. 2. 나누어진 문제가 여전히 분할 가능하면 1번을 다시 수행하고, 가능하지 않다면 문제를 푼다. 3. 나누어진 각각을 모두 합병한다. 이 문제는 해결이 가능할 때까지 반복해서 4등분으로 나눈다. 즉, 계속 쿼드 트리를 만드는 것이다. (쿼드 트리는 트리의 자식 노드가 4개인 트리를 뜻한다.) 어떻게 4등분을 할지 생각해보자. 색종이는 항상 정사각형이기 때문에, 4등분을 하고 각 왼쪽 위을 기준으로 재귀함수를 돌리는 것을 반복한다. num = int(input()) graph = [list(map(int, input().split())) for _ in range(num)] w = .. [BOJ] [Python] 5212 : 지구온난화 현재 지도를 기준으로, 섬이 삼면 이상의 바다로 둘러싸여 있다면 50년 후 그 섬은 잠긴다. 지도상에서 섬이 바다로 바뀌는 데는 굳이 BFS를 사용할 필요가 없다고 생각했다. 바이러스처럼 퍼져나가는 상황이 아니기 때문이다. 이중 반복문을 통해서 해결해보자. 현재 지도인, graph 리스트와 같은 지도를 하나 더 만든다. 이것은 copy 리스트인데, 이중 반복문을 돌며 50년 후 상황을 기록한다. 바다는 . 뿐만 아니라 r과 c의 범위를 나간 곳도 포함이다. 섬을 기준으로 상하좌우를 확인하면서 삼면 이상 바다라면, 섬의 위칫값을 0으로 변경한다. r, c = map(int, input().split()) graph = [[0] * c for _ in range(r)] copy = [[0] * c for _.. [BOJ] [Python] 10971 : 외판원 순회 2 문제의 예제 입력을 표로 작성해보았다. 주의할 점 1. 모든 도시를 경유한다. 2. [i][j]가 0일 경우 갈 수 없는 길이다. 3. 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 고민했던 점 1. 어디서 출발해야 할까? 2. 어떻게 최단 거리로 모두 경유할까? 모든 도시를 경유해야 하는 문제 때문에, 다익스트라 알고리즘을 사용하지 않았다. 백트래킹으로 해결해 보자. n = int(input()) li = [] li_idx = [] dp = [0] * n result = 1e9 for _ in range(n): li.append(list(map(int, input().split()))) def back(cnt): global result if cnt.. 이전 1 ··· 36 37 38 39 40 41 42 ··· 57 다음
