전체 글548 백준 2533 c++ "사회망 서비스(SNS)" -PlusUltraCode- https://www.acmicpc.net/problem/2533[필자 사고]트리 문제다. 다만 얼리어답터 라는 조건이 있는 문제.처음에 어떻게 접근해야 될지 몰랐다. 최소 갯수 , 브루트포스 등등 떠올렸고 역시 마지막에는 dp로 손길이 간다.dp[cur][0] , dp[cur][1] 이런식으로 점화식을 정의하면 현재 노드에서 서브트리의 얼리어 답터 수라고 생각하면 편하다. dp[now][0] += dp[next][1] 반드시 현재 now 가 0이면 다음꺼는 있어야 한다.dp[now][1] += min(dp[next[0], dp[next][1]) 둘중 최소값만 택하면 된다. 이런식으로 코드를 작성했다. 아래는 자세한 코드 해설이다.[코드 해설]1. 전체 개요이 프로그램은 백준 2533번 ‘사회망 서비스.. 2025. 10. 12. 백준 2143 c++ "두 배열의 합" -PlusUltraCode- https://www.acmicpc.net/problem/2143[필자 사고]이분 탐색 삘이 왔는데 어떻게 부분배열을 만들지가 고민이였다.문제의 범위를 보자.. N이 1000밖에 안된다.브루트포스로 모든 부분배열의 합을 구하면 백만개가 된다.시간복잡도로 널널하다.즉 이게 키 포인드라는 점이다. 각 브루트포스를 이용하여 배열의 모든 합들을 구한 뒤.T-aSum[i] = findNum 을 통해 이진탐색으로 나머지 B도 탐색하면 문제 해결이다. 아래는 자세한 코드해설이다.[코드 해설]코드 해설입력 처리 단계T: 두 배열의 부분합을 더했을 때 만들어야 하는 목표 합.N, M: 각각 배열 A와 B의 크기.배열 A, B를 입력받아 각각 vector로 저장한다.부분합 계산 단계배열 A의 부분합(aSum) 생성A의 모.. 2025. 10. 12. 백준 17471 c++ "게리맨더링" -PlusUltraCode- https://www.acmicpc.net/problem/17471[필자 사고]각 노드들을 이분법 으로 나누는 방법 뭐 없을까? 비트마스킹을 이용하여 이분화를 진행할 수 있다.이분화를 진행한 뒤에 BFS를 이용하여 실제로 인접한지 확인한다. 인접하지 않으면 false 인접하면 성공그리고 A와 N가 모두 인접했으면 answer 즉 population 차이를 갱신한다. 최소값으로 아래는 자세한 코드 해설이다.[코드 해설]1. bool BFS(vector& area, vector& selected)이 함수는 특정 선거구(area)가 연결되어 있는지 검사하는 역할을 한다.queue q를 사용하여 BFS(너비 우선 탐색)를 수행한다.visited 벡터는 각 구역이 탐색되었는지 여부를 기록한다.시작점으로 선거구의 .. 2025. 10. 10. 백준 4386 c++ "별자리 만들기" -PlusUltraCode- https://www.acmicpc.net/problem/4386[필자 사고]각 거리의 값들을 구한 뒤 == 크루스칼 알고리즘을 이용그 다음 해당 배열을 정렬하여 mst를 이용해서 값을 구했따. 아래는 자세한 코드 해설이다.[코드 해설]1. find(int a)이 함수는 주어진 노드 a가 속한 집합의 대표(루트)를 찾는 함수이다.크루스칼 알고리즘에서 사용하는 Union-Find(Disjoint Set) 구조의 핵심으로,현재 노드가 자기 자신을 부모로 가지고 있지 않다면 재귀적으로 부모를 따라가며 루트를 찾는다.또한 경로 압축(Path Compression)을 적용하여, 찾는 과정에서 만난 모든 노드의 부모를 루트로 갱신해준다.이로 인해 탐색 효율이 매우 높아진다.2. Union(int a, int b)두.. 2025. 10. 10. 이전 1 ··· 3 4 5 6 7 8 9 ··· 137 다음