CS21 [알고리즘] 완전탐색이란? 완전탐색이란? 문제를 해결할 수 있는 가장 naive한 방법 완전탐색은 모든 가능한 경우에 대해서 탐색을 하는 것 어떤 조건에 맞는 객체를 찾아내기 위해서 가능한 모든 객체를 탐색한다. 언제 이 알고리즘을 사용해야 하는가? 1. 더 효율적인 알고리즘 방법이 생각이 안날 때 2. 기준(변수)을 잡고 그 기준에 따라 모든 경우의 수를 선택할 수 있을 때 3. 시간 복잡도를 만족할 때 어떻게 사용해야 하는가? 기준을 잡아야 함 -> 모든 객체를 선택할 수 있는 기준으로 전체 객체를 빠짐없이 선택해야함 선택한 개체가 조건에 맞는지 확인하기 완전탐색 구현 방법 for문으로 구현 재귀함수로 구현 코드트리 완전탐색 종류 자리 수 단위로 완전탐색 구간 단위로 완전탐색 자리 마다 숫자를 정하는 완전탐색 물체 단위로 완전.. 2024. 2. 14. [알고리즘] 동적계획법(Dynamic Programming)이란? * 한국외국어대학교 신찬수 교수님의 알고리즘 강의를 들으면서 정리한 내용입니다. 교수님의 강의와 유튜브, 강의 노트를 참고하여 정리했습니다. dp 알고리즘이란? 동적 계획법이란 복잡한 문제를 겹치는 부분 문제로 분할하여 분할된 문제의 해답을 기록하고 더 큰 문제를 해결할 때 재사용하는 일종의 접근 방식이다. 일반적인 재귀 함수 문제나 분할정복과 비슷한 면이 있지만, 한번 계산한 결과를 dp 테이블에 저장해놓고 다음번에 필요한 경우 dp테이블에서 참조하여 사용하기 때문에 반복되는 계산을 피할 수 있어 효율적임. 언제 dp알고리즘을 사용하는가? 1. 겹치는 부분문제로 나뉘어지고 2. 최적부분구조를 가지고 있을 때 : 부분문제에서 구한 최적 결과가 전체 문제에서도 최적 결과를 낼 수 있는 경우 => 문제를 만.. 2024. 2. 14. [알고리즘] 분할정복법(Divide and Conquer)이란? 분할정복법이란? 풀기 어려운 문제를 작은 크기의 부분 문제로 재귀적인 분할을 한 후 부분 문제의 해답을 다시 합병하여 답을 얻는 접근 방법이다. 언제 분할정복법을 사용하는가? 1. 최적 부분 구조를 가지고 있을 때 => 문제를 만났을 때 1. 부분 문제로 쪼개지는가? 2. 부분 문제의 해답이 전체 문제의 해답에 유효한가? 어떻게 분할정복법을 사용하는가? 1. 해답의 구조를 파악해 어떻게 subproblem(부분문제)으로 나눌 지(최적 부분 구조 만족하도록) 결정한다. -> 일반화된 n번째에 대한 생각 2. 분할한 부분 문제의 해답을 종합해 전체 문제의 답을 구한다. 예시 예시1) n개의 수 중에서 최대 값 구하기(find_max) def find_max1(A): if len(A) == 1: return .. 2024. 2. 14. [알고리즘] 백트래킹 - 경우의 수 문제 원하는 조합과 순열 만드는 방법1. for문으로 구현하는 방법과2. 재귀함수로 구현하는 방법! 원하는 숫자의 조합이나 순열을 만들고, 객체를 선택하는 방법이다! 경우의수 문제는 중복순열순열조합 중복순열n개 중 하나를 m번 선택하기 중복 O, 순서 Ofor 문으로 구현m = 4n = 5# 1번 for 문 구현 -> 4중 반복문으로 구현되어야함 num_arr = list(range(1, n+1))for i in range(n): for j in range(n): for x in range(n): for y in range(n): print(num_arr[i], num_arr[j], num_arr[x], num_arr[y]) 재귀함수로 구현# .. 2024. 2. 14. [알고리즘] 백트래킹이란? 백트래킹이란? (What) 탐색 알고리즘 중 하나로 DFS처럼 재귀함수로 구현됨 (DFS와 같은 순서로 탐색) 탐색을 하다가 조건에 맞지 않으면 이전 단계로 돌아가 다시 탐색을 하며 답을 찾아 나가는 알고리즘. 언제 사용하나? (Why) 완전탐색처럼 하나하나 탐색해야 하는데 조건으로 가지치기를 할 수 있을 때 예시 최적화 문제 : 수학 혹은 컴퓨터 과학에서 모든 테스트 케이스에 대해 답을 찾는 최적의 해법을 찾는 문제 N-Queen 문제 미로 찾기 문제 완전탐색과 다른점은? 완전탐색처럼 트리를 탐색하지만 조건에 맞지 않는 경우는 가지치기 함. DFS와 차이점은? DFS는 찾는 노드가 나올 때까지 최대한으로 들어감. 백트래킹은 조건에 따라 중간에 가지치기를 하는 것이 특징. 적절하게 가지치기를 해서 필요하.. 2024. 2. 14. [알고리즘] 코딩테스트란? * 한국외대 코테 대비반 오리엔테이션 코딩테스트란? 문제 상황과 (입력, 출력) 예시가 주어졌을 때, 코드를 작성하여 제한된 시간 안에 출제자가 준비한 입력에 대한 올바른 답이 나오도록 하는 시험. 시간복잡도 계산하기 1억번 -> 1초 시간제한 N < 10 : 시간 복잡도 신경 안써도 됨. N < 20 : 2^n 가능 N < 100 : n^4 가능 N < 500 : n^3 가능 ... 몇중 for 문까지 쓸 수 있는지에 대한 감 바로 잡기 코딩테스트 문제 종류 lv1 문제에서 원하는 그대로 구현하여 원하는 답 구하기 - 시뮬레이션 - Brute Force (완전탐색) - Bactracking lv2 알고리즘을 문제 상황에 그대로 적용하여 풀기 - BFS - DFS - DP lv3 여러 테크닉을 활용하여 .. 2024. 1. 21. 이전 1 2 3 4 다음
