algorithm (35) 썸네일형 리스트형 수학 1. 나머지 연산 2. 최대공약수와 최소공배수 3. 소수 4. 에라토스테네스의 체 5. 골든바흐의 추측 6. 관련문제 수학문제 복습! 1. 나머지 연산(Modular Arithmetic) 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다. 더보기 예를 들어, 다이나믹 문제를 풀때 경우의 수가 너무 큰경우 int값이나 long 값을 넘어서, 값을 처리를 하기 위해서 큰 정수값(big integer)을 구현하기 보다는 몇으로 나눈 나머지를 처리하라는 문제가 많다. (A+B) mod M = ((A mod M) + (B mod M)) mod M (AXB) mod M = ((A mod M) X (B mod M)) mod M 나누기의 경우에는 성립하.. 다이나믹 프로그래밍[Dynamic Programming] 연습하기 좋은 문제 및 풀이 다이나믹 프로그래밍[Dynamic Programming] 연습하기 좋은 문제 및 풀이 알고리즘 문제풀이에서 벡터의 사용은 매우 좋은것 같다. 알고리즘을 간략하고 이해하기 쉽게 표현할 수 있다. 예를들어 d배열에서 최댓값을 찾는 등을 한줄로 표현할 수 있다. cout temp) ret = temp; } if (n % 2 == 0) { temp = go(n / 2) + 1; if (ret > temp) ret = temp; } db[n] = ret; return ret; } int main(void) { int x; int cnt=0; cin >> x; cout > x; for (int i = 2; i n; db[1] = 1; db[2] = 2; for (int i = 3; i n; db[1] = 1; db.. 다이나믹 프로그래밍[Dynamic Programming] 1. 다이나믹 프로그래밍이란? 2. 다이나믹 프로그래밍의 속성 3. 다이나믹 문제 푸는 방법 4. 다이나믹 문제 풀이 전략 5. 다이나믹 프로그래밍 문제 1. 다이나믹 프로그래밍이란? 다이나믹 프로그래밍 :Dynamic Programming 큰 문제를 작은 문제를 나눠서 푸는 알고리즘 1940년대 수학자인 Richard Bellman은 'Dynamic Programming'이란 용어를 사용했다. 그는 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, '동적(Dynamic)'이다라는 개념(idea)이 전달되길 원했다. 큰 문제 안에 작은 문제가 중첩되어있는 문제를 해결하는 데 사용하는 계획법(Programming)인것이다. 2. 다이나믹 프로그래밍의 속성 알고리즘 측면에서 다이나믹.. 브루트 포스[1]:순열 (Brute Force[1]:Permutation) 암호학에서의 브루트 포스(brute force attack)가 아닌 알고리즘의 브루트 포스(brute force search)에 관한 것을 작성한다. 브루트 포스(brute force) brute: 무식한, force: 힘 무식한 힘으로 해석되며 즉, 무식하게 다해보는 것이다. 완전탐색 알고리즘: 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 이러한 브루트 포스방법 중에서 순열에 관해서 소개를 하려고 한다. 순열(permutation) 수학에서, 순열 또는 치환은 서로 다른 n개의 원소에서 r(≤n)개를 뽑아 한 줄로 세우는 경우의 수이며, nPr로 나타낸다. 순서가 부여된 임의의 집합을 다른 순.. 런타임에러 다이나믹 프로그래밍문제를 풀다보니 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int a[100001]; int coaunt = 0; int dp(int num) { if (num == 1) return 0; if (a[num] != 0) return a[num]; //cout 자료구조 : 문자열 1. 문자열의 정의 스트링(string)이라고도 한다. 이러한 기호는 미리 정의된 집합이나 음소 문자에서 선택한다. 프로그래밍에서 문자열은 일반적으로, 요소가 문자 인코딩과 관련된 문자를 대표하는 일련의 자료값을 저장하고 있는 자료형으로 이해할 수 있다. 여기서 문자 인코딩의 경우 더 일반적인 배열 자료형과 차이가 있다. 이러한 환경에서 'binary string'과 'byte string'이라는 용어는 저장된 자료가 반드시 텍스트를 표시하지 않아도 되는 문자열을 표시하는 데 사용된다. 문자열 자료형으로 선언된 변수의 경우, 미리 정의된 어느 정도의 기호를 소유할 수 있는 메모리에 기억 자료를 할당하는 것이 보통이다. 문자열이 소스 코드에 보이면 그 문자열을 string literal이라고 일컫는다. 대.. 자료구조 : 덱(deque) 1. 덱의 정의 덱(deque, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다. 양 끝에서만 데이터를 넣고 양 끝에서 뺄 수 있는 자료구조 2. 덱의 함수 push_front : 덱의 앞에 데이터를 넣음 push_back : 덱의 뒤에 데이터를 넣음 pop_front : 덱의 앞에서 데이터를 뺌 pop_back : 덱의 뒤에서 데이터를 뻼 front : 덱의 가장 앞에 있는 데이터 back : 덱의 가장 뒤에 있는 데이터 3.덱의 구현 스택과 큐를 합친것과 같음 4.덱 관련 문제 풀이 백준 10866번 덱 : https://www.ac.. 자료구조 : 큐(queue) 1. 큐의 정의 큐(queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 한쪽 끝에서만 데이터를 넣고 다른 한쪽 끝에서만 데이터를 뺄 수 있다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 2. 큐의 함수 push : 큐에 자료를 넣음 pop : 큐에서 자료를 뺌 front : 큐의 가장 앞에 있는 자료 back : 큐의 가장 뒤에 있는 자료 empty : 큐가 비어있는지 아닌지 size : 큐에 저장되어있는 데이터의 개수 C++의 경우 STL의 queue,.. 이전 1 2 3 4 5 다음
