https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 이 문제는 투 포인터를 통해 해결할 수 있다. K의 값에 따라 연속 수열에 들어올 수 있는 같은 값의 개수가 달라진다. 예시에 있는 3 2 5 5 6 4 4 5 7은 K가 2이므로 수열에 같은 값이 2개 이하 존재해야한다. 즉, 3 2 5 5 6 4 4와 2 5 5 6 4 4, 5 5 6 4 4, 5 6 4 4 5 7, 6 4 4 5 7, ... 이 가능하다. 이중 가장 긴 수열의 길이는 7..
분류 전체보기
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 활용해야한다. 노드간의 이동 방법과 가중치를 입력 받기 때문에 일반적인 다익스트라 알고리즘을 사용하면 된다. 출력 시 INF인 경우 INF를 출력하도록 출력만 신경쓰면 된다. #include #include #include using namespace std; #define INF 100000000 int V, E; int di..
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 이용해 해결할 수 있다. 최단 거리 K에 해당하는 노드를 구하면 된다. #include #include #include #define INF 100000000 using namespace std; vector nodes[300001]; int dist[300001]; int N, M, K, X..
1. 다익스트라 알고리즘? 다익스트라 알고리즘은 최소거리를 구할 때 사용하는 알고리즘이다. 다익스트라는 시작 노드로부터 모든 노드까지의 최소 거리를 구해준다. 다익스트라를 구현하기 위해서는 비용 배열, 방문 배열, 시작점에서 각노드까지의 비용 배열이 필요하다. weight 배열의 값을 통해 노드간의 연결을 판단한다. 특정 값이 있다면 연결되어 있다는 뜻이다. INF이면 연결되지 않았다는 뜻이다. weight 배열을 통해 단방향 노드나 양방향 노드로 만들 수 있다. 2. 다익스트라 알고리즘 구현 다익스트라 알고리즘의 순서는 다음과 같다. dist 배열의 값을 weight[시작 노드]의 값으로 초기화 시작점을 방문 표시 dist 배열에서 최소 비용 노드를 찾고 방문 처리. 이때 이미 방문한 노드는 무시 최소..
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 이 문제는 그리디 알고리즘을 사용하면 해결할 수 있다. 처음에 문제에 접근하였을 때 S를 T로 만들기만 하면 된다고 생각하였다. 가능한 방법은 2가지 방법인 S뒤에 A를 추가하거나 S를 뒤집고 B를 추가하는 방법만 존재한다. 따라서 S를 먼저 큐에 삽입한 후 큐에서 문자열 하나를 뽑는다. 2가지 방법대로 문자열을 수정한 후 다시 큐에 문자열들을 삽입한다. 이때..
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 이 문제는 그리디 알고리즘을 사용해야한다. 문제를 해결할 수 있는 방법은 다음과 같다. 보석을 무게 순서로 정렬하고, 가방에 담을 수 있는 보석의 최대 무게도 오름 차순으로 정렬한다. 위 과정을 거치면 가방에 담을 수 있는 무게를 가진 보석을 순서대로 뽑을 수 있다. 이후 우선순위 큐에 보석의 무게를 넣게 된다면 큐에는 가장 무거운 보석..
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 이 문제는 그리디 알고리즘을 사용해서 해결할 수 있다. 알파벳으로만 이루어진 숫자의 합이 최대가 되도록 하는 방법은 다음과 같다. 가장 높은 자릿수부터 9를 순차적으로 부여하면 합이 최대가 된다. 이때 같은 문자는 같은 값이 되어야하며, 같은 값인 문자는 존재하지 않게 해야한다. 처음 문제를 해결할 때 자릿수를 배열에 담아 배열을 정렬한 후 순차적으로 9부터 값을 부여하였다. 이러한 방법은 ..
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 이문제는 greedy 알고리즘을 활용해서 해결해야한다. 가장 적은 비교 횟수를 통해 카드를 정렬하기 위해서는 가장 작은 카드 뭉치들을 사용해서 값을 누적해야한다. 가장 작은 카드 2장을 뽑기 위해서는 배열을 정렬해서 카드를 뽑으면 된다. 처음 시도한 방법은 vector에 값을 담은 후 sort하여 카드를 뽑아 값을 누적하였다. 이러한 방법은 처음 뽑은 2장의 카드의 합이 이후에 뽑을..
