tony9402

문제 : 1,2,3 더하기 5문제 유형 : 다이나믹 프로그래밍 일단 정수 4인 경우, 1,2,3의 합으로 나타내는 방법이 왜 3개인지 알아보자. 처음엔 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수를 구해보면 아래와 같다. 3 + 11 + 32 + 22 + 1 + 11 + 2 + 11 + 1 + 21 + 1 + 1 + 1 여기서 문제 조건에 만족하지 않은 것은 2 + 2와 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 1 + 2이다.이를 어떻게 풀까.......? 정수 n이 있다고 가정해보자. n은 아래와 같이 쓸 수 있을 것이다. 1. 3 + (n - 3)2. 2 + (n - 2)3. 1 + (n - 1) 1번에서 n - 3이 3이 아닌 1과 2로 식을 전개하면 된다.3 + 1 + (n -..

문제 : 1,2,3 더하기 4 문제 유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자. 4를 1,2,3더하기로 표현해보면 3+1 2+2 1+3 2+1+1 1+2+1 1+1+2 1+1+1+1 이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자. 3+1 (1+3) 2+2 2+1+1 (1+2+1, 1+1+2) 1+1+1+1 이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까? 1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다. 한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다. 4를 가지고 예..

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 3 위 문제는 1, 2, 3 더하기 문제에서 n의 범위가 더 커졌고 모듈러 연산을 하면 되는 문제이다.따라서 이 문제는 여기에서 세운 점화식에다가 모듈러 연산만 추가 하면 된다. 1234567891011121314151617181920212223242526272829#include long long dp[1000001] = {0, 1, 2, 4 }; const long long mod = 1000000009; long long DP(int n){ if (n

단순 구현 문제이다. 한 문장에서 정수를 뽑고 비교연산자를 뽑아서 계산하면 된다. input data를 보면 규칙이 있다. 3 != 3을 보면 '3' + ' ' + '!' + '=' + ' ' + '3'이다. -3 > 3을 보면 '-' + '3' + ' ' + '>' + ' ' + '3'이다. 이 두 가지를 잘 보면 문장을 처음부터 읽을때 -가 나오거나 숫자가 나오면 그건 숫자라는 것을 알 수 있다. 이 숫자의 끝은 숫자가 나오다가 띄어쓰기가 나온다면 그 숫자가 끝난 부분이다. 그 다음엔 비교 연산자를 읽어야 하는데 그것은 단순히 '!', '>', ''}; int main(){ bool check = false; bool ans = false; int count = 1; int ml, mr; while ..

성능 분석과 측정 프로그램의 평가 기준 - 우리가 원하는 작업을 하는가? - 원래 작업의 명세에 부합해서 정확히 작동하는가? - 문서화가 되어 있는가? - 논리적 작업 단위를 수행하는 기준으로 함수가 생성되었는가? - 코드가 읽기 쉬운가? 성능 평가(performance evaluation) - 성능 분석(performance analysis) => 사전 예측 - 성능 측정(performance measurement) => 이후 검사 공간 복잡도 공간복잡도 - 프로그램을 실행 시켜 완료하는 데 필요한 메모리 양 - 고정 부분 => 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간 - 가변 부분 => 특정 문제의 인스턴스에 따라 크기가 달라지는 변수, 순환 스택 공간 - 프로그램 P의 공간 유고 ..

시스템 생명 주기(System Life Cycle) 요구사항 - 프로젝트들의 목적을 정의한 명세들의 집합 - 입력과 출력에 관한 정보를 기술 분석 - 문제들을 다룰 수 있는 작은 단위들로 나눔 설계 - 추상 데이터 타입(abstract data type) 생성 - 알고리즘 명세와 설계 기법 고려 정제와 코딩 - 데이터 객체에 대한 표현 선택 - 수행되는 연산에 대한 알고리즘 작성 검증 - 정확성 증명 : 수학적 기법들을 이용해서 증명 - 테스트 : 프로그램의 정확한 수행 검증, 프로그램의 성능 검사 오류 제거 - 독립적 단위로 테스트 후 전체 시스템으로 통합 객체 지향 설계 구조적 프로그래밍 설계와의 비교 - 유사점 : 분할 - 정복 기법 : 복잡한 문제를 여러개의 단순한 부분 작업으로 나누어 각각을 개..