맞왜틀

🤔문제 해결 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 =..

🤔문제 해결 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 >..

🤔문제 해결 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 이제 일렬로 세운 리스트를 하나하나 탐색한다. ( 맨앞은 했으니..

🤔문제 해결 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을 맨뒤로 옮겨주면 된다. ..

문제 해결 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, ..

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