목록전체 글 (540)
알고리즘 모음(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2645 2645번: 회로배치회로를 n×n의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)는 범위 밖에 있는 격자를 제외하고 상, 하, 좌, 우 4개의 이웃 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자www.acmicpc.net복잡했던 다익스트라 문제였습니다.A와 B를 최소 비용으로 이을려고 할 때의 비용을 구하는 문제입니다. 격자판 위에 다른 회로가 있을 수도 있습니다. A와 B를 이을 때, 선이 다른 회로의 위에 있을 경우, K의 비용이 들어가고, 다른 회로가 없을 경우에는 1의 비용이 들어갑니다. 따라서, 처음으로는 다른 회로가 어떻게 있는지를 구하는 것이 중요합니다. 입력에서 (3, 3, 9, 3..
문제 링크입니다. https://www.acmicpc.net/problem/2398 2398번: 3인통화첫 번째 줄에는 두 개의 정수가 있다. 첫 번째 정수 n(1 ≤ n ≤ 1000) 는 전화망에 있는 스위치의 개수를 나타내며, 두 번째 정수 m은 스위치와 스위치를 연결하는 링크의 개수를 나타낸다. 단, 같은www.acmicpc.net다익스트라와 백트래킹을 이용한 문제였습니다.3자 통화를 할 때 드는 최소 비용과 이때의 연결된 링크의 갯수, 어떤 링크인지를 출력하는 문제입니다. 먼저 3자 통화를 하는데 필요한 최소 비용을 구하는 것부터 해보겠습니다. N개의 정점에서 세명의 위치까지의 최소거리를 구한 후 값을 더해 각 정점에서 출발했을 때의 값을 각각 구한다면 N(
문제 링크입니다. https://www.acmicpc.net/problem/1884 1884번: 고속도로첫 줄에 여러분이 준비해 둔 교통비 K가 주어진다. (0≤K≤10,000) 둘째 줄과 셋째 줄에는 각각 도시의 숫자 N과 도로의 숫자 R이 주어진다. (2≤N≤100, 1≤R≤10,000) 이후 R개의 줄에 각 도로의 정보가 www.acmicpc.net다익스트라를 이용한 문제입니다. 제한된 비용 안으로 목적지까지 가려고 할 때, 최소 거리를 구하는 문제입니다. 여기서 생각해볼 것은, 같은 정점이라도 다른 비용으로 방문할 수 있습니다. 그렇다면 항상 적은 비용으로 도달하는 경우가 최고의 경우이냐 하면 그건 아닙니다. 따라서, 같은 정점이라도 다른 비용으로 도착할 경우를 생각해, 2차원 배열을 이용해 모든..
문제 링크입니다. https://www.acmicpc.net/problem/24042 24042번: 횡단보도당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net1번에서 N번 정점까지 횡단보도를 통해 이동할 때 최소 이동 시간을 구하는 문제입니다. 문제에서 주의할 점은 횡단보도가 한번에 바뀌는 것이 아닌, 번호 순서대로 바뀐다는 점입니다. 1번 -> 2번 -> ……… -> M번 횡단보도 순으로 바뀝니다. 여기서 생각해봐야 할 점이 5번 도로를 지났다고 했을 때, 7번 도로를 건넌다고 한다면 2분을 기다린 후 건너면 됩니다. 그렇다면 5번 ..
문제 링크입니다. https://www.acmicpc.net/problem/2307 2307번: 도로검문그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸리www.acmicpc.net다익스트라를 사용해 푸는 문제입니다.도로를 하나 제한했을 때, 지연시킬 수 있는 최대 시간을 구하는 문제입니다. 모든 길을 제한한다고 한다면, 도로의 수가 5,000개이기에 다익스트라를 5000개를 확인을 해야합니다. 따라서, 다른 방법을 이용해야 하는데, 생각을 해본다면, 최단 거리일 떄의 길을 제외하고 제한한다면, 값은 항상 최단 거리의 값이 될 것입니다. 문제에서 주어진 그림으로 확인..
문제 링크입니다. https://www.acmicpc.net/problem/15439 15439번: 베라의 패션베라는 상의 N 벌과 하의 N 벌이 있다. i 번째 상의와 i 번째 하의는 모두 색상 i를 가진다. N 개의 색상은 모두 서로 다르다. 상의와 하의가 서로 다른 색상인 조합은 총 몇 가지일까?www.acmicpc.netN개의 색상을 가진 상하의가 있을 때, 다른 색으로 만들 수 있는 조합의 가짓수를 구하는 문제입니다. 먼저 N*N을 한 뒤, 모든 경우를 구하고, N개를 빼 같은 색상으로 만들 때의 경우를 빼줍니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #includ..
문제 링크입니다. https://www.acmicpc.net/problem/2476 2476번: 주사위 게임첫째 줄에는 참여하는 사람 수 N이 주어지고 그 다음 줄부터 N개의 줄에 사람들이 주사위를 던진 3개의 눈이 빈칸을 사이에 두고 각각 주어진다. www.acmicpc.net조건문을 이용해 푸는 문제입니다.조건문을 사용해 같은 숫자가 3개일 때, 2개일 때, 없을 때를 나눈 뒤, 문제에 맞게 상금을 구합니다. N번을 반복한 후, 가장 큰 상금을 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF LLONG_MAX..
문제 링크입니다. https://www.acmicpc.net/problem/10886 10886번: 0 = not cute / 1 = cute준희는 자기가 팀에서 귀여움을 담당하고 있다고 생각한다. 하지만 연수가 볼 때 그 의견은 뭔가 좀 잘못된 것 같았다. 그렇기에 설문조사를 하여 준희가 귀여운지 아닌지 알아보기로 했다.www.acmicpc.net입력되는 1과 0의 개수를 샌 뒤, 더 많이 입력되는 수를 비교해 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #define INF LLONG_MAX #define F first #de..
문제 링크입니다. https://www.acmicpc.net/problem/6603 6603번: 로또입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net백트래킹을 이용한 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; int N; vector num; int Select[14]; int arr[14]; void solve..
문제 링크입니다. https://www.acmicpc.net/problem/13907 13907번: 세금첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ Dwww.acmicpc.net다익스트라를 통해 탐색할 때, N번 지점을 몇 번을 거쳐 방문하는지를 확인해야하는 문제였습니다.세금을 인상한 횟수가 30,000회, N이 1,000개 이하이기에 다익스트라를 사용할 때, 세금을 인상하면서 탐색을 하면 무조건 시간초과가 됩니다. 따라서, 다익스트라는 한번만 사용하고 해당 값을 통해 다른 값을 도출해..
문제 링크입니다. https://www.acmicpc.net/problem/13308 13308번: 주유소표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도www.acmicpc.net다익스트라와 다이나믹 프로그래밍이 사용된 문제였습니다. 이 문제는 1번부터 N번점까지 이동할 때, 필요한 최소 비용을 구하는 문제입니다. 이전에 지났던 점을 다시 지날 수 있으며, 기름을 싼 곳에서 전부 채워온 후 한번에 이동할 수 있기에 어느 정점에서, 어떤 기름값으로 채웠을 때 드는 최소 비용을 저장해줘야 했습니다. 따라서, 값을 저장해주는 배열을 ‘위치+..
문제 링크입니다. https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net다익스트라를 사용하는 문제입니다. 정해진 지점에서 시작을 하지 않는다는 것이 특징이였습니다.면접 장소가 주어졌을 때, 면접 장소에서 가장 멀리 떨어진 곳을 찾는 문제입니다. 주어진 어느 지점에서 출발하는 것이 아니기 때문에 어디서 시작해야 할지를 찾아야합니다. 만약에 N개의 지점에서 모두 확인해본다면 100,000개의 지점에서 ..