알고리즘 모음(C++)

문제 링크입니다. 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/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 주어진 map에서 흰 돌을 2개 놓을 때, 검은색 돌을 최대한 많이 죽을 수 있는 개수를 구하는 문제입니다. 돌을 놓을 수 있는 곳에 모두 놓아본 뒤, 잡을 수 있는 돌의 개수를 전부 확인해보면 됩니다. 1. 2개의 돌을 차례대로 놓는다. 2. 돌을 놓은 뒤, 검은 색 돌을 몇개를 잡을 수 있는지를 확인해본다. 3. 모든 경우를 확인한 ..

문제 링크입니다. 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..

문제 링크입니다. https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제에 푸는 방법이 있었기에 쉽게 풀 수 있었습니다. 조건을 따라 사용하면 되지만, 이전에 구했던 값을 또 구한다면 시간초과가 생깁니다. 따라서 새로운 값을 구할 때마다 저장해준뒤, 재사용하면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define INF 98765432..

문제 링크입니다. https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 트리가 주어졌을 때, 쿼리를 기준으로 자신을 포함한 자식노드의 개수를 구하는 문제입니다. 루트노드는 주어졌기 때문에 루트노드부터 시작해 자식의 개수를 찾으면 됩니다. 간선을 저장할 때, 양뱡향으로 저장하기에 부모와 자식 노드의 구분은 이전에 방문을 했는지 여부를 저장하는 check 배열을 통해 했습니다. 자식노드일 경..

문제 링크입니다. https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 자두나무에서 자두가 1초 간격으로 떨어집니다. 2개의 자두나무 중 한 곳에서만 떨어질 때, W이하로 움직이면서 받을 수 있는 자두의 개수를 구하는 문제입니다. (시작점은 1번 자두나무입니다.) 예제 입력의 경우에는 2~3초 동안은 1번 -> 2번 자두나무로 이동 -> 4~5초동안 2번 -> 1번 자두나무로 이동 -> 6~7초동안 1번 이와 같이 움직여 7개를 먹습니다. 이 문제를 풀기 위..

문제 링크입니다. https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net N일이 주어졌을 때, 알약을 먹을 수 있는 방법의 경우를 구하는 문제입니다. 온전한 약을 꺼낸 뒤, 반을 먹고 반은 내려놓는 행위는 W, 반이 남은 알약을 꺼내 먹는 행위를 H라고 합니다. 1일만 약을 먹는다고 했을 때, 나올 수 있는 경우는 WH인 1개뿐이며 2일만 약을 먹는다고 했을 때, 나올 수 있는 경우는 WHWH, WWHH으로 2개가 됩니다. 3일의 경우에는 WHWHWH, WWHHWH,..

문제 링크입니다. https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 격자가 주어지고 중간에 무조건 거쳐야할 점이 주어질 때, 총 경우의 수를 구하는 문제입니다. 수학 중 경우의 수 문제를 풀 때, 한번씩은 풀어봤을 문제입니다. (X, Y)번 격자를 갈 때의 경우의 수는 다음과 같이 구해집니다. 1 1 1 1 1 1 1+1 2+1 ... ... 1 2+1 3+3 ... ... 1 3+1 4+6 ... ... 따..