아네스의 공부일지

dp배열을 미리 생성한 뒤 값을 찾는다. dp인줄 모르고 풀어야하는데.. 궁금해서 알고리즘 분류 봤더니 dp로 바로 풀게됐다.. 어느때 dp로 풀어야할까 ? N 값을 보면 N이전의 값을 참조해야하는데, 이렇게 반복적으로 참조되는경우 dp로 풀면 시간단축할 수 있다. #include using namespace std; int dp[1000001]; //크기 유의, 10^6 인걸 10만으로 잡았다가 계속 런타임에러 ㅠ int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; dp[0] = 0; dp[1] = 0; for(int i = 2; i

처음 분할정복 / 재귀 문제를 풀어보는데, 애초에 이게 분할정복인지 재귀인지 모르고 풀었다. dfs로 풀 수 있을것 같아서 풀어봤었는데 역시 시간초과. 2시간 가량 생각해서 풀었는데.. 분할정복 개념은 알고있었지만 이것에 대한 문제를 풀어본 적이 없어서 너무너무 헷갈렸다. 그래서 다른사람들의 블로그를 참고해서 다시 풀어보기로 한다. 아래는 처음 구현했던 코드다 아주 난잡하기 짝이없다. #include using namespace std; int N,r,c; int cnt = 0; void dfs(int row, int col, int d,int sx, int sy) { if(d >= pow(2,N-1)*pow(2,N-1)) return; if(r == row && c == col ) cout > r >>..

목표 1. Solved Class 5까지 에센셜 모두 풀기 (된다면 에센셜말고 다른것도) solved.ac에 가면 문제들이 여럿있다. 일단 석사 제대로 시작하기 전에 코딩테스트 통과할정도의 실력은 쌓아두고 나중에 취준기간에 급급하게 준비하고 싶지 않다. 그리고 고급 알고리즘도 좀 배워보고 싶기도 하고. 요 며칠간 Class1,2는 뚤었고, Class 3,4,5하면 약 70문제정도 되는거 같은데 대학원 일하고 병행하면 빡빡하게 굴러갈 것 같다. solved.ac - 문제 › CLASS CLASS 문제를 흰 선까지 해결하면 CLASS를 취득할 수 있습니다. 에센셜 문제들을 전부 해결하면 은장을 취득할 수 있습니다. 검은색 점선까지 해결하면 됩니다. 전체 문제를 전부 해결하면 금장을 solved.ac 목표 2..

BFS문제. row, col 바뀌어서 input 주어지니 유의 #include using namespace std; queue q; int T,M,N,K; int cnt=0; int board[51][51]; bool visited[51][51]; int dx[4] = {0,1,0,-1}; // 상, 우, 하, 좌 int dy[4] = {-1,0,1,0}; void bfs(int row, int col){ visited[row][col] = 1; // 시작지점 방문 표시. q.push({row,col}); while(!q.empty()) { int r = q.front().first; int c = q.front().second; q.pop(); for(int i = 0; i< 4; i++) // 시계방..

vector pair안쓰고 그냥 '0' 개수세는 배열 , '1' 개수 세는 배열 만들고 해도 될듯. 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net #include using namespace std; vector v; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; v.push_back({1,0}); v.push_back({0,1}); //first = 0의 개수, second = 1의 개수 for(int i = 2; i> tmp; cout

음... 옛날에 저 에라토스테네스의 체 를 본적이 있어가지고 금방 푼 것 같다. 그냥 IsPrime만 돌리면 시간초과 바로 나버리니 dp로 풀어야함. #include using namespace std; uint8_t prime[1000001]; bool IsPrime(int a){ bool flag = true; for(int i =a-1 ; i>1; i--) { if(a%i ==0){ return false; } } return true; } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N >> M; //아직 미탐색 0, prime num = 1, 소수 아니면 2. prime[1]=2; for(int i =..

배열을 원형큐로 쓰는거 헤매가지고 좀 걸렸던것 같다. #include using namespace std; #define MAXSIZE 100000 typedef class _deque{ private: int ary[100000]; int back; int front; int datasize; public: _deque(){ back = 1; front = 0; datasize =0; } void push_front(int a) { ary[front] = a; front = (front-1 + MAXSIZE) % MAXSIZE; datasize++; } void push_back(int a) { ary[back] = a; back = (back+1 +MAXSIZE)%MAXSIZE; datasize++;..

로직대로만 풀면 되는 문제. #include using namespace std; int N,K; queue q; vector v; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> K; //최초 큐 세팅 for (int i = 1; i 0; i--) { if (i == 1) // K번째 숫자는 출력되야 하므로 { v.push_back(q.front()); // 나중에 출력할 vector에 추가. q.pop(); } else { // 그 외의 연산은 앞에꺼 빼서 뒤로 넣어준다. q.push(q.front()); q.pop(); } } } for (int i = 0; i < v.size(); i++..

#include using namespace std; int N; vector v; bool compare(pair& a,pair& b) { if (a.first == b.first) { return a.second > N; for (int i = 0; i > a >> b; v.push_back({ a,b }); } sort(v.begin(), v.end(), compare); for (int i = 0; i < N; i+..

오 너무 간만에 class 써봐서 까먹었다.. 그래도 보던것들이 있어서 그런지 검색없이 풀었음 ㅎㅎ command함수는 없어도 됐는데, main문에 넣기 싫어서 class안에 집어넣었다. #include using namespace std; int N, M; string s; class stk { private: size_t stkpointer; int ary[100001]; public: stk() { stkpointer = 0; } void command(string s) { if (s == "pop") this->pop(); else if (s == "size") this->size(); else if (s == "empty") this->empty(); else if (s == "top") thi..