[ 백준 10868 ] 최솟값 (C++, 세그먼트 트리)
[문제보기] [해결과정] - 세그먼트 트리 활용 [소스코드] #include #include #include #include #include using namespace std; typedef long long ll; #define MAX 400005 int n, m, a, b; ll minTree[MAX*10]; ll node[MAX]; // init(배열, 위치, 시작점, 끝점) ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) { if (dataIdxL == dataIdxR) return minTree[treeIdx] = arr[dataIdxL - 1]; ll mid = (dataIdxL + dataIdxR) / 2; return minTree..
2021. 4. 17.
[ 백준 2357 ] 최솟값과 최댓값 (C++, 세그먼트 트리)
[문제보기] [해결과정] - 세그먼트 트리 활용 1. minTree, maxTree 구별 2. 각각 init함수와 query함수 작성 [소스코드] #include #include #include #include #include using namespace std; typedef long long ll; #define MAX 400005 int n, m, a, b; ll minTree[MAX*10]; ll maxTree[MAX*10]; ll node[MAX]; // init(배열, 위치, 시작점, 끝점) // init_최소 트리 ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) { if (dataIdxL == dataIdxR) return minTre..
2021. 4. 17.
[ 백준 10026 ] 적록색약 (C++)
[문제보기] [해결과정] 1. input -> n, arr 입력받기 2. 정상인 사람이 볼 때, -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행, -> 진입할 때, 방문체크 하고 gNum++ (그룹수) -> bfs(0) 플래그 0으로 진입 3. bfs(0) -> bfs수행 하는데, flag가 0인 부분으로 진입 4. 적록색약인 사람이 볼 때, -> 먼저 check 배열 초기화, gNum = 0으로 변경 -> 맵을 순회하며 R을 G로 바꾸거나 혹은 G를 R로 다 바꿔버림. 5. 적록색약인 사람이 볼 때 기능 실행 -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행, -> 진입할 때, 방문체크 하고 gNum++ (그룹수) -> bfs(1) 플래그 ..
2020. 3. 18.
[ 백준 17471 ] 게리맨더링 (C++)
[문제보기] [해결과정] 1. input : n, arr (int형) 배열에 각각의 인원수 담기 -> 2차원 vector에 각각의 점에 간선 긋기 2. dfs(int count, int r(레드갯수), int b(블루갯수)) -> count != n+1 이라면, color에 색칠 후에 dfs(count+1, 색칠한곳+1, 색칠안한곳) 전송 -> count == n+1 이라면 아래 3번 수행 3. function -> red, blue 각각의 진영 갯수 0으로 초기화 -> redSum, blueSum 각각의 총합 0으로 초기화 -> 방문 체크 배열(check) 초기화 -> rf, bf 플래그 초기화 -> 1~N까지 점을 돌며, 레드 진영 한번, 블루 진영 한번.. 각각 한번씩 정점을 큐에 넣고 그 색에 대..
2020. 2. 27.
[ 백준 1405 ] 미친 로봇 (C++)
[문제보기] [해결과정] 1. input : n, double 형 d[4] ( 동, 서, 남, 북 ) -> d[i]/=100으로 해서 소수점으로 변환 2. 동, 서, 남, 북으로 이동하는 것을 맵에서 check 하기 위해서 map배열을 만들어준다. -> 맵의 가장 중앙 지점을 방문 처리 한다. 3. 맵의 가장 중앙 지점 부터 dfs 실행 -> dfs(y,x, cnt, p) cnt는 dfs count이고, p는 확률(소수)를 담을 변수 -> 만약, 단순한 경로(겹치지 않는 경로) 일 경우 ret += p -> 현재까지의 확률을 정답란에 저장 -> 만약, 단순한 경로가 아닌 경우(이미 방문한 지점을 방문) 패스 4. output : 소수점 11자리 까지 지정하여 출력 -> cout.precision(11);..
2020. 2. 26.