컴퓨터 공학 기초
-
백준 1260 (DFS와 BFS)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 21. 03:10
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해당 문제는 N개의 정점이 주어지면 해당 정점들의 간선의 정보가 주어지면 해당 정점들의 간선을 통해 연결 되어 있는 정점들을 DFS, BFS로 탐색을 하며 탐색되는 각 정점을 출력하는 문제이다. 이때 하나의 정점에 연결 된 간선이 여러개라면 숫자가 작은 정점을 방문하는 조건이 있다. 주의 사항 : 하나의 정점에 간선이 여러개일 경우 숫자가 작은 정점부터 방문해..
-
백준 13023(ABCDE)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 20. 21:48
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 해당 문제는 N명의 사람으로 구성 된 그룹이 있으며, 해당 그룹은 M개의 인원들이 친구 관계를 맺고 있다. 이때 아래와 같은 조건의 친구관계를 가지는 그룹일 경우 1 출력 아닐경우 0을 출력하는 문제이다. 주의 사항 : N명의 사람이 최대 2000 명이기 때문에 2000번을 탐색하기에는 시간초과가 발생한다. 따라서 Vector 에 n 번째 인원의 친구 정보만 push 하는 과정을 통해 오직 친구인 사람의 번호만 Vector 에 저장하도록 한다. #include #include using namespac..
-
백준 11723 ( 집합 )컴퓨터 공학 기초/알고리즘 (구현) 2020. 8. 20. 17:22
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 해당 문제는 주어지는 명령의 조건에 따라 처리해주면서 알맞게 출력만 해주는 문제이다. 이때 한가지 주의해야 할 점이 있는데 일반 cin, cout 사용시 시간초과가 발생함으로 printf 와 scanf 사용 혹은 ios_base::sync_with_stdio(false); cin.tie(NULL); 위의 구문을 사용하여 입출력을 사용한다. 풀이 : #include #include #include using namespace std;..
-
백준 1182 (부분수열의 합)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 20. 03:58
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 해당 문제는 숫자 N 과 S 그리고 N개의 정수가 주어질 때 N개의 숫자를 조합하여 더했을 때 주어진 S가 나올 수 있는 모든 경우를 구하는 문제이다. 따라서 DFS를 이용한 조합을 추출하고 해당 조합의 총합이 S인지만 비교해주면 되는 문제이다. 이때 주의해야 할 점은 따로 조합의 크기는 없으므로 재귀가 수행 할 때마다 현재 선택된 수의 총합을 갱신하며 S값과 ..
-
백준 1759 (암호 만들기)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 19:19
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해당 문제는 정수 L, C가 주어지며 C개의 문자들이 주어지면 해당 문자 중 L개의 문자를 가지고 조합을 만들어 해당 조합이 오름차순일때만 출력하는 문제이다. 추가적인 조건은 다음과 같다. 1. 출력 형태역시 문자조합의 오름차순으로 출력을 해야한다. 2. L개의 길이를 가지는 문자열은 항상 1개 이상의 모음, 2개 이상의 자음이 포함되어야 한다. #include #include #include #inc..
-
백준 6603 (로또)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 17:58
https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 양수 K와 K 개수의 수열이 주어질 때 해당 수열로 만들 수 있는 조합을 출력하는 문제이다. #include #include using namespace std; int n; vector nList; vector results; int used[50]; void dfs(int level, int idx){ if (level == 6){ for (int i = 0; i < 6; +..
-
백준 10971 (외판원 순회 2)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 17:38
https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 해당 문제는 N개의 도시가 주어질 때 N개의 도시를 빠짐없이 모두 순회하면서 드는 최소비용을 구하는 문제이다. 이때 도시를 순회하는 과정에 다음과 같은 규칙을 지켜야 한다. 1. 이미 방문한 도시는 재방문 하지 못 한다. 2. 단 마지막 도시에서 가장 처음 도시로 돌아가는 경우에는 재방문이 가능하다. 3. i 번째 도시에서 j 번째 도시로 이동 할 경우..
-
백준 10819 (차이를 최대로)컴퓨터 공학 기초/알고리즘 (브루트포스) 2020. 8. 19. 16:40
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 해당 문제는 N개의 정수가 주어질 때 해당 정수를 아래에 식에 맞춰 계산 했을 때 나올 수 있는 최대한의 수를 구하는 문제이다. 이때 주어진 정수의 위치는 사용자가 바꿀 수 있으므로 순열을 이용하여 주어진 정수들의 숫자를 바꾸어 모든 탐색을 진행한다. 이렇게 탐색을 진행하면서 바꾼 수열에 식을 대입하여 결과 값만 비교하면 풀리는 문제이다. 풀이 : #include #include using namespace s..