분류 전체보기40 [알고리즘] 동적계획법(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. [SQL] inner join, 특정 속성이 최대인 행 고르는 where 조건 프로그래머스 문제 select concat('/home/grep/src/', f.board_id, '/', f.file_id, f.file_name, f.file_ext) as file_path from used_goods_board as b inner join used_goods_file as f on b.board_id = f.board_id where b.views = (select max(views) from used_goods_board) order by f.file_id desc; 1. inner join 문의 기본 구조 -> inner join은 그냥 조인이라고도 함. -> 조인 조건에 해당하는 각 테이블의 row 합치는 연산이라고.. 2024. 1. 26. [알고리즘] 코딩테스트란? * 한국외대 코테 대비반 오리엔테이션 코딩테스트란? 문제 상황과 (입력, 출력) 예시가 주어졌을 때, 코드를 작성하여 제한된 시간 안에 출제자가 준비한 입력에 대한 올바른 답이 나오도록 하는 시험. 시간복잡도 계산하기 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 ··· 3 4 5 6 7 다음
