ebson

1. 집의 좌표들과 치킨집 좌표들을 각각 리스트에 저장 2. combinations를 사용해 치킨집 좌표 리스트에서 추출한 M개의 치킨집 좌표들을 순회하면서 아래(3,4,5)를 반복 3. 집의 좌표 목록을 순회 4. 집에서 치킨집까지 거리를 계산하고 최소 치킨거리를 저장 5. 모든 집들의 최소 치킨거리를 더한 값을 최소 치킨거리 리스트에 저장 6. 최소 치킨거리 리스트에서 최소값을 출력 N, M = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(N)] chickens = [] homes = [] for y in range(N): for x in range(N): if board[y][x] == 2: chi..

1 전체 영역에서 최고, 최저 높이 추출 2 최저-1 -> 최고 높이 까지 검사하면서 아래 반복 2.1. board 를 순회하면서 미방문 안전지대의 경우 안전영역개수 cnt 증감하고 2.2. dfs 방식으로 탐색하면서 미방문 상태이면서 안전한 좌표를 방문체크 2.3. 안전영역개수 cnt를 cnt_list에 저장 3. cnt_list에서 최대값을 출력 N = int(input()) board = [list(map(int, input().split())) for _ in range(N)] import sys sys.setrecursionlimit(10**9) dy = (1, -1, 0, 0) dx = (0, 0, 1, -1) def dfs(y, x, h): for i in range(4): ny = y +..

1. combinations를 import하여 가능한 모든 조합에 대해 아래를 반복 1.1. startT과 linkT 리스트를 초기화 1.2. start_tot 과 link_tot을 저장 1.3. diff_list에 두 점수의 차를 저장 2. diff_list의 최소값을 출력 N = int(input()) board = [list(map(int, input().split())) for _ in range(N)] nums = [] for n in range(N): nums.append(n) from itertools import combinations from itertools import permutations diff_list = [] for combi in combinations(nums, N//2)..

1. nums에 순서대로 숫자들을 저장 2. +, -, *, / 연산자를 개수만큼 qs 배열에 저장 3. 문제 조건에 맞게 divide 함수를 정의 4. permutations를 사용해 가능한 모든 연산자들의 순열에 대해 아래를 반복 4.1. ans에 nums[0]을 저장 4.2. 연산자들의 순열을 순회하면서 +, -, *, divide 연산을 수행한 결과를 ans으로 갱신 4.3. ans와 min_ans, max_ans를 각각 최소, 최대 비교해 min_ans, max_ans를 갱신 5. max_ans를 출력하고 다음줄에 min_ans를 출력 N = int(input()) nums = list(map(int, input().split())) ops = list(map(int, input().split(..

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 7: PART 2. 알고리즘 유형 분석 - 동적계획법 Dynamic Programming 43강 ~ 50강 내용 요약입니다. Chapter 6. 동적 계획법 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복함 분할 정복과 비슷한 느낌임 # DP 구현 2가지 Top-down : 구현-재귀 저장방식-메모이제이션(Memoization) Bottom-up : 구현-반복문 저장방식-타뷸레이션(Tabulation) # Memoization - 한 번 구한 답들은 저장해두자 부분 문제들의 답을 한 번 구했으면 또 구하지 않도록(중복연산 방지) Cache에 저장해두고 다음부턴..

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 7: PART 2. 알고리즘 유형 분석 - 이분탐색 Binary Search 37강 ~ 42강 내용 요약입니다. 1. 이진 탐색 Binary Search 1.1. 탐색 전에 반드시 정렬되어 있어야 한다. 1.2. 살펴보는 범위를 절반 씩 줄여가면서 답을 찾는다. 1.3. 정렬 O(NlogN) + 이진탐색 O(logN) => 결과적으로 O(NlogN) 1.4. 미리 정렬되어 들어오면 이진탐색만 하면 되므로 O(logN) 1.5.일차원 배열에서 탐색행위가 1회일때는 선형탐색이 유리하지만(O(N) O(NlogN)) 2. b..

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 6: PART 2. 알고리즘 유형 분석 - DFS, BFS, 백트래킹, 32강 ~ 36강 내용 요약입니다. # 예제문제(1) 길찾기 문제 # 보통 위, 아래, 왼, 오 4방향이 많다. # 체스 등 응용 문제도 있다. # 방향값을 미리 코드로 짜두고 for문으로 순회하는 기법을 익혀두자 dy = (0, 1, 0, -1) dx = (1, 0, -1, 0) chk = [[False] * 100 for _ in range(100)] N = int(input()) def is_valid_coord(y, x): return 0

아래 내용은 Udemy 알고리즘 코딩 테스트 입문부터 합격까지 (Feat. 컴공선배 알고리즘캠프) 강의 섹션 6: PART 2. 알고리즘 유형 분석 - DFS, BFS, 백트래킹, 25강 ~ 31강 내용 요약입니다. #DFS, BFS, 백트래킹 1. 그래프(Graph) 1.1. 그래프 실생활 예 - 지도, 네비게이션, 노선도, SNS 관계도, VCS(버전관리 시스템) - 지하철 노선도를 예로, 그래프에서는 각 역을 Vertex(=node)라고 하고 연결선을 edge 라고 한다. - 그리고 Vertex(=node)를 V 또는 N개, edge를 E 또는 M개라고 주로 표현한다. 1.2. 그래프 종류1 - 무방향(양방향) 그래프, 방향 그래프 1.3. 그래프 종류2 - 순환 그래프(Cyclic Graph), ..