알고리즘 모음(C++)

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

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