본문 바로가기

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.

티스토리툴바