알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있www.acmicpc.net다익스트라를 이용한 문제입니다. 비교할 값이 2개가 있기에 조심해야 되는 문제였습니다.시작 지점에서 출발해 도착 지점까지 갈 때, 쓰레기 위를 지나는 값, 근처를 지나는 값의 최소를 출력하는 문제입니다. 쓰레기의 위치는 g로 주어지며, 근처는 상하좌우인 4방향입니다. 따라서, 쓰레기의 위치를 받을 때, 근처의 위치도 같이 표시해주면 됩니다. 먼저 함수 탐색..

문제 링크입니다. https://www.acmicpc.net/problem/1486 1486번: 등산첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000www.acmicpc.net다익스트라를 2번 이용해 푸는 문제입니다. 높이를 의미하는 알파벳이 주어지고 N*M이 주어질 때, 세준이가 오를 수 있는 가장 높은 높이를 구하는 문제입니다. 세준이는 (1, 1)에서 시작하고, 높이의 차는 ‘T’이하만 이동할 수 있습니다. 다른 위치로 이동할 때 드는 시간은 1. 현재 위치보다 낮은 곳을 이동할 경우 -> 1 2. 현재 위치보다 높은 곳을 이동 -> ..

문제 링크입니다. https://www.acmicpc.net/problem/11952 11952번: 좀비첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2,www.acmicpc.net다른 목적을 가진 다익스트라를 2번 사용해 푸는 문제였습니다.좀비가 점령한 도시가 있을 때, 다른 도시들을 거쳐 N번 도시로 갈 수 있는 최소 비용을 구하는 문제입니다. 점령된 도시와 거리가 S 이하인 도시는 숙박비를 q로, 아닌 도시는 p로 받습니다. 먼저, 도시들이 점령 당한 도시들로부터 얼마나 떨어져 있는지를 구해야 합니다. 여기..

문제 링크입니다. https://www.acmicpc.net/problem/13911 13911번: 집 구하기첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사www.acmicpc.net다익스트라를 시작할 때, 맥도날드 정점과 스타벅스 정점을 각각 전부 넣고 시작하는 문제였습니다. 맥도날드의 위치들과 스타벅스의 위치들이 주어질 때, 두 가게의 거리의 합이 최소가 되는 지점의 번호를 출력하는 문제입니다. 먼저 맥도날드와 스타벅스로 부터 떨어져 있는 거리를 구해야합니다. 가게가 하나가 아닐 수도 있기에, 어떤 지점을 ..

문제 링크입니다. https://www.acmicpc.net/problem/16681 16681번: 등산첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net다익스트라를 양쪽에서 이용해 푸는 문제입니다.목표 지점을 정해, 집에서 목표지점까지는 높이를 무조건 올라가게, 목표지점부터 고려대학교까지는 높이를 무조건 내려가는 방식으로 할 때, 얻을 수 있는 최대 가치는 얼마인지 구하는 문제입니다. N의 갯수가 100,000이기에, 목표지점 하나마다 경우를 확인해보기에는 경우가 많아 시간초과가 됩니다. 따라서, 시작지점과 끝점에서 시작에..

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