아네스의 공부일지

문제풀이 아이디어 핵심 BFS를 사용하는 queue에 x,y,count값을 저장한다. N,M이 바뀌어서 주어지니 board입력받을 때 유의하자. C++ 풀이 #include using namespace std; queue q; // x,y, count int board[1001][1001]; bool visited[1001][1001]; int dx[4] = {-1, 0 , 1, 0}; //시계방향 탐색 (상 , 우 , 하 , 좌) int dy[4] = {0,1,0,-1}; int N,M; int res=0; void bfs(){ while(!q.empty()){ int x=q.front().first.first; //row 좌표 int y = q.front().first.second; // col 좌표..

아이디어는 아래 분할 정복 문제 풀었던 것과 동일하다. 다만 색종이를 판단해야하는 방법이 추가됐을 뿐. [백준 1074번] Z ( 분할정복, 재귀) ** 다시풀어보기** 처음 분할정복 / 재귀 문제를 풀어보는데, 애초에 이게 분할정복인지 재귀인지 모르고 풀었다. dfs로 풀 수 있을것 같아서 풀어봤었는데 역시 시간초과. 2시간 가량 생각해서 풀었는데.. 분할정복 i-never-stop-study.tistory.com 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net C++ 풀이 #in..

강의 들은지가 오래되고 , 분명 썼는데 언제썼더라... Groupby한것을 기존 dataFrame에 합칠때 썼던거 같기도.. merge와 Join이 있는데 merge를 쓰자. inner Join 예시 이렇게 사용할 수 도 있다. Left Outer / Right Outer Join 헷갈리게 Left, right 하지 말고 How를 left로 고정시키고 쓰는게 더 편해 보인다. 다만 column의 순서가 달라지니 유의. Full outer join 수행

함수 근사란? 파라미터Θ를 조정해서 (x,y)페어를 잘 표현하는 함수를 찾고싶다. 왜 RL강의에서 "함수 근사" 를 배우는가 ? 크게 2가지로 함수근사를 사용하고 배우게 됨. 1. 파트4 정책 최적화에서 정책함수 π를 표현하기 위해서. 2. 파트5 심층강화학습에서 사용하기 위해서 함수근사 사용 효과가 굉장히 좋음. 데이터로부터 함수 근사를 수행할 수 있음. 선형회귀같은 경우에 데이터가 선형이라는 가정을 하고 시작하기 때문에(함수에 대한 구조 가정) 실제 데이터가 선형이 아니라면 정확도가 떨어진다. 그러나 딥러닝같은 경우에는 이런 가정 없이, 충분히 데이터가 많다면 함수를 근사할 수 있다. 데이터를 함축적으로 잘 표현하는 좋은 representation을 배울 수있음 (나중에 배워보자) 좋은 represe..

1에서 시작해서 방문할 수 있는 모든 노드를 찾는 문제. C++ 풀이 #include using namespace std; vector v[101]; bool visited[101]; queue q; int cnt = 0; void bfs() { visited[1] =true; q.push(1); while(!q.empty()) { int a = q.front(); q.pop(); for(int i =0; i> N >> M ; for(int i = 0 ; i > a >> b; v[a].push_back(b); v[b].push_back(a); } bfs(); cout

짱구를 굴렸을 때, 음.. 뭔가 그리디하게 선택해서 풀면 되겠다 라고 생각은 했지만, 그리디 증명은 어떻게 하지 ? C++ 풀이 #include using namespace std; vector v; bool compare(pair& a, pair& b){ if(a.second == b.second) { return a.first > N; for(int i = 0; i>..

C++ 풀이 C++은 기본적으로 priority_queue를 지원하는데, 이게 default로 max_heap이라서 min_heap을 쓰려면 음수로 넣어주고 빼서 쓸 때 다시 마이너스 붙여줘서 사용해야한다. #include using namespace std; priority_queue pq; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; for(int i = 0; i> tmp; if(tmp == 0) { if(pq.empty()) { cout

처음에 map에다 때려 박고 M개를 비교했는데, 400ms가 나왔다. 실버에서 400ms라.. 뭔가 이상해서 C++로 푸신분들 보니 30ms도 안나와서 알고리즘 분류를 보니 이분탐색으로 되어있더라.. 그래서 이분탐색으로도 한번 풀어보고, 파이썬으로 이분탐색 안풀어봤으니 풀어보고자한다. #include using namespace std; vector v; map m; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N >> M; for(int i = 0 ; i> s; m[s]; // 다 넣고 } for(int i = 0 ; i< M; i++) { string s; c..

복습 TD로도 Off-policy를 할 수 있겠구나. TD(0) (복습) TD(0) 현재 보상인 Rt+1과 한번 감가한 다음state의 value fucntion Off-policy MC(복습) Off-policy를 하는데 Correction term이 존재했다. Importance sampling for Off-Policy TD Importance sampling의 단점 Q-Learning : An Off-Policy TD Control Q-Learning이 TD의 유일한 Off-Policy 방법은 아니다. TD의 다양한 Off-Policy 방법이 존재하나 Q-Learning이 가장 구현이 쉽다. 어떤 정책을 사용하든 행동 a를 구했다고 생각하고 행동 a를 환경에 가한 후 , 환경으로부터 보상과 다음상..

복습 강화학습 문제는 MDP로 정의된다. 마르코프 결정과정에서 최적 가치함수, 최적 정책을 구하는것이 목적. 최적 가치, 정책을 얻기 위해서 DP / MC,TD (환경을 알 때 / 모를 때) 정책 평가 : 주어진 정책의 가치함수를 계산하는 과정 정책 개선 : 우리가 알고있는 정책을 조금 더 나아지게 만드는 과정. 위 그림을 통해서 전반적인 교육과정 및 세부사항과 각 내용의 장단점, 특징을 이해하기. 지금까지 배운 강화학습 기법의 템플릿 정책 개선마다 새롭게 Q^pi_k를 추산하기 위해서 또 새롭게 샘플들을 모음. 좋은 특성은 아님. 새롭게 정책을 개선할 때 마다 환경과 interaction이 있어야하고 샘플링이 되야한다. 특히 시뮬레이션환경이 아니라 현실 환경이라면 그만큼 학습이 느려질 것임. 사람은 타..