메밀이네

DP는 DP인데 문제를 이해하는데 좀 오래걸렸습니다. 간단하게는 모든 코인에 대해 메모제이션을 하면 되지만 메모리제한이 엄격해 다른 방법을 찾아야 합니다. 두번 중첩된 for문을 설명해보자면 1. i가 0부터 n까지 반복문을 실행합니다. 바깥쪽 반복문은 i번째 코인이 사용되는 경우의 수를 구하겠다는 것을 의미합니다. 2. 안쪽에 있는 중첩된 반복문은 i번째 coin의 값부터 시작합니다. 첫번째 반복문을 통해선 무조건 1이 더해집니다(코인값 j와 같은 가치의 코인을 사용하는 경우). 이후 코인값 j에서 i번째 코인의 값을 뺐을때의 값을 구할 수 있는 경우의 수를 더해줍니다. 이 반복문을 통해 coins[i]가 j값을 만들기 위해 사용된 모든 경우의 수를 구할 수 있습니다. 123456789101112131..

동적 계획법 단계의 문제를 열심히 풀고 있습니다. 계단 수란 다음 자릿수가 1의 차이를 가지고 이어지는 수입니다 예를들면 3456, 210 등이 있겠습니다. 다이나믹 프로그래밍으로 풀었습니다. 자릿수 N으로 4가 주어졌을 경우 첫번째 숫자의 다음 자리 수는 첫번째 숫자에서 1을 더하거나, 1을 뺀 수가 와야 합니다. 첫번째 숫자가 3일 경우, 다음 자리에 올 수 있는 계단 수는 2와 4인것입니다. 메모제이션 된 2와 4의 값을 더하면 쉽게 현재의 계단 수 개수를 구할 수 있습니다. 0과 9의 경우 다음 자리에 올수있는 숫자가 1과 8로 한정적입니다. 이 경우만 케이스를 분류해서 따로 계산합니다. 1234567891011121314151617181920212223242526272829303132333435..

꽤나 오랫동안 헤메였는데 선행 노드에 대해 이해하고 쉽게 풀 수 있었습니다. DFS에서 방문한 노드를 체크해 큐에서 순서대로 노드를 탐방한다면 위상 정렬은 다음 노드의 선행자가 없을경우만 큐에 푸쉬합니다. 선행자에 대해 확실히 짚고 넘어갔다면 금방 풀었을 것 같습니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include int* buildingTime;int** buildings;int* pre; int max(int a, int b) { return a > b ? a : b;} i..

저는 단계별로 풀어보기로 문제를 풀고있는데, 기수정렬 또는 계수정렬로 풀어보세요! 라고 써있는걸 기수정렬로만 풀었더니 런타임 에러가 떠버려서... 슬랙에서 질문하니 아직 문제 설명 수정이 안되어있다는 한탄을 하시더라구요.. ㅎㅎ; 메모리 제한 같은부분에서 대답이 척척 나오시던데 저도 더욱 열심히 공부해야겠습니다. 아래는 제가 짜본 기수정렬과 계수정렬입니다. - 기수정렬 소스코드 void radix_sort(int* arr, int n, int radix) {std::queue newarr[10]; for (int i = 0, mod = 1; i < radix; i++, mod*= 10) {for (int j = 0; j < n; j++) {int temp = (arr[j] / mod) % 10;newar..

힙 정렬이나 합병 정렬을 이용해서 수 정렬하기 문제입니다. 이론상으론 알고있는데 수도코드없이 머리로만 하려니까 에러가 많이 나더라고요... 종이에 적어서 차근차근 풀어보니 쉽게 풀렸습니다. #include void merge(int* arr, int left, int mid, int right);void divide(int *arr, int left, int right); void divide(int *arr, int left, int right) {if (left < right) {int mid = (left + right) / 2; divide(arr, left, mid);divide(arr, mid+1, right);merge(arr, left, mid, right);}} void merge(int..

배열로 해야지... 라는 생각은 1도 못하고 공백의 규칙을 찾으려고만 했는데어떻게든 할수있을것 같긴 한데 갈수록 머리가 아파서 결국 다른분의 도움을 받아서 완성했습니다... 1. 입력받은 n에 대하여 가로 2*n-1줄, 세로 n줄의 배열을 선언하고 일괄적으로 ' '(공백)으로 초기화한 후2. n은 3, 6, 12...의 순으로 전달되므로 특별한 케이스는 n=3일때를 제외하고 n의 값이 3이 될때까지 재귀적으로 다음 함수를 호출합니다.3. 그리고 출력 후 heap의 메모리를 해제하는데, 여기서 제가 조금 더 헤맸습니다... 한동안 코딩을 놓고있었던게 바로 드러나버리니 부끄러울 따름이네요 소스코드는 아래와 같습니다. 비쥬얼 스튜디오 C++ 사용했습니다. #include #include void set_sta..