알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13398 13398번: 연속합 2첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net다이나믹 프로그래밍을 이용해 푸는 문제입니다.연속된 수를 선택해 수열의 최댓값을 구하는 문제입니다. 이때, 수열의 수 중, 하나를 빼고 더할 수 있기에 점화식을 구해야했습니다. 저는 배열을 2차원 배열로 만들었습니다. [X][2]로 만들어, [X][0]은 수를 하나도 빠짐없이 전부 더할 때, [X][1]은 수열 중, 하나를 빼고 더할 경우로 만들었습니다. [X][0]에서 구할 수 있는 i..

문제 링크입니다. https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net다익스트라를 이용하는 문제입니다.가중치가 주어졌을 때, 연결할 수 있는 최솟값을 출력하는 문제입니다. 연결했을 때의 최솟값만 출력하면 되기에 다익스트라 알고리즘을 이용해서 풀어주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #i..

문제 링크입니다. https://www.acmicpc.net/problem/1719 1719번: 택배첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 거리를 출력하는 것이 아닌, 최단거리를 가기 위해서 처음으로 가는 정점을 출력하면 됩니다. 즉, 기본적인 다익스트라를 사용하면서, 거리가 바뀔 때마다 가는 정점을 같이 바꿔줘야한다는 의미입니다. 먼저 1~N까지 모두 출력해야 하기에 반복문을 통해 i번 정점을 기준으로 탐색을 시작할 수 있도록 해줍니다. 정점에서 탐색을 시작했다면 이제 갈 수 ..

문제 링크입니다. https://www.acmicpc.net/problem/1446 1446번: 지름길첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이www.acmicpc.net다익스트라를 이용한 문제입니다. 현재 위치에서 지름길을 통해 이동하거나, 다음 위치로 이동하는 과정을 거쳐, 원하는 목적지까지 최소 이동거리로 이동하는 문제입니다. 먼저 Distancs배열을 만들어줍니다. 해당 배열을 N번째 위치를 얼마의 최솟값으로 이동할 수 있는지를 저장하는 배열입니다. -> 해당 배열은 처음에 무한히 큰 값으로 초기화를 해줘야합니다. 초기화를 통해 큰 ..

문제 링크입니다. https://www.acmicpc.net/problem/13903 13903번: 출근 첫 번째 줄에는 보도블록의 세로, 가로 R, C(1 ≤ R, C ≤ 1,000)크기가 주어진다. 다음 R개의 줄에는 C개의 문자로 이루어진 보도블록의 초기 상태가 주어진다. (가로 블록은 0로 표시되고, 세로 블록 www.acmicpc.net BFS를 이용한 문제입니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #define INF 987654321 #define F first #define S second using namespace std; int R,..

문제 링크입니다. https://www.acmicpc.net/problem/5341 5341번: Pyramids The input will be a sequence of integers, one per line. The end of input will be signaled by the integer 0, and does not represent the base of a pyramid. All integers, other than the last (zero), are positive. www.acmicpc.net 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespa..

문제 링크입니다. https://www.acmicpc.net/problem/17025 17025번: Icy Perimeter Please output one line containing two space-separated integers, the first being the area of the largest blob, and the second being its perimeter. If multiple blobs are tied for largest area, print the information for whichever of these has the smallest per www.acmicpc.net 영문으로 되어있는 문제이지만 간단했습니다. 문제를 해석해보자면, '#'으로 연결된 가장 큰 그룹을 ..

문제 링크입니다. https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 다른 BFS와 달리 map의 N번째 칸에 도달했을 때, 더 이상 이동못하는 것이 아닌, 1번째 칸으로 이동하게 됩니다. 이를 코드로만 짤 수 있다면 나머지는 다른 BFS문제와 같게 푸시면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #..

문제 링크입니다. https://www.acmicpc.net/problem/28074 28074번: 모비스 주어진 문자열에 포함된 알파벳 대문자들을 이용해 MOBIS를 만들 수 있으면 "YES", 그렇지 않으면 "NO"를 출력한다. www.acmicpc.net 주어진 단어로 'MOBIS' 단어를 만들 수 있는지 물어보는 문제입니다. 알파벳 5개가 나왔는지를 저장할 수 있는 배열을 만든 뒤, 해당 배열 안의 값이 전부 0이 아니기만 하면 됩니다. 자세한 것은 코드를 참고해주세요. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF 987654321 #define F f..

문제 링크입니다. https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 산봉우리의 갯수를 구하는 문제입니다. 여기서 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격좌들의 집합이라고 정의합니다. 산봉우리와 인접한 격좌는 모두 산봉우리의 높이보다 작아야한다고 합니다. 예시를 통해 산봉우리를 확인해본다면 해당 그림과 같이 3개가 됩니다. 따라서, 1이상의 같은 격좌로 이루어져 있으며, 8방향으로 이어지고, 주변보다..

문제 링크입니다. https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net Dp를 이용해 푸는 문제입니다. 주어진 2개의 문자열에서 공통으로 가장 긴 문자열을 찾는 문제입니다. 위의 문자열을 X, 아래 문자열을 Y라고 할 때, X문자열의 문자를 1번부터 하나씩 늘려가면서 Y와 비교했습니다. 사용된 논리는 LCS와 비슷합니다. 아래를 확인해주세요. https://junseok.tistory.com/170 백준 9251 - LCS(C++) 문제 ..

문제 링크입니다. https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net DP를 이용해 푸는 문제였습니다. 주어진 수에서 +, -를 이용해 식을 만들 때, N번째 수의 값을 만들 수 있는지 확인하는 문제입니다. 1~N-1까지의 수를 이용해야하는데, 한 수를 거칠 때마다 경우가 2배씩 늘어납니다. 그렇다면 최악의 경우 2^99개까지 경우가 만들어지는데, 이러면 시간초과가 생깁니다. 문제의 조건을 본다면, 계산할 때마다 나오는 값의 범위가 항상 0..