연습문제
정렬_심화24) 안테나 _ python
문제링크 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 코드 # 안테나 n = int(input()) homeList = list(map(int, input().split())) homeList.sort() idx = (homeList[(n-1)//2]) print(idx)
백트래킹(Backtracking)
💡 백트래킹(Backtracking)이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 용어 설명 유망함(promising) : 진행 중인 경로가 해답을 찾을 가능성이 있음을 의미 유망하지 않음(non-promising) : 진행 중인 경로가 해답을 찾을 가능성이 없음을 의미 가지치기(pruning) : 유망하지 않은 하위 트리를 자르는 것 백트래킹 vs DFS ? 공통점 두 방법 모두 깊이 우선 탐색 (DFS, Depth-First Search)을 이용하여 탐색합니다. 재귀 함수를 사용하는데, 이 때 스택(stack) 메모리를 사용하여 작동합니다. 차이점 목적 DFS: 모든 노드를 방문하는 것이 목적입니다. 경로 ..