본문 바로가기

C++156

[백준] 4803번 - 트리 (C++) 문제 및 풀이 문제) 백준 - DFS - 트리 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 1번 노드부터 탐색하면서 트리의 개수를 계산합니다. 그래프에서 노드의 개수와 간선의 개수를 계산하여 cntEdge(i) / 2 == cntNode(i) - 1을 통해 트리 여부를 판별합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/480.. 2022. 2. 12.
[백준] 3184번 - 양 (C++) 문제 및 풀이 문제) 백준 - DFS - 양 https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net DFS를 통해 각 영역을 구분합니다. 영역을 구분하면서 영역에 존재하는 양과 늑대의 개수를 세어줍니다. 양이 많을 경우 양의 개수만 더하고, 늑대가 많을 경우 늑대의 개수만 더해주면 해결할 수 있습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/.. 2022. 2. 12.
[백준] 1032번 - 명령 프롬프트 (C++) 문제 및 풀이 문제) 백준 - 구현 - 명령 프롬프트 https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 첫 번째 문자열과 두 번째 이후 문자열을 비교하여 만약 다를 경우 '?'를 저장합니다. C++ 소스코드) 2022. 2. 12.
[백준] 21000번 - Archer Vlad (C++) 문제 및 풀이 문제) 백준 - 물리학 - Archer Vlad https://www.acmicpc.net/problem/21000 2022. 2. 10.
[백준] 18290번 - NM과 K (1) (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - NM과 K (1) https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 백트래킹으로 해결합니다. valid함수로 인접 여부를 판별하며, solve함수로 선택된 점과 더한 부분합을 계산하여 선택된 점이 K이면 최댓값을 갱신합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/18290_NM%EA%B3%BCK.. 2022. 2. 9.
[백준] 9421번 - 소수상근수 (C++) 문제 및 풀이 문제) 백준 - 에라토스테네스의 체 - 소수상근수 https://www.acmicpc.net/problem/9421 9421번: 소수상근수 양의 정수 n의 각 자리수의 제곱의 합을 계산한다. 그렇게 해서 나온 합도 각 자리수의 제곱의 합을 계산한다. 이렇게 반복해서 1이 나온다면, n을 상근수라고 한다. 700은 상근수이다. 72 + 02 + 02 = www.acmicpc.net 1부터 N까지 차례로 소수와 상근수 판별을 하여 둘 다 만족할 경우 출력합니다. 소수 판별은 에라토스테네스의 체를 활용하여 해결했습니다. 상근수는 판별은 상근수 변환을 이용하여 변환할 때마다 set에 insert 합니다. 만약, set에 변환된 숫자가 존재할 경우 cycle이 돌아 상근수가 아니므로 false를 return 합니.. 2022. 2. 9.
[백준] 2304번 - 창고 다각형 (C++) 문제 및 풀이 문제) 백준 - 자료 구조 - 창고 다각형 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 입력을 받을 때, 제일 긴 막대 기둥의 인덱스를 저장합니다. 먼저 오름차순(기둥이 길어지는 부분)을 계산합니다. 스택에 높이를 push 하여 다음 높이가 더 클 경우 push, 작을 경우 기존 스택에 가장 긴 높이의 넓이를 result에 더합니다. C++ 소스코드) Full Code) https://github.com/Chocochip10.. 2022. 2. 9.
[백준] 22869번 - 징검다리 건너기 (small) (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 징검다리 건너기 (small) https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 0번째부터 오른쪽으로 출발하여 N-1번째까지 도착할 수 있는지 확인합니다. cache[idx]를 통해 idx번까지 도달 여부를 저장해 1일 경우 가능, -1일 경우 미방문, 0일 경우 불가능으로 판단합니다. C++ 소스코드) Full Code) https://github.co.. 2022. 2. 8.
[백준] 6550번 - 부분 문자열 (C++) 문제 및 풀이 문제) 백준 - 문자열 - 부분 문자열 https://www.acmicpc.net/problem/6550 6550번: 부분 문자열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다. www.acmicpc.net 문자열 s가 문자열 t의 부분 문자열로 존재하는지 확인하는 문제였습니다. t의 문자열을 처음부터 탐색하면서 s와 같을 경우 idx를 1 증가시킵니다. 만약 idx가 s 문자열의 길이와 같을 경우 true를 return 합니다. C++ 소스코드) 2022. 2. 8.
반응형

티스토리툴바