해나의 컴공생존기

1. 문제정의 행렬의 곱에서 어떤 행렬을 먼저 곱하냐에 따라 걸리는 시간이 달라진다. 행렬들은 M1, M2, ... Mn으로 표현되며, 행렬의 크기는 di-1 * bi로 표현된다. Cij는 Mi부터 Mj까지 곱했을 때 최소 비용을 의미하며 C1n이 최종 답이 된다. 2. solution 전체 답을 제일 좋은 답으로 만들기 위해서는 어떤 곱을 나중에 해야할까? 우리는 이 문제에 대한 해답을 알지 못한다. 따라서 하나씩 다 해볼 것이다. Cij에서 i-j가 작은 값부터 해볼 것이다. 1) i-j =0 C11,C22,C33, ... Cnn 위와 같은 경우는 비용이 모두 0이라고 할 수 있다. 2) i-j =1 C12,C23,C34, ... Cn-1n 비용은 di-1 * di * di+1 3) i-j =2 C1..

정의해준 재귀함수를 분석해보겠다. 인자로 a,b,c 가 들어오고 이 값에 따라 재귀호출을 하는 것 같다. a,b,c 중 하나라도 0이하가 되면 1을 리턴한다. a,b,c 중 하나라도 20이상이 되면 a,b,c에 20을 넣고 재귀호출한다. a> b >> c; if (a == -1&&b==-1&&c==-1) break; //종료조건 cout

1. Binary Search 이진탐색트리 코드이다. l은 왼쪽 끝 ,r은 오른쪽 끝 ,m은 중간이다. 기본 적인 아이디어는 sorting된 배열의 중간을 찾아 크기를 비교해가며 원하는 값을 찾는 것이다. 처음에는 0번째 배열을 l , 마지막 배열을 r로 두고 탐색을 시작한다. 탐색은 l과 r이 만나면 종료된다. m은 l과 r의 중간이고 (l+r)/2 로 두었다. 이게 성립하나를 위해 몇가지 예시를 보겠다. 1) n=2 l=0, r=1, m=0 으로 모두 탐색 가능하고 2) n-3 l=0, r=2, m=1 으로 모두 탐색 가능하다 a[m]과 x를을 비교해서 x가 작다면 왼쪽을 탐색하고 x가 크다면 오른쪽을 탐색하고 x와 같다면 종료된다. 왼쪽 탐색을 위해서는 r을 m의 바로 전 인덱스로 설정되고 오른쪽 ..

1. 알고리즘 바킹독님 영상 보고 공부하기..! 꼭 끝까지하고 백준도 모두 풀어보기!! (C++) 2. 동아리 스터디 동아리 스터디 신청한거 밀리지 말고 꾸준하게 열심히 공부하기!!! 2. Node.js 저번 스터디 열심히 못한게 넘 아쉬워서 꾸준히 해서 책 한번 끝내보자! 4. 프로젝트 계획 한 프로젝트 해서 배포하기! 개강 전에 마쳐보기!! 5. 전화영어 정말정말 귀찮지만 환급을 위해 꼭 6번까지만 빠지기..! 6. 토익 토익 목표는 840점..! 더도 말고 덜도 말고 딱 장학금 기준까지만 찍자 파고다 Voca , 파고다 RC 실력완성, 파고다 LC 실력완성, ets 기출 1000 vol3 으로 준비할 것이다. 책은 6/22 ~ 7/23 까지 해서 끝낼 것이고 그 이후로는 기출만 돌리다가 8/7에 토..

한번 동적할당을 하고 이중 포문을 이용해서 코드를 짰는데 시간초과가 났다.. 그래서 두번 공적할당을 하고 합을 구하는 과정에서 시간복잡도를 줄였다.. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int num ; int* arr; cin >> num; arr = new int[num]; for (int i = 0; i > arr[i]; int sum=10,fre=0; cin >> sum; int* N = new int[sum+1]; for (int i = 0; i < sum+1; i++) N[i] = 0; for (int i = 0; i < num; ..

#include #include using namespace std; int main() { long long sum=1; long long num[10] = { 0, }; cin >> sum; while (sum) { num[sum % 10]++; sum /= 10; } long long Big = 1; int index=0; for (int i = 0; i < 10; i++) { if (i == 6 || i == 9) continue; Big = max(Big, num[i]); } cout

어떻게 각 자리 숫자를 확인할까 하다가 몇자리인지 확인하고 그만큼 반복하며 일의자리 수 체크 10으로 나누기를 했다. 하지만 훨 간단한 방법이 있었다. 난 몇번반복하는가에 대하여 고민을 많이 했는데 이를 한번에 해결할 방법이 있었다. 밑에 주석처리 해놨으니 참고하면 될 것 같다. #include #include using namespace std; int main() { int a, b, c,sum; int num[10] = { 0, }; cin >> a >> b >> c; sum = a * b * c; int D=10,B=1; while (sum>D) { D *= 10; B++; } for (int i = 0; i < B; i++) { num[sum % 10]++; sum /= 10; } /* whil..

연결리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 저장하는 자료구조 특징 k 번째 원소를 확인하기 위해 O(k)가 필요하다 임의의 위치에 원소를 추가,제거는 O(1) 종류 단일 연결리스트 이중 연결리스트 원형 연결리스트 배열 vs 연결리스트 // 연결리스트에 원소를 넣었다가 뺏다하는 함수 #include using namespace std; const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; int unused = 1; void insert(int addr, int num) { dat[unused] = num; pre[unused] = addr; nxt[unused] = nxt[addr]; if(nxt[addr]!=-1) // 맨 끝에 삽입하는게 아..

#include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int a; cin >> a; for (int i = 0; i < a; i++) { for (int j =0; j < i; j++) { cout 0; k--) { cout

#include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(nullptr); int a; cin >> a; for (int i = 0; i 0; j--) { cout