알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 다이나믹 프로그래밍 문제였습니다. 문제만 읽으면 간단히 BFS, DFS로 풀 수 있는 문제지만 해당 알고리즘을 사용한다면 시간초과가 됩니다. 따라서 동적계획법과 회귀를 사용하여 푸는 문제입니다. 문제 조건입니다. 1. 자신이 있는 곳에서 상,하,좌,우 한곳으로 이동한다. 2. 이동한 곳에는 전에 있던 곳보다 대나무가 많아야한다. 3. 1,2조건을 만족하면서 최대한 오래 살..

문제 링크입니다 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 스택(stack)이란 기본적인 자료구조로 한쪽 끝에서만 자료를 넣고 뺄수 있는 LIFO(last in first out) 형식을 따릅니다. 스택 push, pop등 다양한 연산을 사용할 수 있습니다. push(num) -> num을 가장 위에 하나 추가한다. pop() -> 가장 위에 있는 항목을 제..

문제 링크입니다. https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A 4 -> 8 -> 81 -> 162 이와 같은 방법으로 최소 횟수는 5입니다. 1. 주어지는 수의 범위가 10^9이기 때문에 int 범위는 넘습니다. 따라서 long long 형으로 선언해줍니다. 2. 처음에 큐에 (A,0)를 저장해서 BFS를 시작합니다. 3. X*2, X*10+1 각각 B ..

문제 링크입니다 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지의 위치와 공기 청정기의 위치가 주어지고 일정 시간이 지난 뒤 남은 미세먼지의 갯수를 구하는 문제입니다. 미세먼지의 확산 방법부터 보겠습니다. 미세먼지는 자신이 있는 위치에서 상하좌우로 퍼집니다.(위 사진과 같이 퍼집니다.) 공기 청정기의 순환 방식도 보겠습니다. 화살표를 따라 공기가 움직이고 미세먼지는 공기를 따라 움직입니다. 이때 미세먼지가 공기 청정기 안으로 빨려간다..

문제 링크입니다 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제의 조건입니다. 입력 받은 문자열이 폭발 문자열을 포함한다면 해당 문자열이 사라집니다. mirkovC4nizCC44 - 입력 받은 문자열 C4 - 폭발 문자열 이라고 한다면 mirkovC4nizCC44는 폭발 문자열을 포함하고 있기에 mirkovC4nizCC44 -> mirkovnizCC44 -> mirkovnizC4 -> mirkovniz 가 됩니다. 시간 제한..

문제 링크입니다 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 지민이의 이야기의 진실을 알고 있는 사람들을 피해서 거짓말을 말할 수 있는 파티의 최대 갯수를 찾는 문제입니다. 진실을 알고 있는 사람이 있는 파티는 거짓말을 하면 들통이 남으로 무조건 진실을 말해야하며 진실을 모르는 사람만 있는 파티인 경우에는 사람들이 진위 여부를 가릴 수 없어 지민이는 거짓말을 합니다. 진실을 알고 있는 사람들을 - A, B, C, D, E ..... 진실을 모르는 사람..

문제 링크입니다 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 입력된 단어를 정렬하는 문제입니다. cmp라는 함수를 사용해서 길이, 사전순으로 정렬을 하는 방식으로 풀었습니다. 정렬을 다한 후에는 출력 for문에서 같은 문자를 제외하고 출력했습니다. cmp함수에서 첫번째로 length를 이용해 길이를 비교합니다. 길이가 다르다면 올바른 return 값을 해주면 됩니다. 만약 길이가 같다면 단어를 사전 순으로 비교해서 올바른 retu..

문제 링크입니다 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net n가지 종류의 동전이 있습니다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶은데 그러면서 동전의 개수가 최소가 되도록 하려고 합니다.( 각각의 동전은 몇 개라도 사용할 수 있다. ) 이때 동전의 최소 갯수를 구하는 문제입니다. 저는 다이나믹 프로그래밍의 방법으로 접근했습니다. 1원부터 시작해서 원하는 값까지 계속 최솟값을 비교..

문제 링크입니다 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이 문제는 다이나믹 프로그래밍(동적 계획법)의 문제로 계산했던 값을 재사용하는 방식으로 해결했습니다. 스티커를 하나 고른다면 그 스티커의 상하좌우 스티커는 사용할 수 없게 됩니다. 스티커에 점수가 각각 부여되었을 때 최대의 값을 가질 수 있도록 스티커를 때내는 방법을 찾아야합니다. (1,1) (1,2) (1,3) (1,4) (1,5) (2,1) (2,2) (2,3) (2..

문제 링크입니다 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 7569 토마토 문제와는 다르게 2차원 BFS를 요구하는 문제입니다. 4방향 탐색을 위해서 arr,arr2 배열을 만들어줬습니다. 이중 for문으로 토마토를 입력받고, 익지 않은 토마토의 갯수와 익은 토마토를 큐에 넣는 작업을 동시에 했습니다. 입력이 끝나고 익지 않은 토마토의 갯수가 0개라면 바로 0을 출력해주고 0이 아니라면 BFS를 실행합니다. BFS 탐색 중..

문제 링크 입니다. https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 3차원 BFS를 요구하는 문제입니다. 3차원 배열을 선언할때 Z축을 맨 앞에, X,Y축 순서로 만들어야합니다. 예를 들면 tomato[z][x][y]입니다. 자세한 것은 코드를 참고해주세요! 3차원 BFS를 해야하기 때문에 기존의 4방향과는 다르게 6방향으로 탐색을 해줘야합니다. 처음 입력을 받을때 익지 않은 토마토의 갯수를 셉니다. 익지 않은 토마토의 ..

문제 링크입니다 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 기본적인 BFS,DFS문제입니다. 저는 BFS로 풀었습니다. 1이 집이 있는곳, 0이 집이 없는 곳을 뜻합니다. 1이 연속적으로 모여있을때 한개의 단지임을 나타냅니다. 위의 그림을 보면 3개의 단지가 있는 것을 볼 수 있습니다. 문제를 풀때 접근방법은 이중 for문을 통해서 첫번째 1를 찾습니다. 그후에 1의 좌표를 입력받은 뒤에 그 좌표에서부터 BFS를 시작합니다.(좌표를 큐에 넣..