분류 전체보기 (83) 썸네일형 리스트형 [ Python ] 15657번 : N과 M (8) 코딩테스트 해설백준 15657번: N과 M (8)문제 유형 : 백트래킹작성 코드import sysN, M = map(int, sys.stdin.readline().rstrip().split(" "))sequence = sorted(map(int, sys.stdin.readline().rstrip().split(" ")))def backtrack(start, current): if len(current) == M: print(" ".join(map(str, current))) return for i in range(start, N): backtrack(i, current + [sequence[i]])backtrack(0, [])접근 방식백트래킹 방식을 적용하.. [ Python ] 15656번 : N과 M (7) 코딩테스트 해설백준 15656번: N과 M (7)문제 유형 : 백트래킹작성 코드import sysN, M = map(int, sys.stdin.readline().split(" "))sequence = sorted(map(int, sys.stdin.readline().split(" ")))def recursion_tree(current_select: list, depth: int) -> list: if depth == M: return [current_select] results = [] for num in range(N): results.extend(recursion_tree(current_select + [num], depth + 1)) return re.. [ Python ] 15655번 : N과 M (6) 코딩테스트 해설백준 15655번: N과 M (6)문제 유형 : 백트래킹작성 코드import sysN, M = map(int, sys.stdin.readline().split(" "))sequence = sorted(map(int, sys.stdin.readline().split(" ")))def recurion_tree(current_select: list, depth: int) -> list: if depth == M: if all([current_select[i] 접근 방식재귀를 이용해 각 상위 요소의 하위 요소의 트리를 구성하도록 하였다.우측값이 좌측값보다 항상 커야 하기 대문에, all을 이용해 크기 를 M-1 만큼 반복하도록 하였다.개선 사항함수의 오타를 수정 해야한다.list.. [ 알고리즘 ] 백트래킹(BackTracking) 백트래킹 이란? 해결책으로 이어질 가능성이 있는 모든 경로를 탐색하면서, 각 단계에서 그 경로가 목표를 달성할 수 없다고 판단되면 이전 단계로 돌아가 다른 경로를 시도하는 방법입니다. 백트래킹의 필요성 다양한 문제(특히 최적화 문제와 결정 문제)에서 최적의 해를 찾거나 해가 존재하는지를 확인할 때 사용. 백트래킹의 원리 백트래킹의 기본 개념선택: 가능한 옵션 중 하나를 선택.제약: 선택이 문제의 조건을 만족하는지 검사.목표: 해결책에 도달했는지 확인.백트래킹과 다른 알고리즘과의 비교- 브루트 포스 알고리즘브루트 포스(Brute Force)는 문제의 모든 가능한 경우를 차례대로 시도해보며 정답을 찾는 방법입니다. 가장 단순하고 직관적인 접근 방식이지만, 가능한 모든 경우를 검토해야 하므로 문제의 크기가.. [ 알고리즘 ] 순열과 조합 순열과 조합이란?순열(Permutation)과 조합(Combination)은 기본적인 조합론의 개념으로, 요소들의 집합에서 일부를 선택하여 배열하는 다양한 방법을 나타냅니다.순열 (Permutation)순열은 집합에서 일정 수의 요소를 취하여 일렬로 나열하는 것을 의미합니다. 순서가 결과에 영향을 미치기 때문에, 같은 요소들을 다른 순서로 나열하면 다른 순열로 간주됩니다.예시: 집합 {A, B, C}에서 2개를 선택하여 나열하는 순열은 다음과 같습니다ABBAACCABCCB이 경우, 선택된 요소의 순서가 결과에 영향을 미치므로 AB와 BA는 서로 다른 순열로 취급됩니다.계산 방법: n개의 요소 중에서 r개를 선택하는 순열의 개수는 nPr로 표현되며, n! / (n-r)!로 계산됩니다. 여기서 !는 팩토리얼.. [ 알고리즘 ] 재귀(Recursion) 재귀란? 재귀(recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 재귀재귀(Recursion)는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다. 주로 복잡한 문제를 더 작은 부분 문제로 나누어 해결할 때 유용합니다. 재귀 함수는 기본적으로 두 가지 부분으로 이루어져 있습니다 기저 조건(Base Case)함수가 자기 자신을 호출하여 문제를 더 작은 부분으로 나누는 단계입니다.def factorial(n): # 기저 조건: n이 1 이하일 때, 1을 반환하여 재귀를 멈춤 if n 재귀 단계(Recursive Step)함수가 자기 자신을 호출하여 문제를 더 작은 부분으로 나누는 단계입니다.def factorial(n): # 기저 조건: n이 1 이하일 때, .. [ Python ] [1차] 비밀지도 (17681) 코딩테스트 해설2018 KAKAO BLIND RECRUITMENT : [1차] 비밀지도문제 유형 : 구현작성 코드def solution(n, arr1, arr2): answer = [] for i, j in zip(arr1, arr2): line = bin(i|j)[2:].replace("1", "#").replace("0"," ") if len(line) 접근 방식정수 배열 arr1, arr2의 각 요소를 or 연산 한 결과를 binary형태로 바꾸고, 문자열 0b를 제거하기 위해 [2:] 로 슬라이싱을 합니다.그리고 1을 # 으로 0으로 " " 으로 표현합니다.추가로 정해진 길이 n보다 생성된 line이 짧을 경우, 좌측에 공백을 n - len(line) 만큼 생성.. [ Python ] 15654번 : N과 M (5) 코딩테스트 해설백준 15654번: N과 M (5) 문제 유형 : 백트래킹작성 코드import sysN, M = map(int, sys.stdin.readline().split(" "))sequence = sorted(map(int, sys.stdin.readline().split(" ")))def recurion_tree(current_select: list, depth: int) -> list: if depth == M: return [current_select] results = [] for num in range(N): if num not in current_select: results.extend(recurion_tree(current_.. 이전 1 2 3 4 5 6 7 ··· 11 다음
