개인사

[G2] 백준 16920번 확장 게임 C++ 구현, 너비 우선 탐색, 플러드 필

리뷰 https://www.acmicpc.net/problem/16920각 라운드 마다 플레이어 번호가 낮은 순서부터 확장할 수 있을 만큼 확장 후 최종적으로 플레이어 마다 확장한 크기만큼을 출력하는 문제 전역 변수N : 맵 한변의 최대 길이를 정의할 상수 변수P : 플레이어 관련 배열의 최대 길이를 정의할 상수 변수n, m : 맵의 세로/가로 변의 길이를 저장할 변수p : 플레이어 수를 저장할 변수v : 맵의 방문 여부를 저장할 배열S : 플레이어 당 한 턴에 이동할 수 있는 거리를 저장할 배열cnt : 플레이어 당 점령한 성의 개수를 저장할 배열Pos : 시뮬레이션 시 사용할 현재 위치와 남은 이동 횟수를 정의할 구조체dx, dy : 4방향 탐색을 위한 방향 배열qs : 플레이어 별 Pos타입의 큐..

[G4] 백준 2479번 경로 찾기 C++ 너비 우선 탐색

리뷰 https://www.acmicpc.net/problem/2479비트 차이가 한개 나는 노드끼리 간선을 연결하고 특정 노드에서 목표 노드로 이동 가능한 경로를 구하는 문제 전역 변수N : 배열의 최대 길이를 정의할 상수 변수n : 노드의 개수를 저장할 변수l : 노드의 비트 개수를 저장할 변수H : 노드의 비트 정보를 저장할 배열c : 어떤 노드로 부터 왔는지를 저장할 배열v : 방문 여부를 체크할 배열edges : 간선 정보를 인접 리스트로 저장할 벡터 배열 함수1. bfsvector bfs(int sn, int en) { queue q; q.push(sn); v[sn] = true; while (!q.empty()) { int cn = q.front(); q.pop(); if (cn == ..

[G5] 백준 16938번 캠프 준비 C++ 백트래킹, 정렬

리뷰 https://www.acmicpc.net/problem/16938문제 N개를 조합하여 난이도의 합이 L~R이며 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이가 X이상인 조합의 개수를 찾는 문제 전역 변수n : 문제의 개수를 저장할 변수l, r : 문제 난이도 합의 최소, 최대 값을 저장할 변수x : 가장 어려운 문제와 가장 쉬운 문제의 난이도 차이의 최소값을 저장할 변수ans : 문제 조합의 개수를 저장할 변수lst : 문제의 난이도를 저장할 배열c : 선택한 문제의 난이도를 저장할 벡터 함수1. dfsvoid dfs(int level, int sum) { if (sum > r) return; if (level == n) { if (sum 문제를 선택하는 모든 경우를 탐색하기 위한 함수 ..

리뷰 https://www.acmicpc.net/problem/15661N명의 사람을 두 팀으로 나누어 능력치 차이의 최소값을 구하는 문제 전역 변수N : 배열의 최대 길이를 정의할 상수 변수n : 사람의 수를 저장할 변수ans : 정답을 저장할 변수lst : 인접 행렬을 저장할 배열 함수1. get_statsint get_stats(vector& T) { int res = 0; for (int i : T) { for (int j : T) { res += lst[i][j]; } } return res;} 팀에 속한 인원의 능력치의 합을 구하기 위한 함수 2. dfsvoid dfs(int level, vector& S, vector& L) { if (level == n) { if (S.empty..

리뷰 https://www.acmicpc.net/problem/2023N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 구하는 문제 전역 변수n : 정수의 자릿수를 저장할 변수st : 가장 첫번째 자릿수를 정의할 배열odd : 뒤에 붙을 수 있는 자릿수를 정의할 배열 함수1. is_primebool is_prime(int val) { int i = 3; while (i * i 현재 숫자가 소수인지 판정하기 위한 함수 2. dfsvoid dfs(int level, int val) { if (!is_prime(val)) return; if (level == n) { cout 현재 수의 뒤에 홀수를 붙여가며 재귀 레벨이 n까지 도달할 때 까지의 모든 경우를 찾는 함수 문제풀이n값을 입력 받고, st배..

