알고리즘 모음(C++)

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

문제 링크입니다. https://www.acmicpc.net/problem/17270 17270번: 연예인은 힘들어첫 번째 줄에는 약속 장소 후보의 수 V와 약속 장소를 연결하는 총 길의 수 M이 주어진다. (2 ≤ V ≤ 100, 1 ≤ M ≤ 1,000) 그리고 다음 M개의 각 줄에는 a, b, c 가 주어진다. a, b는 길의 시작과 끝이www.acmicpc.net다익스트라를 이용해 풀 수 있는 문제였습니다.지헌이와 성하가 만날 때, 최적의 장소를 구하는 문제입니다. 최적의 장소는 구하는 방법은 1. 둘이 만날 때, 거리는 최소가 되어야 합니다. 2. 출발지는 장소 후보에서 제외됩니다. 3. 지헌이가 성하보다 더 일찍 도착해야 합니다. 4. 위의 조건을 모두 만족하는 장소가 있다면, 지헌이한테 가장..

문제 링크입니다. https://www.acmicpc.net/problem/23801 23801번: 두 단계 최단 경로 2첫째 줄에 정점의 수 N (10 ≤ N ≤ 100,000), 간선의 수 M (10 ≤ M ≤ 300,000)이 주어진다. 다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타www.acmicpc.net다익스트라를 사용하는 문제입니다.무조건 들려야하는 점이 존재할 때, 해당 점을 하나라도 들리면서 갈 수 있는 최소 비용 경로를 구하는 문제입니다. 들려야하는 점의 갯수가 최대 N-3개이니 100,000개 정도가 주어집니다. 따라서, X->K + K->Z를 점마다 확인하는 것은 시간 초과가 될 것입니다.(K를 들려야 하는 점으로 ..

문제 링크입니다. https://www.acmicpc.net/problem/22865 22865번: 가장 먼 곳$N$개의 땅 중에서 한 곳에 자취를 하려고 집을 알아보고 있다. 세 명의 친구 $A$, $B$, $C$가 있는데 이 친구들이 살고 있는 집으로부터 가장 먼 곳에 집을 구하려고 한다. 이때, 가장 먼 곳은 선택할www.acmicpc.net다익스트라를 이용하는 문제입니다.1 ~ N까지 중에서, 친구의 위치가 3개가 주어질 때, 최소 거리가 가장 긴 위치를 찾는 문제입니다. 1부터 시작해 1->1 ~ 1->N,,,,,,N->1 ~ N->N까지 모든 경우를 구한 뒤, 3지점까자의 각각의 거리를 비교해서 최솟값을 찾는 것은 다익스트라를 100,000번 돌려야 되기 때문에 시간초과가 생기게 됩니다. 따라..

문제 링크입니다. https://www.acmicpc.net/problem/20007 20007번: 떡 돌리기첫째줄에 N, M, X, Y가 공백으로 구분되어 입력된다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ 100,000, 1 ≤ X ≤ 10,000,000, 0 ≤ Y 다익스트라를 통해 거리를 구한 뒤, *2를 하면 됩니다. 거리가 가장 짧은 곳부터 오름차순으로 방문하기 때문에 거리를 구한 뒤, 정렬을 해주면 됩니다...

문제 링크입니다. https://www.acmicpc.net/problem/23793 23793번: 두 단계 최단 경로 1서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으www.acmicpc.net다익스트라를 이용한 문제입니다.문제 시간이 0.3초이며, N과 M의 값이 큰 만큼, 시간을 생각하면서 풀어야하는 문제입니다. 먼저, 문제를 풀기 위해 방향을 생각해보겠습니다. 두개를 출력하면 됩니다. 1. X -> Y -> Z를 들려서 올 때의 최소 비용 2. X -> Z(Y를 제외)로 올 때의 최소 비용 2번은 간단합니다. 다익스트라를 실행할 때, Y점에 도달한다면, 해당 경우를..

문제 링크입니다. https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net다익스트라 알고리즘을 활용한 문제입니다.문제를 풀기 위해선 1->N 점까지 가는 최단 거리가 1->민준->N 점으로 가는 최단거리와 같은 것인지를 알아야 했습니다. ->이 두 경우의 값이 같다면 항상 민준이는 건우를 도울 수 있기 때문입니다. 따라서 1->N까지 가는 다익스트라로 원래 최단 거리를, 1->민준 + 민준->N의 최단 ..

문제 링크입니다. https://www.acmicpc.net/problem/13424 13424번: 비밀 모임입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 1~N번 정점까지 친구들이 있는 곳까지 거리를 각각 구한 뒤, 이를 모두 비교하면 되는 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #define INF 21000..