전체 글
-
백준 2667 (단지번호붙이기)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 24. 15:58
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 해당 문제는 0과 1로 이루어진 격자판이 주어지며 해당 격자판의 1은 집을 의미하고 0은 빈 집을 의미한다. 이때 집들의 모임인 단지를 정하고 단지의 개수와 각 단지마다 포함 된 집의 개수를 오름차순으로 출력하는 문제이다. 단지는 상하좌우로 인접한 집들의 집합이다. 풀이 : 2 중 for를 사용하여 격자판을 모두탐색 하며 만약 처음 방문하는 집일 경우에 BFS를 통한 상하좌우 방향의 집 탐색을 진..
-
백준 11724 (연결 요소의 개수)컴퓨터 공학 기초/알고리즘 (BFS, DFS) 2020. 8. 21. 03:30
https://www.acmicpc.net/problem/11724 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 해당 문제는 N개의 정점과 M개의 간선들이 주어질 때 하나로 연결 된 요소들의 총 개수를 구하는 문제이다. 풀이 : for 문을 사용하여 N개의 정점을 BFS를 사용하여 탐색하며 탐색한 정점은 check 해주며 Check 되지 않은 정점이 있을 경우 해당 정점에서 다시 BFS를 사용하여 정점을 탐색하는 과정을 반복하면서 check되..
-
백준 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;..
-
백준 15658 (연산자 끼워넣기2)카테고리 없음 2020. 8. 20. 04:49
https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수� www.acmicpc.net 해당 문제는 N의 정수가 주어지며 N개의 수로 이루어진 수열이 주어진다. 마지막 줄에는 연산자의 개수가 주어지게 되는데 이때 4개의 숫자가 주어지며 각각의 수가 의미하는 것음 사칙연산자의 개수와 같다. 위와 같은 입력이 주어질 때 아래의 조건을 만족시키면서 N개의 수를 모두 연산한 결과 값들 중 최대값과 최소값을 구하는 문제이다. 조건은 다음과 같다. ..
-
백준 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..