작심 24/7

2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net BFS와 재귀로 풀었다. x, y의 촌수를 구해야 할 때 x를 루트로 잡고 x부터 y가 나올 때까지 BFS 해주었다. 만약 y를 만나지 못한다면 -1을 출력했다. 무방향 그래프이므로 입력받을 때 벡터[x]=y, 벡터[y]=x 둘 다 값을 넣어준다. BFS 해줄 때 다음 노드로 넘어갈 때마다 촌수를 +1 해주었고 현재 노드와 연결된 모든 노드들을 검사한 후(검사하는 노드마다 방문 체크) 검사가 다 끝나면 이전 노드로 돌아가기 전에 촌수를 -1 해주..

11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 모든 정점을 둘러보며 현재 정점이 가리키는 정점을 다시 현재 정점으로 삼는 방식으로 재귀로 DFS를 구현했다. 한 번 방문한 정점은 visited로 표시해준 후 다시는 방문하지 않도록 해주었다. 한 정점의 연결고리 검사가 모두 끝나면 visited를 0으로 다시 초기화해주고 그다음 정점의 연결고리들을 모두 검사해준다. #include using namespace std; void Dfs(int N, int idx, int graph[][101], int visited[]) { for (..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 무방향 그래프 이므로 u와 v를 입력받으면 벡터[u]=v, 벡터[v]=u 를 넣어준다. 벡터가 empty될 때까지 방문하지 않은 곳만 DFS로 탐색해주고 한 번이라도 방문한 곳은 visited로 표시해준다. 여기서 주의할 점은 간선을 가지지 않는 정점도 하나의 연결 요소로 취급하므로 먼저 벡터가 empty인 애들의 수부터 전부 카운트 해주는 것이 포인트이다. #include #include usin..

1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net N개의 정수 중에 순서 상관없이 1~N만큼 뽑아 더하는 조합 문제이다. 조합 함수를 만들어서 중간 중간에 원소의 합을 더해주며 그 합과 S를 비교하며 카운트 해주면 된다. #include #include using namespace std; int arr[21] = { 0 }; int cnt = 0, sum = 0, res = 0; vector v; void combination(int N, int S) { if (cnt ==..

2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 9명 중에 순서 상관없고 중복 없이 7명을 찾아내는 것이므로 조합이다. 조합 함수를 만들어서 재귀로 풀어주면 된다. 결과 벡터에 있는 값 < 현재 배열에 있는 값인 경우에만 push와 카운트, sum에 더해주고 재귀호출 해주며 카운트가 7이 될 때까지 반복한다. 카운트가 7이고 sum이 100이면 출려해주고 끝내고 아닐 경우엔 돌아와서 pop, 카운트와 sum에서도 빼준 뒤 다음 배열의 값으로 넘어간다. #include #include #include using name..

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 조합 문제의 변형이다. N에 따라 나눌 수 있는 팀의 경우의 수를 살펴보면 N 팀 2 1 | 2 ==================== 4 1, 2 | 3, 4 1, 3 | 2, 4 1, 4 | 2, 3 ==================== 6 1, 2, 3 | 4, 5, 6 1, 2, 4 | 3, 5, 6 1, 2, 5 | 3, 4, 6 1, 2, 6 | 3, 4, 5 1, 3, 4 | 2, 5, 6 1, 3, 5 | 2, 4, 6 1, 3, 6 | 2, 4, 5 1, 4, 5 | 2..

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 순열 문제의 변형이다. 연산자 배열을 만들어 나열시켜주고 순열 알고리즘 처럼 check 배열을 만들어 갔다 온 곳은 체크 해준다. 재귀를 이용해서 끝까지 계산 해주고 완료되면 최댓값 최솟값 비교를 해준다. 재귀가 끝나고 돌아오면 값을 이전 값으로 다시 만들어주며 반복한다. #include #include using namespace std; int Max = -1111111111, M..

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹으로 푸는 문제이다. 1. 같은 행에 숫자 N이 없을 때 2. 같은 열에 숫자 N이 없을 때 3. 같은 3*3 칸에 숫자 N이 없을 때 이 세 조건을 충족시키면 다음 빈칸을 채우러 가고 만족시키지 못한다면 N+1을 하여 다음 숫자를 넣어본다. N을 9까지 증가시켰는데 빈칸을 채우는데 실패하면 이전 빈칸의 숫자가 잘못된 것이므로 돌아간다. 모든 빈칸이 채워지는 경우엔 finish에 표시한 후 모두 빠져나와 출력시키면 끝 #include #include us..