알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍www.acmicpc.net주어진 문제를 활용해 풀 수 있는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; int N; int dp[41]; int cnt1, cnt2; int..

문제 링크입니다. https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어www.acmicpc.netmap을 사용하는 문제입니다.원소의 갯수가 200,000개 까지이기에 찾기 위해서 이중for문을 사용한다면 바로 시간초과가 생기는 문제입니다. 따라서, map을 사용해, 빠르게 찾는 방법을 사용해야합니다. 첫번째 수열과 두번째 수열을 입력 받은 뒤, 서로의 map에 저장해주고, for문을 통해 수열의 값이 다른 수열에 있는지 찾으면 됩니다. 자세한 것은 코드를 참고해주세요.#de..

문제 링크입니다. https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.netmap을 사용해, enter문자열이 입력된다면 값을 추가, leave문자열이 들어온다면 이름을 찾은 뒤 삭제해주면 됩니다. map을 찾는 이유는 n의 값이 2,000,000이기에 for문을 사용한다면 시간초과가 생기기 때문입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #incl..

문제 링크입니다. https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 730에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다.www.acmicpc.net다차원 배열을 사용하는 다익스트라 문제입니다.소가 길을 건널 때, 주어진 조건에 따라 최소 시간을 구하는 문제입니다. (1, 1) ->(N, N)으로 가면서, 3번째 방문하는 곳은 항상 풀을 먹어야 합니다. 이동할 때마다 이동시간 T가 추가됩니다. 항상 최단 횟수로 갔을 때, 최소 비용이 나온다는 보장을 할 수 없습니다.(위의 예시가 그렇습니다.) 따라서 다익스트라를..

문제 링크입니다. https://www.acmicpc.net/problem/14215 14215번: 세 막대첫째 줄에 a, b, c (1 ≤ a, b, c ≤ 100)가 주어진다.www.acmicpc.net 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; int x, y, z; int maxi, sum; int main() { cin.tie(0); cout.tie(0); cin >> x >> y >> z; sum = x + y + z; maxi = max(x, y); maxi = max(maxi, z..

문제 링크입니다. https://www.acmicpc.net/problem/5073 5073번: 삼각형과 세 변각 입력에 맞는 결과 (Equilateral, Isosceles, Scalene, Invalid) 를 출력하시오.www.acmicpc.net주어진 3변을 이용해, 어떤 삼각형인지 판별하는 문제입니다. 삼각형이 성립하는 조건을 유의해서 풀어주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; int x, y, z; int main() { cin.tie(0); cout.tie(0); w..

문제 링크입니다. https://www.acmicpc.net/problem/10101 10101번: 삼각형 외우기문제의 설명에 따라 Equilateral, Isosceles, Scalene, Error 중 하나를 출력한다.www.acmicpc.net문제 조건 따라 조건문을 사용하는 문제였습니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include using namespace std; int x, y, z; int main() { cin.tie(0); cout.tie(0); cin >> x >> y >> z; if(x + y + z != 18..

문제 링크입니다. https://www.acmicpc.net/problem/9063 9063번: 대지첫째 줄에는 점의 개수 N (1 ≤ N ≤ 100,000) 이 주어진다. 이어지는 N 줄에는 각 점의 좌표가 두 개의 정수로 한 줄에 하나씩 주어진다. 각각의 좌표는 -10,000 이상 10,000 이하의 정수이다. www.acmicpc.net주어진 점들로 최소 넓이의 직사각형을 구하는 문제입니다.점들이 N개 주어졌을 때, 모든 점들을 포함하는 최소 넓이의 직사각형을 구하는 문제입니다. 좌표가 들어올 때마다, 직사각형의 X좌표 시작점과 끝점, Y좌표 시작점과 끝점과 계속 비교해 값을 갱신해 나가면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/9506 9506번: 약수들의 합어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다. n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.www.acmicpc.net약수들을 구할 수 있는지를 물어보는 문제입니다. 자신을 포함하지 않은 약수이니, 1부터 N/2까지 확인해, 나눠떨어지는지를 확인하면 됩니다. 나눠떨어지는 수를 전부 더한 뒤, 이들의 합이 N과 같은지 확인해면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #inc..

문제 링크입니다. https://www.acmicpc.net/problem/2151 2151번: 거울 설치첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net다차원 배열을 이용한 BFS로 풀 수 있는 문제였습니다.두 개의 문이 있을 때, 거울을 이용해 한쪽 문에서 다른 문을 볼 수 있도록 할려고 한다면 몇개의 거울을 사용해야되는지 구하는 문제입니다. 먼저 2개의 문의 위치를 저장한 뒤, 한 쪽 거울에서 BFS 탐색을 시작해줍니다. 여기서는 거울의 설치 갯수를 물어보는 문제이니, 배열 하나를 만들어 큰 값을 저장해줍니다. 그러..

문제 링크입니다. https://www.acmicpc.net/problem/20529 20529번: 가장 가까운 세 사람의 심리적 거리각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다.www.acmicpc.net경우를 나눈 뒤, 경우에 해당하는 방식으로 푸는 문제입니다.16개의 mbti를 중복이 가능하게 주어졌을 때, 3명의 심리적 거리를 구하는 문제입니다. 심리적 거리를 구하는 방법은 4개의 알파벳 중, 다른게 있을 때마다 1씩 늘어나게 됩니다. 여기서 N값이 주어질 때, 100,000개까지 주어집니다. 따라서 100,000개를 전부 확인해본다면 무조건 시간 초과가 생길 것입니다. 따라서, 시간을 줄일 방법을 찾아야하는데, 만약에 N이 17개가 주어졌다고 한다면, 16개의 mbti가 ..

문제 링크입니다. https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 반올림과 평균을 구하는 코드를 요구하는 문제입니다. 이 문제를 푸는 요점은 반올림을 하는 코드를 구할 수 있는지였습니다. 반올임을 하기 위해선, 일단 double형을 통해 소수점을 포함한 값을 저장합니다. 그 다음, 해당 값을 int형으로 변환시킨 값을 만들어줍니다. -> 해당 과정은 소수점을 없애줍니다. 두 값을 뺐을 때, 0.5이상이라면 +1을 해..