완전탐색

[python] 백준 - 10819. 차이를 최대로

🤔문제 해결 S2 | 완전탐색, 백트래킹 백트래킹을 하려고 했으나, 순열로 푸는게 더 간단해보여서 조합을 이용했다. 숫자들을 배치할 수 있는 모든 경우의 수를 뽑아서 규칙에 맞게 계산을 해주고 최대값을 찾는다. 💻소스 코드 from itertools import permutations def my_sum(numbers_tuple): # 문제의 규칙에 맞게 더하기 total = 0 for i in range(N - 1): total += abs(numbers_tuple[i] - numbers_tuple[i + 1]) return total if __name__ == '__main__': N = int(input()) numbers = list(map(int, input().split())) answer =..

[python] 백준 - 18428. 감시 피하기

🤔문제 해결 S1 | 완전탐색 N의 범위가 매우 작으므로 완전탐색을 하는 문제이다. 벽을 세울 수 있는 빈 공간을 리스트로 구하고, 콤비네이션(3)을 한다. ( 벽을 3개 세워야 하므로 ) 벽을 세우면 감시를 시작한다. 선생님리스트도 만들어서 상하좌우 감시를 한다. 감시를 하던 도중 끝까지 가거나 벽을 만나면 해당 방향의 감시는 멈추고 학생을 만나면 감시에 성공하므로 그 벽은 다시 철거하고 다른 벽을 세운다. 선생님이 모든 방향에 대해서 감시에 실패할 때까지 반복한다. 💻소스 코드 from itertools import combinations as cb def watch(): for teacher in teacher_list: x, y = teacher # 상 nx, ny = x, y while nx >..

[python] 프로그래머스 - 지형 편집

🤔문제 해결 Lv4 | 이분탐색 or 완전탐색(?) 이분탐색으로 코드를 구현했더니 효율성에서 실패했다. 그래서 한층한층 값을 저장하고 다음 층의 값을 구할 때는 이전에 저장한 층의 값을 이용하기로 했다. 먼저 2차원 행렬을 일렬로 세운고 오름차순 정렬한다. [[4, 4, 3], [3, 2, 2], [2, 1, 0]] ➡ [0, 1, 2, 2, 2, 3, 3, 4, 4] 다음 제일 낮은 층( 여기서는 0 )으로 평평하게 만들 경우를 구한다. 지형을 빼는 작업만 하면 되므로 ( 전체지형 수 - 가장 낮은층의 지형 수 ) * Q(빼는 비용) 빨간 부분을 다 지우면 높이가 0인 평평한 지형을 만들 수 있다. 값은 21칸 * Q(지우는 값) = 63 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

[python] 프로그래머스 - 외벽 점검(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 Lv 3 | 정답률: 0.6% 주어진 값의 크기가 크지 않기 때문에 완전탐색으로 해결이 가능하다. 먼저 친구를 순열로 만든다. ex) [1,2,3] 이면 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] 외벽이 원형이므로 앞과 뒤가 이어져 있다고 생각해야 한다. 취약점도 첫번째 취약점을 먼저 갈것인가 두번째 취약점을 먼저 갈것인가... 순서를 정해서 가야한다. - 첫번 째 테스트케이스의 취약점([1, 5, 6, 10])을 배열(n=12)로 나타내면 [0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0] 위의 경우는 첫번째 취약점(1)이 가장 먼저 나오는 경우 - 다음 취약점 2가 가장 먼저 나오는 경우는 0,1을 맨뒤로 옮겨주면 된다. ..

[python] 백준 - 1051. 숫자 정사각형

문제 해결 1. (부르트포스) 완전탐색 문제이다. 2. '가장 큰' 정사각형을 구하라고 했으므로 만들수 있는 최대 크기에서부터 하나씩 줄여나갔다.(시간 효율) 3. 네 꼭지점의 크기가 같을 때 return + break를 걸어주어 바로 탐색을 종료 + 난이도가 적당한 2차원배열 + 완전탐색 문제이다. 소스 코드 def find_squre(s): # 정사각형의 꼭지점의 숫자 크기가 같은 경우를 찾는다. for i in range(n-s+1): for j in range(m-s+1): if numbers[i][j] == numbers[i][j+s-1] == numbers[i+s-1][j] == numbers[i+s-1][j+s-1]: return True return False n, m = map(int, ..

[python] 백준 - 15683. 감시

문제 해결 완전탐색 시뮬레이션 1. 먼저 CCTV의 위차와 방향들을 따로 리스트에 저장해둔다 2. 각각의 CCTV마다 감시할 수 있는 방향들이 다르기 때문에 하드코딩이지만 방향을 다 설정해준다. (1) 여기서 5번 CCTV는 방향을 바꿀수 없기 때문에 처음부터 탐색할 수 있는 곳들을 모두 표기해준다. 3. DFS를 통해 모든 경우의 수를 계산해 준다. 4. 경우의 수를 하나 찾을 때마다 감시하는 영역을 표시해주어 사각지대가 최소인 부분을 찾는다. -> 뭔가 하드코딩한 것 같지만 시뮬레이션문제라 어쩔 수없는 것같다. 시뮬레이션 문제를 풀면 진이 빠지는 것 같다. 항상 너무 길다...😵 소스 코드 from copy import deepcopy def dfs(idx, maps): # idx : 몇 번째 cct..