본문 바로가기

PS(Problem Solving)221

[백준] 3584번 - 가장 가까운 공통 조상 (C++) 문제 및 풀이 문제) 백준 - 트리/DFS - 가장 가까운 공통 조상 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net DFS를 통해 한 노드에 대하여 조상으로 올라가 트리를 순회하여 Set에 모든 조상을 저장합니다. 그 후, 공통 조상을 탐색할 다음 노드에 대하여 마찬가지로 트리를 순회합니다. 이때 탐색한 조상이 Set에 있을 경우, 그 조상을 반환하여 출력합니다. C++ 소스코드) Full Code) ht.. 2022. 2. 19.
[백준] 6118번 - 숨바꼭질 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 2022. 2. 19.
[백준] 2302번 - 극장 좌석 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 극장 좌석 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net VIP 좌석을 제외한 연속된 i개 자리에 대하여 피보나치 수열 i개로 사람들을 앉힐 수 있습니다. 동적 계획법을 통해 피보나치 수를 구하고 입력으로 들어온 VIP 좌석마다 ans에 곱합니다. C++ 소스코드) 2022. 2. 18.
[백준] 21919번 - 소수 최소 공배수 (C++) 문제 및 풀이 문제) 백준 - 수학 - 소수 최소 공배수 https://www.acmicpc.net/problem/21919 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net N개의 숫자 배열 A를 입력받아 각 숫자의 소수 판별 후 최소 공배수를 구하면 해결할 수 있었습니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21919_%EC%86%8C%EC%88%98%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutions.. 2022. 2. 18.
[백준] 21610번 - 마법사 상어와 비바라기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 마법사 상어와 비바라기 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 문제에 제시된 설명대로 구현하면 해결할 수 있는 문제였습니다. int A[i][j]: i 행 j 열에 담긴 물의 양 int cloud[i][j]: i 행 j 열의 구름 여부, 1일 경우 이전 구름/2일 경우 생성된 구름 chgRange(x): x 범위 예외 처리 moveCloud(d, s): 구름을 d의 방향으로 s만큼 이동 rain(): 구.. 2022. 2. 17.
[백준] 14712번 - 넴모넴모 (Easy) (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 넴모넴모 (Easy) https://www.acmicpc.net/problem/14712 14712번: 넴모넴모 (Easy) 네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 www.acmicpc.net C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/14712_%EB%84%B4%EB%AA%A8%EB%84%B4%EB%AA%A8.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutio.. 2022. 2. 17.
[백준] 2167번 - 2차원 배열의 합 (C++) 문제 및 풀이 문제) 백준 - 구현 - 2차원 배열의 합 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 배열에 저장된 수에서 인덱스의 쿼리가 주어질 때 합을 구하는 문제였습니다. C++ 소스 코드) 2022. 2. 17.
[백준] 14722번 - 우유 도시 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 우유 도시 https://www.acmicpc.net/problem/14722 14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 동적 계획법을 통해 동쪽, 남쪽을 탐색하면 우유를 마시거나, 마시지 않으면서 최대 우유 개수를 탐색합니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/14722_%EC%9A%B0%EC%9C%A0%EB%8F%84%EC%8B%9C.cpp GitHub -.. 2022. 2. 16.
[백준] 18353번 - 병사 배치하기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 병사 배치하기 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 열외 해야 하는 최대 병사 수를 구하는 문제였습니다. 문제의 관점을 바꾸자면 내림차순을 만들 수 있는 최대 병사 수를 구하는 문제이므로 11722번-가장 긴 감소하는 부분 수열 문제와 유사하다는 것을 알 수 있습니다. ㅁ 2021.03.09 - [PS(Problem Solving)/백준_BOJ] - [백준] 11722번 - 가장 긴 감소하는.. 2022. 2. 16.
반응형

티스토리툴바