Looking closely, thinking further

* 복습 겸 기록을 위해 작성한 포스트 입니다. 1. DP란, 결국 완전탐색의 일종이다. 또한 점화식을 만들 수 있어야 한다. N번째 값에 대한 어떠한 연산이 N-1 값에 대한 동일한 연산, N-2 값에 대한 동일한 연산으로 나뉠 수 있어야 한다. 어떠한 연산을 함수 f(N) 이라고 하면, f(N) = a1 * f(N-1) + a2 * f(N-2) + ... (for 임의의 상수 a1, a2,...) 형태로 표현되어야 한다. 이렇게 생각해볼 수 있는 문제들을 풀때 Dynamic Programming 기법을 사용하는 것이다. 2. DP의 조건 1. 참조 투명성을 가져야 한다. 2. 겹치는 부분 문제(연산)가 존재해야 한다. 3. 최적 부분 구조를 가지고 있어야 한다. 1번 조건인 참조 투명성은, 문제를 해..

* 최대 시행 횟수가 1,000,000개가 넘어가는 프로그램에 시간복잡도가 n^2인 로직을 넣으면 BOJ에서는 바로 시간초과를 낸다. 따라서 더 효율적인 로직으로 소수를 구해야 하는데, 이때 사용될 수학 원리가 바로 '에라토스테네스의 체'이다. * 에라토스테네스의 체란, 어떤 수 n보다 작은 소수들을 모두 구할 때, 2 M >> N; int* a = new int[N](); for (int i = 1; i

백준 1436번 문제, 영화감독 숌 666이라는 문자열을 가지고 있는 수 중 N번째로 작은 수를 출력하는 문제이다. C++ string 클래스에 대한 이해가 부족하여 빙빙 돌아가는 풀이로 풀게되었다. 총평) * string class 의 to_string : to_문자열 * 아스키코드 6과 char type '6'을 헷갈리면 안된다(문자와 숫자를 비교할 때 어떻게 비교되는지 신경쓰기). string class의 find 멤버함수를 직접 구현해놓은(?) 느낌이다. #include #include using namespace std; int main() { int N; cin >> N; string input; bool deter = false; int hellcount = 0; for (int i = 66..

Baekjoon 문제풀이의 기록을 남기기 위해 github repository를 생성했다. 근 1달간 풀었던 문제들을 4/8일자로 한꺼번에 올렸으며, 앞으로 매일 풀 문제들을 이곳에 계속 upload할 것이다. 문제를 보고 생각해낸 로직으로 바로 풀리지 않을 때는, 새로 배운 개념들과 feedback을 정리해 당일 내 blog에 upload할 것이다.

**배열 - 평균은 넘겠지 *review - cout으로 소수점 설정하는 방법 *총평 - for문을 남발하며 코드를 작성하다가 infinite loop에 빠져버렸다. 오류찾느라 처음부터 다시 코드를 짜면서 가독성이 곧 효율성이라는 걸 새삼 깨달았다. - double과 integer 자료형 가지고 연산할 때 오류 범하지 않게 주의, static_cast가 곧바로 떠올라 다행이었다. https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net #include using namespace std; int main() { int testCa..

**배열 - OX퀴즈 *새롭게 배운 개념) - 2차원 동적배열 생성 및 할당해제 - 함수의 인자전달방식 : 배열을 parameter로 지정시 배열을 argument로 넣어도 배열이 아닌 pointer로 전달된다. 때문에 전달받은 배열(pointer)로 함수내부에서 연산시(대표적으로 배열크기구하기) 기대하던 결과가 나오지 않을 수 있다. - cin에 char array를 대입 시, 프로그램 실행 후 CLI에 문자열을 입력하면 각 요소가 하나하나 char array에 대입된다. char array 생성시 초기화를 ()으로 해주면 (null로 해주면) 이후 문자열의 끝을 지정할 때 편리하게 사용할 수 있다(아래 operation함수에서 null로 반복문 break를 건 것처럼). *총평 - 입력받는 값을 저장..