DOYLE DEVELOPMENT NODE

에라토스테네스의 채를 응용해서 풀었다.. 요런거는 백준에서는 테스트케이스를 다돌리는 거 같아서 소수 테이블을 구해주고 나머지를 코딩해주는게 낫다. 근데 이거 채점할 당시에 백준서버가 터져서 맞는답인지는 모른다. 케이스마다 답은 다 나오는데 시간초과의 위험이 상당히 큰 문제라 ㅎㅎ

-----------------------------------------------------------

역시 시간초과 떳는데 사실 여기 코드 그대로 하면 시간초과가 안뜬다. 그 비밀은 line8부터 10이다. 이 세 가지 함수는 cin, cout을 c형식인 printf, scanf를 사용하는 것처럼 바꿔 속도가 증가하게 된다. 역시 속도는 c다.. 다른 방법으로는 이렇게 시간이 중요한 문제(아슬아슬하게)는 printf를 써주면되겠다!

소수의 정의를 강의에서 배우고 푼 문제 

눈 여겨볼만한 테크닉이 하나 있다. 그것은 바로 8번줄 소수 N은 a*b (a <= b)형태로 이루어지는데 여기서 될 수 있는 a, b 의 최댓값은 루트N이므로 여기까지만 N이 나누어 떨어지는지 확인하면 된다. 그런데 이것을 코드로 구현하려니 한가지 문제점이 있다. 항상 소수점같이 컴퓨터의 이진으로 저장하는 체계로는 설명할 수 없는 부분이 나타날 때 수학과 간극이 생기는데 이것을 i*i 로 구현함으로써 멋지게 회피해나갔다. 

p.s 난 왜 문제를 한방에 못푸는 것일까.. 뭘 뺴먹든가 뭘 잘못 넣는다. 기분좋은 것은 항상 디버깅에 성공하고 디버깅 실력이 점점 늘고 있다는 것.. gdb를 cs:app bomb_lab 할 때 많이 썻지만.. 역시 비주얼스튜디오 디버거가 직관적이라 편하다 ddd는 또 다를려나 

2진수를 8진수로 바꾸어서 푸는 문제 은근 코드가 손이가고 메모리도 크고 시간도 많이잡아먹었다.. 내 연산이 좀 비효율적이었나.. 데이터 크기는 최대 1,000,000개의 1과 0으로 이루어진 2진수이다. 문제를 볼 때 빨리 풀고 싶어서 시간복잡도를 계산안하고 무식하게 푸는 방법을 많이 썼는데 시간복잡도를 항상 풀기 이전의 계산하는게 중요하다고 했다.. 그래야 코딩을 할 지 안 할지 결정할 수 있기 때문이다. 이중 for 문도 없고 push back pop back, back 같이 아직 stl을 깊게 탐구하지 않았지만 그렇게 시간복잡도를 증가시키는 연산이 없는 거 같아서 예상 시간복잡도는 O(n)이다.

진법변환 공식은 N수가 있으면 나눠주고 그 나머지를 차례대로 스택에 넣어준 후 거꾸로 출력하면 된다. 그것은 수학 공식.

나는 벡터를 썻다. 스택과 벡터가 있으면 유연성 떄문이지 사람들이 벡터를 쓰던데 그 이유를 조금 찾아봐야겠다.. STL을 알고리즘 문제 풀때마다 그 때 그때 찾아써서 제대로 공부하고 각 자료구조들의 차이점 장점에 대해서 파악하고 분석해볼 필요를 느낀다... 일단 강의진도는 따라가고 문제로 돌아가면 위의 공식을 그대로 풀어주면 되지만 까다로운 부분은 36진법 까지 가능해서 얘네를 아스키코드로 변경시켜줘야하는 코드를 추가시켜줘야한다.. 인터넷창에 아스키 코드 검색하고 찾아봤다.. 아스키코드와 최근 CS:APP ISA(instruction set 아키텍쳐(스펠링생각안난다)) 부분을 공부하면서 느끼는 건데 컴퓨터는 정보를 encode 하고 decode가 핵심이라는 생각이든다. 

#include <iostream>
#include <vector>
using namespace std;
long long N;
int main()
{
	cin >> N;
	int b;
	cin >> b;
	char show_val;
	vector<int> output;
	while (N != 0)
	{
		output.push_back(N%b);
		N = N / b;
	}
	while (!output.empty())
	{
		show_val = output.back();
		if (show_val > 9)
		{
			for (int i = 0; i < 26; ++i)
			{
				if (show_val == (i + 10))
				{
					show_val = show_val + 55;
					cout << show_val;
					output.pop_back();
				}
					
			}
		}
		else
		{
			cout << (int)show_val;
			output.pop_back();
		}
		
	}
	cout << endl;
	return 0;
}

연속되는 정수 N에서 K개의 합으로 N을 만드는 경우의 수를 구하는 문제

d[k][n] = 시그마d[k - 1][n - l] l은 0보다는 크고 n보다는 작은 수 아이디어는 이렇다. 연속되는 정수 k개로 n을 만들려면 정수 k -1 개로 자연수 n에서 n보다 작은 l 수 만큼 빠진 수를 구한 경우의 수들을 모두 더해야 한다. 솔직히 어렵다.. 

조오금 까다로운 문제다. 강의노트가 없었다면 아마 꽤 시간을 많이 걸렸거나 못 풀었을 것 같다. 아이디어만 캐치하면 코딩자체는 심플하고 쉽다. i가 i번째에서의 블록 개수라고 하면 i-2 에서 블록 3개를 가지고 i와 i-2사이의 3x2공간을 채우는 경우를 생각해보면 3가지 경우가 있고 점화식이 생각난다. 하지만 여기서 끝이 아니라 i - 4, i - 6, .. 계속 나아가 심지어 0일 때 조차도 블록을 쌓을 수 있는 경우가 있는데 블록들을 2층으로 쭉 쌓고 그 부분을 감싸는 형태의 모습이다. 이 블록은 2칸 마다 새로운 형태의 블록이기 때문에 따로 점화식을 세워줘야 한다.

각 수가 몇 개의 제곱 수 의합으로 이루어져있는지 푸는 문제, 다이나믹 프로그래밍을 이용해 이전 값을 저장하고 점화식을 세워가며 풀면 쉽다.

핵심은 7 = 1 + 1 + 1 + 4 라고 되있을 때 마지막 4이다. for문을 제곱으로 증가시켜가며 최소값을 찾고 그 값에 1을 더해준다.

힌트 : 다이나믹 프로그래밍을 이용해 점화식을 세워보자 첫번 째로 계단을 올라온 경우 두번 째로 계단을 올라온 경우

첫번 째로 계단을 올라온 경우는 두 칸아래 계단을 첫 번째로 올라왔는지 두 번째로 올라왔는지 상관 없이 올라올 수 있고

두번 째로 올라온 계단은 직전 계단의 첫번째로 올라온 경우에만 올라올 수 있다. 점화식을 세워보자!