전체 글
-
백준 31065 Farmer John Actually Farms [C++]알고리즘 2024. 1. 14. 19:34
문제 https://www.acmicpc.net/problem/31065 31065번: Farmer John Actually Farms Farmer John is growing $N$ ($1 \leq N \leq 2\cdot 10^5$) plants of asparagus on his farm! However some of his plants have genetic differences, so some plants will grow faster than others. The initial height of the $i$th plant is $h_i$ inches, and after eac www.acmicpc.net 문제 해설 농부 존은 농장에서 식물을 키우고 있다. 각각 식물의 초기 크기는 h_i 이고..
-
백준 31063 Candy Cane Feast [C++]알고리즘 2024. 1. 14. 15:57
문제 https://www.acmicpc.net/problem/31063 31063번: Candy Cane Feast Farmer John's cows have quite the sweet tooth, and they especially enjoy eating candy canes! FJ has $N$ total cows, each with a certain initial height and he wants to feed them $M$ candy canes, each also of varying height ($1\le N,M\le 2\cdot 10^5$). FJ pl www.acmicpc.net 문제 해설 1 번째줄의 입력으로 소의 마리수와 먹이의 개수가 주어진다. 2 번째 줄의 입력으로 소의 크기가..
-
백준 1260 DFS와 BFS [C]알고리즘 2023. 2. 11. 16:06
문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 우선, DFS 와 BFS에 관련하여 설명은 다른 게시물을 통해 추후 남길 예정이니 해당 게시물을 통해 확인 바란다. N 제한이 작으므로 N*N 인접행렬(아래 코드에서 matrix) 을 통해 정점간 연결되어있는지를 표현할 수 있다. 해당 matrix를 가지고 DFS, BFS의 탐색 방법을 통해 V부터 방문된 탐색 결과를 출력해주면 된다. 코드 #inc..
-
백준 14502 연구소 [C]알고리즘 2023. 2. 11. 14:35
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 N과 M제한이 작으므로 모든 경우의 수를 다 해보는 브루트포스 알고리즘 문제이다. 다음과 같이 풀이해주면 될 것으로 보인다. 1. 모든 비어있는 공간 (아래 코드에서 empty)에 대하여 3개 벽을 세워본다 2. 모든 위치에 있는 바이러스가 어느 위치까지 퍼져나갈 수 있는가를 구해준다. 3. 바이러스가 퍼져나가지 않은 공간의 갯수를 세주고 각 경우에 대해 최댓값을 구해준다. 아래 코드에서는 dfs로..
-
백준 11866 요세푸스 문제 0 [C]알고리즘 2023. 2. 4. 14:58
문제 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 백준 2164 카드2 문제 의 응용버전이다. 백준 2164 문제에서는 1회 만큼 Q를 pop을 하고, 1회 만큼 Q의 front 값을 다시 Q에 push를 하고 Q를 pop 해주는 방식으로 문제를 해결해주었다면, 이번 문제에서는 K-1회 만큼 Q의 front 값을 다시 Q에 push를 하고, Q를 pop 하며 1회만큼 Q를 pop해준다는 점이 차이점이다. 자세한 내용은 코드를 통해 확인해보도록 하자 코드 #include #include using namespace std..
-
백준 2164 카드2 [C]알고리즘 2023. 2. 4. 14:42
문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 큐의 push, pop을 활용하여 문제 조건을 잘 이행할 수 있냐를 물어보는 문제인 것으로 보인다. 제일 위에 있는 카드를 버리고 (pop), 제일 위에 있는 카드를 빼내서, 맨 아래에 넣는다 (push+pop)를 통하여 구현할 수 있다. 자세한 사항은 밑에 있는 코드를 통해 확인해 보도록 하자. 코드 #include #include using namespace std; int N; q..
-
백준 20975 Just Stalling [C]알고리즘 2023. 1. 14. 21:10
문제 https://www.acmicpc.net/problem/20975 20975번: Just Stalling The first line contains $N$. The second line contains $N$ space-separated integers $a_1,a_2,\ldots,a_N$. The third line contains $N$ space-separated integers $b_1,b_2,\ldots,b_N$. All heights and limits are in the range $[1,10^9]$. www.acmicpc.net 문제 해설 농부 존은 N마리의 소를 가지고 있는데 각 소의 키는 a1 .. aN이다. 그의 외양간에는 N개의 칸이 있으며 각 칸에는 b1...bN의 높이 제..
-
백준 1874 스택 수열 [C]알고리즘 2023. 1. 14. 17:00
문제 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 풀이 4, 3, 6, 8, 7, 2, 5, 1 과 같은 스택 수열이 있다고 가정해보자. 맨 처음 숫자 4를 만들기 위해서는 [1,2,3,4]를 차례대로 스택에 PUSH해야한다. S = [1,2,3,4] 그리고 나서 4,3은 차례대로 POP을 하여 스택 수열을 만족시킬 수 있다. 그렇다면, 그 다음 숫자인 6을 ..