16강 (DP) 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 초기값이 어디인지를 잘 생각해서 적용해주어야 함 구현이 짧은 편 D[i][j] (2차원으로 선언 하는 이유? , 지금까지 몇 개의 계단을 밟았는지에 대한 정보가 있어야 하므로) 직접적인 값 or 추상화(D[K][1]) 관점을 달리 하면 또 다른 방식으로 DP식이 도출될 수 있음 2차원 배열을 잘 활용해서 여러 조건을 관리하기 DP에서의 경로추적 → 값 테이블 이외에 경로 복원용 테이블을 하나 만들어서 관리 복원용 테이블의 INDEX를 타고가서 1에 도달할 때 까지 출력 후 종료 17강 (그리디) 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름 1. 관찰을 통해 ..
정렬I (14강) *max_element(arr, arr+k) → arr[0], arr[1], ..., arr[k-1]에서 최댓값인 원소의 주소를 반환(+참조) 선택정렬, 버블정렬, 삽입정렬 O(N^2) Merge Sort O(NlogN) Stable Sort 우선순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬 Quick Sort O(NlogN) - 코딩테스트에서 STL을 못 쓰게 하고 직접 구현해서 정렬을 사용해야 한다면 Quick Sort 구현하지말고 다른 방식으로 퀵소트의 장점은 추가적인 공간이 필요하지 않다는 점, cache hit rate가 높아서 속도가 빠름 → 추가적인 공간을 사용하지 않고(In-Place Sort) pivot을 제자리로 보내는 방법 필요, stable sort가..
13강 (시뮬레이션) 1. 상하좌우는 dy[4], dx[4]를 적극사용 2. 매번 반복문을 돌면서 시작위치를 탐색하기보다는 vector pos에 미리 시작위치를 입력받을 때 저장해두는 것이좋다 3. bfs에서와 마찬가지로 특정 index를 활용하여 bool visited 배열의 사용 없이 방문여부를 체크할 수 있다. 4. 이전 값을 저장해둠으로써 false로 되돌리는 효과를 얻을 수 있다. 각 CCTV의 방향을 정해야함 >> 16가지의 가능성 (백트래킹) 변수들이 가질 수 있는 값이 여러개이고 모든 조합을 확인하고 싶은 상황에서 변수들끼리는 서로 독립적일 때 백트래킹대신 진법 이용하면 더 쉬움 가능한 종류가 4개 → 4진법사용 000~333 각각의 자리를 방향 3개에 대응시킴 39는 4진법으로 213 →..
9강 (BFS) - 너비 우선 탐색 - pair이용 (좌표) - BFS를 돌 때 큐에 쌓이는 순서는 반드시 거리 순 - 예외처리는 continue로 넘겨버리는 것이 깔끔 → 좀 더 직관적 - visited 배열을 별도로 관리하기보다 distance배열에 -1을 저장해둠으로써 관리가 용이해지고 공간을 절약할 수 있음 (거리와 방문 여부 동시 관리 가능) - [응용1] 최단경로(거리측정) - [응용2] 시작점이 여러개일 때 - [응용3] 시작점이 두 종류일 때 → A의 전파가 B에 영향을 주고 B의 전파가 A에 영향을 주지 않는 경우(독립적인 상황)가 아니고 상호 영향을 주는 관계라면 어느 하나를 먼저 전파시키는 것이 불가능 이러한 경우에는, 시간 순으로 A와 B를 동시에 진행시켜야 함 - [응용4] 1차원..
4강 - STL의 list는 이중연결리스트 구조 - 야매 연결 리스트 (배열로 구현하는 간결 연결리스트) const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; int unused = 1; fill(pre, pre+MX, -1); fill(nxt, nxt+MX, -1); 1406번 에디터 → STL list, 야매 연결 리스트를 사용하여 풀어보기 5강 (스택) push, pop, top, emtpy, size 스택이 비어있을 때에는 top이나 pop을 호출하지 않도록 주의 6강 (큐) 원형큐 → push와 pop을 반복하다보면 점점 뒤로 밀리는 점 개선 7강 (덱) stl deque에선 인덱스로 원소에 접근할 수 있음 stl deque는 front에서도 O(1)..
0강 - X 1강 실수를 비교할 때에는 등호를 사용하면 안된다. abs(a-b) < 1e-12을 사용해서 비교 2강 - 참조자 사용 - STL vector는 인자로 전달하여 해당 함수에서 값을 변경하여도 원본 vector에 반영되지 않음. vector를 함수인자로 넘길 때 복사비용때문에 1차원 벡터기준 O(N)의 시간복잡도 필요 → vector& v1과 같이 참조자 사용으로 O(1)으로 사용가능. - getline(cin, s)를 통해 공백이 있는 문자열을 입력받음 - ios::sync_with_stdio(0), cin.tie(0) → 동기화를 끊음을 통해 시간 절약 가능. 단, 이를 사용했으면 cout과 printf를 섞어써서는 안된다. 3강 - 배열 초기화시 memset 비추천 - algorithm ..