유댕이 메모장 유댕이 메모장

주어진 배열을 모두 더해서 값을 가지고 활용하는 문제 예시) BOJ 11659 i번째 수부터 j번째 수까지 반복해서 수를 구하는 방법 대신 S[i] = S[i-1] + A[i]를 활용하면, O(n) S[i] - S[j-1]으로 값을 총 O(N) 시간 만에 구할 수 있다

백트래킹 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 BOJ15649 N과 M 기본 문제 #include using namespace std; int n, m; int arr[10]; bool isused[10]; void func(int k) { // k까지 고른 상태에서 arr[k]를 정하는 함수 if (k == m) { for (int i = 0; i < m; i++) cout m; func(0); }

재귀 조건 1) 특정 입력에 대해 자기 자신을 호출하지 않고 종료되어야 함(base condition) 2) 모든 입력은 base condition으로 수렴해야 함 재귀에 대한 정보 1) 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 넘겨줄지 정확히 알아야 함 2) 모든 재귀 함수는 반복문만으로 동일한 동작의 함수 구현 가능 3) 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 시간/메모리에서 손해 자기 자신을 여러 번 호출하면 비효율적일 수 있음 절차지향적 사고를 버려라! 1) 1에서 잘 동작함 2) k에서 잘 동작함 3) k+1에서 잘 동작함 -> (k+1, k, k-1, k-2...)에서도 잘 동작함 필요한 것: 함수의 정의 / Base condition / 재귀식 BOJ11729 하노이..

# BaaarkingDog 님의 강의를 참고했습니다 BFS 다차원 배열에서 각 칸을 방문할 때, 너비를 우선으로 방문하는 알고리즘 STL container의 pair 기능을 사용해 좌표 입력 pair t2 = { 4,6 }; // C++ 11 #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 // t.first, t.second 대신 t.X, t.Y로 사용 가능 int board[502][502] = { {1,1,1,0,1,0,0,0,0,0}, {1,0,0,0,1,0,0,0,0,0}, {1,1,1,0,1,0,0,0,0,0}, {1,1,0,0,1,0,0,0,0,0}, {0,1..