프로그래밍 공부/코테 풀이 암기13 DFS/BFS_감시 피하기 * 시뮬레이션 -> 순열, 조합 라이브러리 활용 * 조합 활용 -> from itertools import combinations from itertools import combinations n = int(input()) # 복도의 크기 board = [] # 복도 정보 (N x N) teachers = [] # 모든 선생님 위치 정보 spaces = [] # 모든 빈 공간 위치 정보 for i in range(n): board.append(list(input().split())) for j in range(n): # 선생님이 존재하는 위치 저장 if board[i][j] == 'T': teachers.append((i, j)) # 장애물을 설치할 수 있는 (빈 공간) 위치 저장 if board[i][.. 2022. 10. 8. BFS/DFS_아기상어(삼성기출) * 완전탐색 -> BFS/DFS 활용 (반복문, 재귀함수) 문제 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램 작성 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹.. 2022. 10. 8. BFS/DFS_특정 거리의 도시 찾기 풀이 암기 최단경로 문제 풀기 전 맛보기 그래프 확인! why BFS? - 바로 옆에 있는 도로(경로) 확인이 목적 from collections import deque # 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호 n, m, k, x = map(int, input().split()) graph = [[] for _ in range(n + 1)] # 모든 도로 정보 입력 받기 for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) # 모든 도시에 대한 최단 거리 초기화 distance = [-1] * (n + 1) distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정 # 너비 우선 탐색(BFS) 수행 q = dequ.. 2022. 10. 5. DP_병사 배치하기 풀이 암기 * 하나의 수열이 주어졌을 때, 증가하는 형태의 가장 긴 부분의 수열만 남기기 * [10, 20, 10, 30, 20, 50] --> [10, 20, 30, 50]의 형태로 남기기 # 하나의 수열이 주어졌을 때, 증가하는 형태의 가장 긴 부분의 수열만 남기기 # [10, 20, 10, 30, 20, 50] --> [10, 20, 30, 50]의 형태로 남기기(가장 긴 증가하는 부분 수열) n = int(input()) array = list(map(int, input().split())) # 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환 array.reverse() # 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화 dp = [1] * n # 가장 긴 증가하.. 2022. 10. 3. 이전 1 2 3 4 다음
