최근, 강화학습을 공부하면서 DP를 접하게 되었다. MP(markov process), MDP(markov decision process)를 공부하면서 DP를 처음 접하게 되었다. 기억나는 표현은 시간적 요소와 공간적 요소(메모리) 사이의 Trad-off라는 것. 즉, 메모리를 조금? 더 사용해서 관심 문제를 상대적으로 빠르게 해결하는 수단이라는 것이다. 특정 계산의 결과를 저장하여, 그 계산이 다시 일어나지 않도록 조치를 취하는 방식으로 작동한다. 백준1463 문제를 해결함에 있어서 DP를 어떻게 써먹을지 한번 고민해 봅시다. problem 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다...
선택 정렬 특징 (오름차순 기준) 0. 인간이 정렬할 때 본능적으로 사용하는 방법과 제일 유사 남아 있는, 섞여 있는 카드에서 제일 작은 숫자의 카드를 찾아서 이미 정렬된 배열 맨뒤에 위치시킨다. 1. 앞에서부터 뒤쪽으로 정렬되고, 정렬된 부분은 절대 변하지 않는다.즉, 오름차순이므로 작은 수부터 정렬된다. 2. 선택 정렬의 비교 횟수는 최소값을 찾기 위해서 N(N-1)/2 정도, 교환 횟수는 많아야 N-1회 즉, 비교 횟수 > 교환횟수 코드를 한번 봅시다. 12345678910111213141516171819202122static void select(int* src, int count) { int min; int minindex; for (int i = 0; i
알고리즘 공부 몰아서 하지 말고매일마다 뇌를 자극하도록 하는 차원에서 시작하는. 삽입 정렬 말로 표현 (오름차순인 경우) "i번 선수는 자신의 왼쪽만 보고, 자신이 가장 크면 가만히 있는다. 자신이 가장 크지 않다면 자신이 있어야 할 자리로 이동하게 된다. 이때 i번 선수가 자신의 자리를 찾아간다기 보다는 다른 선수들이 한 칸씩 이동하면서 최종적으로 생기는 자리에 들어가기만 하면 된다" 12345678910111213141516171819202122232425262728293031323334353637383940414243#include // 190313 sort_insertionusing namespace std; class Sort {public : static void insert(int* src,..
github : https://github.com/taewookimmr/Algorithm-C 현재 관심 있는 회사의 면접 후기들을 읽어보다가 면접 때 나왔던 재미있는 문제들이 보여서 직접 구현해보고자 한다. 문제 : 두 개의 큐를 이용해서 하나의 스택을 표현하시오제약 조건 : 큐의 index 역할을 하는 front와 rear, 동작 함수인 put(int k), get()를 제외하고는 어떤 변수, 함수도 사용할 수 없다. (단, 임시 변수는 사용할 수 있다.) 문제를 처음 딱 봤을 때, 솔직히, 답이 바로 떠오르지 않았다.잠시 딴 생각하다가 생각난 아이디어는 다음과 같다. (어떻게든 last-in이 first-out이 되도록 하면 된다!) 0) stack이라는 객체를 만드는데 맴버로 queue 두 개를 정..