리뷰 https://www.acmicpc.net/problem/251951번 노드에서 출발하여 더 이상 갈 곳이 없을 때 까지 곰곰이를 만나지 않을 수 있는지 여부를 체크하는 문제 전역 변수N : 배열의 최대 길이를 정의할 상수 변수n : 정점의 개수를 저장할 변수m : 간선의 개수를 저장할 변수s : 곰곰이가 존재하는 정점의 개수를 저장할 변수sp : 각 노드가 시작 노드로 사용이 가능한지 여부를 저장할 배열fv : 곰곰이가 존재하는 정점 정보를 저장할 배열edges : 인접 리스트 정보를 저장할 벡터 배열 함수1. bfsbool bfs(int sn) { queue q; q.push(sn); vector v(n + 1, false); v[sn] = true; while (!q.empty()) { i..

리뷰 https://www.acmicpc.net/problem/33851두 정점 u, v가 주어질 때 해당 정점으로 모두 이동이 가능한 정점 중 최단 거리를 구하는 문제 전역 변수N : 배열의 최대 길이를 정의할 상수 변수n : 정점의 개수를 저장할 변수m : 간선의 개수를 저장할 변수q : 쿼리의 개수를 저장할 변수edges : 인접 리스트를 저장할 벡터 배열 함수1. bfsvector bfs(int sn) { queue q; q.push(sn); vector dist(n + 1, -1); dist[sn] = 0; while (!q.empty()) { int cn = q.front(); q.pop(); //cout 매개변수로 받은 sn번 노드에서 모든 노드로 갈 수 있는 거리를 구하는 구하는 함..

리뷰 https://www.acmicpc.net/problem/15782회사 문화 이후 오랜만에 접한 LazyPropagation + 오일러 경로 테크닉 문제였다. 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 정점의 수를 저장할 변수m : 쿼리의 수를 저장할 변수edges : 인접 리스트를 저장할 벡터 배열it : 트리 인입 시간을 저장할 배열ot : 트리 탈출 시간을 저장할 배열ti : 인입 시간 기준 노드의 초기 가중치를 저장할 배열t : 오일러 경로 탐색 시간을 저장할 변수tree : 세그먼트 트리 정보를 저장할 배열lazy : 세그먼트 트리 업데이트 정보를 저장할 배열lst : 초기 노드별 가중치를 저장할 배열 함수1. dfsvoid dfs(int cur, int par) { i..

리뷰 https://www.acmicpc.net/problem/31222주어진 수열의 범위에 해당하는 부분 수열에서 정확히 일치하는 연속된 구간의 개수를 구하는 문제 전역 변수N : 배열의 최대 크기를 정의할 상수 변수n : 수열의 길이를 저장할 변수m : 쿼리의 개수를 저장할 변수lst : 수열의 원소 정보를 저장할 배열tree : 세그먼트 트리 정보를 저장할 배열 함수1. buildvoid build(int node, int s, int e) { if (s == e) tree[node] = lst[s] == lst[s + 1] ? 0 : 1; else { int mid = (s + e) / 2; build(node * 2, s, mid); build(node * 2 + 1, mid + 1, e..

리뷰 https://www.acmicpc.net/problem/18513K채의 집을 지을 때, 가능하면 샘터의 주변에 집들을 지어서 K채의 모든 집에 대한 불행도의 합이 최소가 되도록 짓는 문제 전역 변수n : 샘터의 개수를 저장할 변수k : 지어야 할 집의 개수를 저장할 변수ans : 정답을 출력하기 위한 변수dx : 2방향 탐색을 위한 방향 배열PD : 현재 위치와 가장 가까운 샘터로 부터의 거리를 정의할 구조체q : 너비 우선 탐색에서 사용할 PD타입의 큐v : 좌표 기반 방문 여부를 체크하기 위한 해시셋 함수1. bfsvoid bfs() { while (!q.empty()) { PD pd = q.front(); q.pop(); int p = pd.p, d = pd.d; for (int i ..