728x90 [알고리즘 개념정리] 3. 동적계획법(DP) **본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.** Dynamic Programming : 전체 문제를 작은 부분 문제(subproblem)로 나누어 푸는 방법 -> DP, 분할 정복,... 중복되는 부분 문제는 한 번만 계산 메모이제이션 : memoization 배열 -1로 초기화, 배열 값 음수이면 계산 후 저장, 양수이면 저장해둔 값 재활용 기저 조건(Base Case) 설정 최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해로부터 구해짐. ★ DP 문제 판별법 문제를 읽는다. 입력 조건 & 시간제한 & 메모리 제한을 확인한다. ex) 입력 조건 : 상태 개수를 정의. k=100, n=100000 -> kn=10000000 정의할.. 2022. 1. 19. [백준/C++] 10840번: 구간 성분(G1) 문제 https://www.acmicpc.net/problem/10840 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다. 이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N, M의 범위는 1 ≤ N, M ≤ 1,500 이다. www.acmicpc.net 사용한 알고리즘 2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash) -> Polynomial Rolling hash 이분 탐색 -> 참고 자료 : https://royhelen.tistory.com/36 풀이 X[26]배열에 27의 거듭제곱 수를 미리 담아둔다. (X[0]=1, X[1]=27, ... , X[2.. 2022. 1. 18. [영어 표현/예문] 40~42. have over, in the back of one's mind have ~ over : ~을 손님으로 맞이하다, (집에) 초대하다 I had that woman over for brunch. We had the mayor over. 우리는 시장을 손님으로 맞이했다. in the back of one's mind : 마음속 깊이, 마음 한 구석에 I could recognize what's in the back of his mind. 그의 속마음을 엿볼 수 있었다. 2022. 1. 18. [백준/C++] 16916번: 부분 문자열(G3) 문제 https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 사용한 알고리즘 2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash) -> Polynomial Rolling hash KMP 풀이 방법1. Polynomial Rolling hash P를 정수 p로 바꿔준다 S의 첫번째 부분 문자열을 정수 s으로 바꿔준다. s과 p가 같으면 1을 출력하고 종료한다. S의 모든 부분 문자열을 정수 s으로 바.. 2022. 1. 17. [백준/C++] 2866번: 문자열 잘라내기(G5) 문제 https://www.acmicpc.net/problem/2866 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 사용한 알고리즘 2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash) -> Polynomial Rolling hash 풀이 이차원 char배열 alphabet에 알파벳을 입력받는다. 열을 거꾸로 올라가며 hash값을 계산해서 hash배열에 담아준다. ex. 배열 alphabet : m r v i.. 2022. 1. 17. [영어 표현/예문] 37. confront confront : 닥치다, (문제나 곤란한 상황에) 맞서다 (=face up to), (위험한 상황 등에) 정면으로 부딪치다[마주치다] So, what did he say when you confronted him? 그래서 니가 증거를 들이댔을 때 그가 뭐라고그랬어? When confronted with the evidence of his guilt, he confessed. 증거를 들이대자 그는 자백했다 If it angers you that much, confront him about it. 그렇게 분하면 그에게 가서 따져라 2022. 1. 17. 이전 1 ··· 38 39 40 41 42 43 44 ··· 46 다음 728x90
