BOJ C++ 알고리즘 공부
-
[스택] 에디터 (백준 1406)(C++)BOJ C++ 알고리즘 공부 2024. 2. 15. 22:28
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 1. 문제 개요 편집기가 지원하는 명령어가 다음과 같을 때, 초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 대, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 가정한다. L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시) D 커서를 ..
-
[스택] 탑 (백준 24930)(C++)BOJ C++ 알고리즘 공부 2024. 2. 13. 21:48
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 1. 문제 개요 일직선 위에 N개의 서로 높이가 다른 탑이 있다. 각 탑의 꼭대기에서 왼쪽 방향으로 레이저 신호를 발사할 때, 발사한 탑의 높이보다 높은 높이를 가진 탑은 이를 수신할 수 있다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 있을때, 높이가 6, 9인 탑에서 발사한 레이저는 받을 수 있는 탑이 없다. 반면에 높이가 5, 7인 탑에서 발사된 레이저는 높이가 9인 탑에..
-
[DFS/BFS] 단지번호붙이기 (2667)(C++)BOJ C++ 알고리즘 공부 2024. 2. 4. 18:16
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1. 문제 개요 그림과 같이 정사각형 모양의 지도가 있을 때, 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 위, 아래, 양, 옆에 나란히 있는 칸을 이웃이라 할 때, 이웃인 단지의 수를 구하는 문제. 그림에서 단지의 수는 3이 된다. 2. 입출력 3. 문제 풀이 DFS를 사용해서 해결할 수 있는 문제. 2차원 배열에 방문 여부를 저장하고, 이미 방문한 집은 방문하지 않도록 한다. 집을 방..
-
[DP] 동물원 (1309)(C++)BOJ C++ 알고리즘 공부 2024. 1. 28. 21:23
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. 문제 개요 2*N 배열에 사자를 가둘 때, 위 아래 양 옆으로 사자 붙어 있지 않게 하는 배치는 몇 가지인지 구하는 문제이다. 이 때, 가두어야하는 사자의 수는 정해져있지 않으며, 사자가 한 마리도 없는 경우도 하나의 경우의 수로 포함된다. 2. 입출력 3. 문제 풀이 처음에는 왜인지 백트랙킹 문제라고 생각했다.. 근데 DP로 풀으라는 말을 보고 다시 생각해보니 금방 풀렸다. 규칙은 다음과 같다. N=1인 배열이 있다면 사자를 가두는 경우의 수는 다음과 같이 3가지일 것이다. 그 다음에, N=2인 배열의 경우의 수를 구하려 ..
-
[DP] 오르막 수 (11057)(C++)BOJ C++ 알고리즘 공부 2024. 1. 24. 01:32
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 1. 문제 개요 수의 자리가 오름차순을 이루는 수를 오르막 수라고 할때, 수의 길이 N으로 만들 수 있는 오르막 수의 개수를 구하는 문제. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 1234, 1113 등이 오르막 수이다. 2. 입출력 3. 문제 풀이 N*M의 2차원 배열을 사용하여 N자리 오르막 수 중 숫자 M으로 끝나는 수의 개수를 구한 후,..
-
[DP] 1로 만들기 (1463)(C++)BOJ C++ 알고리즘 공부 2024. 1. 22. 17:01
1. 문제 개요 정수 N이 주어졌을 때, N이 3으로 나누어 떨어지면 3으로 나누기, 2로 나누어 떨어지면 2로 나누기, N에서 1을 빼기, 이렇게 세 가지의 연산을 사용하여 N을 최대한 빠르게 1로 만드는 문제이다. 사용한 연산의 최솟값을 구한다. 2. 입출력 3. 문제 풀이 다이나믹 프로그래밍을 통해 주어진 수를 1로 만들 수 있는 연산의 조합 중 최솟값을 구한다. 예를 들어, 주어진 수가 10인 경우, 10은 5에 2를 곱하거나, 9에 1을 더하여 만들 수 있다. 그렇다면 10이 1이 되는 최솟값은 숫자 5가 1이 되는 연산의 최솟값+1과 숫자 9가 1이 되는 연산의 최솟값 둘 중에 더 작은 값을 채택하면 된다. 이를 수식으로 나타내면 다음과 같다. count[10] = min(count[9]+1,..
-
[에드혹] 오락실에 간 총총이 (26071)(C++)BOJ C++ 알고리즘 공부 2023. 6. 1. 17:12
https://www.acmicpc.net/problem/26071 26071번: 오락실에 간 총총이 모든 곰곰이를 하나의 칸에 모으기 위해, 총총이가 최소 몇 번 버튼을 눌러야 하는지 구하시오. www.acmicpc.net 1. 문제 개요 게임의 화면은 NxN 크기의 칸으로 나누어져 있고, 각 칸에는 곰곰이가 있거나 또는 비어있다. 화면에는 최소 한 마리의 곰곰이가 존재한다. 게임은 상하좌우 네 개의 버튼을 눌러서 진행할 수 있다. 각 버튼을 누르게 되면, 화면에 있는 모든 곰곰이들이 그 버튼에 해당하는 방향으로 한 칸 움직이게 된다. 만약 이미 화면의 끝에 있어서 그 방향으로 이동하지 못하는 곰곰이들은 가만히 있는다. 버튼을 잘 눌러서 모든 곰곰이들을 하나의 칸에 모으게 되면, 승리하게 된다. 승리하..