누적합

int a[100004], psum[100004];

for(int i = 1; i <= n; i++){
	cin >> a[i];
	psum[i] = psum[i - 1] + a[i];
	
}

→ 1부터 누적합 만들기

psum[a] - psum[b - 1]

→ a ~ b 까지의 누적합 (b-1까지 빼야 a~b의 합이 나옴)

탐색

방향벡터

//위, 오른쪽, 아래, 왼쪽
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

for(int i = 0; i < 4; i++){
	int ny = y + dy[i];
	int	nx = x + dx[i];
}

탐색

void go(int y, int x){
	// 노드에 방문했으면 visit check!!
	visited[y][x] = 1;

	// 4가지 방향별로 체크하기
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		
		//다음 방향의 경계를 체크
		if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
		
		// 다음 방향의 노드가 인접해 있지 않을 때
		if(a[ny][nx] == 0) continue;
		
		// 다음 방향의 노드를 이미 방문 했을 때
		if(visited[ny][nx]) continue;
		
		// 다음 방향의 노드로 이동
		go(ny, nx);
	}
	return;
}

DFS

1. 방문했는지 check하고 다음으로 가기

//adj: 인접 노드를 담은 배열
vector<int> adj[n];

void DFS(int here){
	//방문 기록 표시
	visited[u] = 1;
	
	//노드를 방문했을 때 수행할 로직
	
	//다음 인접 노드를 방문
	for(int there : adj[here]){
		
		**//방문했는지 미리 체크하기**
		if(visited[there] continue;
		
		DFS(there);
	}
	
	//노드를 방문한 뒤 수행할 로직
	
	return;
}

2. 일단 가고, 방문했는지 체크하기

void DFS(int here){
	//일단 와서, 방문했으면 돌아가기
	if(visited[here]) return;
	
	//방문 안했으면, 왔다고 체크
	visited[here] = 1;
	
	//일단 다른 인접 노드로 가기
	for(int there : adj[here]){
		DFS(there);
	}
	
	return;
}