문제링크 : https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int K, V, E; vectorv[20001]; int visited[20001]; bool flag; //인접색깔 체크용 void dfs(int cur) { if(!visited[cur]) visited[cu..
문제링크 : https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; vectorv[100001]; int cost[100001]; void dfs(int cur) { for(int i=0; i> N >> M; for(int i=1; i> n; v[n].push_..
문제링크 : https://www.acmicpc.net/problem/24481 24481번: 알고리즘 수업 - 깊이 우선 탐색 3 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2번 노드이다. 2번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 4번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, R; vectorv[100001]; int visited[100001]; void dfs(int cur, int depth) { visited[..
문제링크 : https://www.acmicpc.net/problem/1889 1889번: 선물 교환 첫째 줄에 학생의 수 N(3 ≤ N ≤ 200,000)이 주어진다. 학생은 1부터 N까지 번호가 매겨진다. 이어서 다음 N개 줄에는 각 학생이 선물을 주고자 하는 두 학생의 번호가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, x, y; int inDegree[200001]; int check[200001]; //방문체크 vectorarr[200001]; //연결된 인원 vectorresult; //참여 인..
문제링크 : https://www.acmicpc.net/problem/24446 24446번: 알고리즘 수업 - 너비 우선 탐색 3 너비 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 2, 4번 노드이다. 3번 노드는 2번 또는 4번 노드의 자식이다. 5번 노드는 1번 노드에서 방문 될 수 없다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M, R; vectorv[100001]; int visited[100001]; void bfs() { memset(visited, -1, size..
문제링크 : https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result=-1; vectorv[100001]; void inorder(int node, bool flag) { if(node==-1) return; int left = v[node][0]; int..
문제링크 : https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, M; int dp[101][101]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(..
문제링크 : https://www.acmicpc.net/problem/25418 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int A, K; int visited[1000001]; int bfs() { queueq; q.push({A, 0}); while(!q.empty()) { auto[cur, cnt] = q.front(); q.pop(); if..
문제링크 : https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, a, b, result=-1; int arr[100001]; int visited[100001]; void bfs(int s) { queueq; q.push({a, 0}); //시작점, 점..
문제링크 : https://www.acmicpc.net/problem/14248 14248번: 점프 점프 첫 번째 줄에는 돌다리의 돌 개수 n이 주어진다.(1≤n≤100,000) 돌의 번호는 왼쪽부터 1번에서 n번이다. 다음 줄에는 그 위치에서 점프할 수 있는 거리 Ai가 주어진다.(1≤Ai≤100,000) 다음 줄에는 출 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result, s; int arr[100001]; bool visited[100001]; void dfs(int cur) { if(curN) return; //범위 조건 v..
문제링크 : https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result; vectorv; int dp[101]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i..
문제링크 : https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; char arr[1001]; int dp[1001]; bool check(char cur, char next) //BOJ 순서 확인 { if(cur=='B' && next == 'O') return 1; if(cur=='O' && next == 'J') retu..
문제링크 : https://www.acmicpc.net/problem/13325 13325번: 이진 트리 입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int k, tsize, result; int arr[1> k; tsize = 1 갭 x : return 1+2 = 3 11 -> 갭 x : return 1+4 = 5 35 -> 갭 2 : return 2+5..
문제링크 : https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N, result; int arr[1001], dp[1001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i=0; i>..
문제링크 : https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net #include using namespace std; typedef long long ll; typedef pair pii; const int MAX = 987654321; int N; int arr[5001]; int dp[5001][5001]; int func(int s, int e) { if(s>=e) return 0; /..