아네스의 공부일지

아아.. 맨처음에 dp인줄알고 dfs와 dp를 섞어서 풀다가 시간초과나고 아니 dp인것 같은데 아니라고 ? ( 실은 모든경우 탐색하는것 같은 느낌이라 우려가 되긴 했다) 그래서 dijkstra처럼 풀어서 표가 다 구해지면 동생의 위치를 출력하게 했는데 안되더랑.. 그런데 생각해보니 queue에 time을 추가해서 넣어주면 0,1,1,1,2,2,2,3,3,3 이런식으로 들어와서 동생 위치에 도달하는 순간이 최소시간이라는걸 뒤늦게 깨닫고 단순 bfs+ pair을 써서 풀었다. 요새 여러 종류의 문제를 풀다보니 머릿속이 뒤죽박죽인듯하다. C++ 풀이 #include using namespace std; queue q; //bfs탐색용 bool visited[200001]; // 방문여부 int N, K ; v..

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 >>..

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..