전체 글 (30) 썸네일형 리스트형 [백준] 1563번 개근상 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 브루트포스로 문제 풀이를 생각해보면 시간 초과가 나기 때문에 메모이제이션을 이용해서 풀이해보도록 한다. N이 1000이고 지각 2번, 결석 3번에 대한 모든 조합을 생각해보면 서로 다른 알파벳 3개 중에 1번은 1000개 중복, 2번은 2개 중복, 3번은 3개 중복이므로 #중복조합 은 n.H.r={n+r-1).C.r -> 이가 된다. ( '.' 콤마는 순열, 조합 기호 표시를 가시적으로 잘 보여주기 위해 임의로 삽입 ) 서로 다른 (n + r - 1)개의 수 중, r개를 뽑는 경우의 수 )로 1002.C.2 가 되고 1000000 연산이 필요한데 n이 1 ~ 1000 에 따른 모든 수를 구하기 위해서는 시간 초과가 나게 됩니다.. [백준] 4883번 삼각 그래프 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 이유는 (100,00, 3) 의 그래프를 1초 ( 약, 1억번의 연산 ) 내에 전부 탐색하려면 메모이제이션이 반드시 필요하다. (2) DP 배열 정의 -> DP[N][4] : N행, 1 - 3 열까지의 정점까지는 오는데에 필요한 최소 비용 (3) 풀이 방법 -> 아래 그래프와 같이 정점 -> 정점으로 가는 방향은 (아래, 오른쪽, 오른쪽 아래, 왼쪽 아래) 이므로 4가지 방향에 대해서 탐색을 한다. 그래프 범위 내에 있는 경우만 탐색하면된다. (4) 함정 -> 마지막으로 입력받는 0이 처음에 입력받는 수열 길이 N을 말하는 것 ( 무한루프 사용으로 해결 ) 2. Source Code #include #include #include #de.. [백준] 2342번 Dance Dance Revolution 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 전봇대 A와 연결되어 있는 전깃줄에 대해서 정렬하고 LIS를 수행한다. (2) DP 배열 정의 -> DP[idx][left][right] : idx 까지 발이 left, right 위치에 있는 경우 들어가는 비용의 최솟값 (3) 풀이 방법 -> 이동 조건에 따른 힘을 계산해주는 함수를 정의, 구현한다. 조건을 천천히 따라가면 충분히 쉽게 구현 가능하다. 조건이 충족하는 경우, 기저 사례를 구분해준다. 2. Source Code #include #include #include #include #define MAX 100001 using namespace std; int order[MAX]; // idx 까지 left, right의 발 위치.. [백준] 2565번 전깃줄 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> 전봇대 A와 연결되어 있는 전깃줄에 대해서 정렬하고 LIS를 수행한다. (2) 풀이 방법 -> (1)번에서 설명한 방식대로 접근하면 쉽게 해결 가능하다. 2. Source Code #include #include #include using namespace std; int n; vector a;// first : A // second : B int dp[101]; int main() { int x, y;// x -> y cin >> n; for (int i = 1; i > x >> y; a.push_back(make_pair(x, y)); } // 정렬 수행 sort(a.begin(), a.end()); // LIS 수행 for (int.. [백준] 11053번 가장 긴 증가하는 부분 수열 1. Approach (1) 다이나믹 프로그래밍으로 접근한다. -> KOI 유전자가 될 수 있는 최대 길이를 문자열의 처음, 끝부터 분할해나가면서 확인한다. (2) DP 배열 정의 -> dp[i] 는 i 번째 인덱스 까지의 배열 중 가장 긴 부분수열의 길이. (3) 풀이 방법 -> 내부 for문을 1부터 j - 1 까지 돌리면서 a[j] dp[i] ( 현재 i 인덱스의 가장 긴 부분수열의 길이 보다 큰 경우에) 2. Source Code #include #include using namespace std; int n; int a[1001]; int dp[1001]; int main() { cin >> n; for (int i =.. [CERT C/선언과 초기화] (3) 기억클래스 취약성 의미 기억클래스란 변수의 값이 어떤 종류의 메모리에 저장되는지를 지정하는 것을 의미한다. auto, register, static으로 구성되어있다. auto 변수 함수, 블록 내부에서 사용되고 흔희 local 변수라고 불린다. 기억 클래스가 명시되지 않고 선언된 변수는 모두 자동 변수이다. 스택 공간을 사용하며, 함수나 블록에서 기억 영역이 확보되고, 벗어나면 소거됩니다. ** return 문에서 return 되는 값은 외부에서 기억영역을 호가보하게된다. register 변수 CPU가 연산 시 데이터를 임시로 저장하는데 사용하는 작고 빠른 기억장소이다. 2개까지만 선언 가능하고, 초과된 변수는 AUTO 변수로 지정된다. 레지스터에는 주소가 없으므로 참조가 불가능하다. static 변수 프로그램이 종료될 .. [CERT C/선언과 초기화] (2) 가변인자 함수 사용 시 주의할 점 의미 가변인자 함수는 인자의 개수가 정해지지 않은 함수를 의미한다. 예를들면 printf, scanf 함수가 가변인자 함수이다. int printf(const char*, ...); int scanf(const char*, ...); 동작 방식 상황에 따라 들어오는 인자의 개수가 다르므로 에 정의 되어있는 함수를 이용해서 다룬다. 1. va_list args 가변 인자 목록, 가변 인자의 메모리 주소를 저장하는 포인터이다. va_list : char *형 args : argument를 가리키는 포인터 2. va_start(args, 마지막 고정인수) 가변 인자를 가져올 수 있도록 포인터를 설정한다. 3. va_arg(args, type) 가변 인자 포인터에서 특정 자료형 크기만큼을 가져온다. 4. va_.. [CERT C/선언과 초기화] (1) 코드의 가독성을 높이기 위해 타입 정의를 사용하라 의미 C 언어 같은 경우, 함수 포인터를 이용한 함수들은 타입을 읽을 때 가독성이 떨어지는 경우가 많다. 아래 signal 함수로 예를 들어본다. void(*signal(int signum, void (*handler)(int)))(int) signal 함수를 반환하는 부분과 매개변수 부분으로 나누어보면 (1) signal 함수는 두 개의 파라미터를 가진다. signal(int signum, void (*handler)(int)) (2) signal 함수가 반환하는 값은 void (*)(int); -> 함수 포인터 형이며 반환 값이 없고 int 매개변수를 받는 함수를 가르리키는 포인터이다. 문제 코드 1. 함수의 선언이 읽기도 어렵고 이해하기 힘들다. #include int (*getFunction(in.. 이전 1 2 3 4 다음
