알고리즘 모음(C++)

문제 링크입니다 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를 시작합니다.(좌표를 큐에 넣..

문제 링크입니다. https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 기존의 BFS문제들과는 달리 물이 차오르는 것을 염두해두고 풀어야하는 문제입니다. 따라서 물의 좌표를 저장하는 큐와 고슴도치의 좌표를 저장하는 큐를 만들어야합니다. 고슴도치는 물이 차오를 예정인 곳으로 갈 수 없기 때문에 물을 먼저 차오르게 한다음 고슴도치를 이동했습니다. 물의 좌표에서 상하좌우로 물을 먼저 채운다음 고슴도치를 BFS를 통해 갈 수 있는 곳을 찾은 후, 이차원 배열 check..