Python/백트래킹3 [Algorithm] 삼성 SW 역량테스트 2017 하반기 오전 1번 문제 조삼모사, 코드트리 | 파이썬 ※ 조삼모사https://www.codetree.ai/training-field/frequent-problems/problems/three-at-dawn-and-four-at-dusk/description?page=1&pageSize=20&tier=1%2C10 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai[문제]n개의 일이 주어질 때 이를 아침과 저녁으로 2n개씩 나누어처리하고자 합니다.일마다 특성이 다르기 때문에 같이할 때의 업무 강도를 나타내는 업무 간의 상성 Pij가 존재합니다. 예를 들어 업무 상성이 다음과 같이 주어질 때,1, 2번 일을 아.. 2024. 8. 12. [Algorithm] Backtracking(백트래킹) 순열 및 조합 구현하기 itertools 우선 순열과 조합의 차이를 알아보자. 순열 : 원소들의 순서를 고려하여 나열하는 것 (원소의 순서가 다르면 다른 순열로 취급) 조합 : 원소들의 순서를 고려하지 않고 나열하는 것 (선택된 원소의 순서는 고려되지 않음) 파이썬 라이브러리 중 하나인 itertools를 사용하면 조합과 순열을 쉽게 구할 수 있다. from itertools import permutations, combinations arr = [1,2,3] k = 2 npr = list(permutations(arr, 2)) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)] ncr = list(combinations(arr, 2)) # [(1, 2), (1, 3), (2, 3)] 그러나.. 라이브러리.. 2024. 4. 13. [Algorithm] Backtracking(백트래킹) 백트래킹이란? 완전탐색처럼 모든 경우를 탐색하나, 중간 과정에서 조건에 맞지 않는 케이스를 가지치기하여 탐색 시간을 줄이는 기법이다. 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. 백트래킹의 특징 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다. 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에 재귀를 사용하는 경우가 많다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 가지치기란? 지금의 경로가 해가 될 것 같지 않으면 그 전으로 돌아가는 것이다. 불필요한 부분을 쳐내는 것으로 되돌아간 후 다시 다른 경로를 검사한다. 백트래킹의 적용 N의 크기가 작을 때 보통 20 이하 (주로 재귀함수로 구현하기 때문) .. 2024. 1. 5. 이전 1 다음
