[문제 풀이] 영상 참고 www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include #include #include using namespace std; int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 }; int field[101][101] = { 0, }; int visited[101][101] = { 0, }; int* alti; int n,cnt; queue q; void bfs(int alt, int cnt); int main() { int ans = -1; cin >> n; vector alti; for (int ..
Koala - 2기
[문제 풀이] 영상 참고 www.youtube.com/watch?v=I0Dq42C0h8w&feature=youtu.be&ab_channel=%EC%B2%9C%EC%88%98%ED%99%98 [코드] #include #include #include #include #include #include using namespace std; int n, m, v; vector a[1001]; bool visited[1001] = { 0, }; stack s; void dfs(int v); void bfs(int v); int main() { ios_base::sync_with_stdio(0); int ltemp, rtemp; cin >> n >> m >> v; while (m--) { cin >> ltemp >> ..
1. 그래프 기초 강의 youtu.be/GXM1-xHIbxc 2. bfs, dfs 기초 강의 youtu.be/9gM3lnhENMA 3. bfs, dfs 문제 강의 * 영상이 긴 관계로 강의 설명 부분에 각 문제별 영상 시간을 올려드릴테니, 경우에 맞게 넘어가시면 되겠습니다! youtu.be/I0Dq42C0h8w
www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오...
http://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을..
www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1≤N≤100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번 www.acmicpc.net N개의 [강의 번호, 강의 시작시간, 강의 종료시간]이 있을 때, 강의 시간이 겹치지 않고 배정하기 위해 필요한 최소한의 강의실 개수를 구하라 이는 이미 시작한 강의의 종료시간이 새로 시작할 강의의 시작시간보다 작으면 강의실의 낭비를 줄일 수 있다. 먼저 강의 목록 중 시작시간과 종료시간을 입력받아 오름차순으로 정렬한다. //typedef pair pii; for (int i = 0; i < n; i..
youtu.be/HSQ77EeiiaI
2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net 큐, 덱으로는 돌아가는 식의 문제를 내는 것이 국룰인것 같습니다. 이 문제도 반전 요세푸스와 풀이 과정은 비슷하나, 첫 입력 인덱스를 기억해야 한다는 것이 까다롭습니다. 그래서 pair로 덱에 입력을 받겠습니다. 비교할 때는 first를 통해 비교하고, 출력할 때는 second를 출력할 것입니다. [정답코드 보기] #include #include #include #include #include #include #include #include #include using namespace std..
출처 : www.acmicpc.net/problem/13975 문제 여러 장의 소설이 각각 다른 파일에 저장되어 있다. 소설을 모두 쓰면, 각 장이 쓰인 파일을 합쳐 최종적 완성본인 단 하나의 파일만을 남겨두어야 하는데, 이 과정에서 두 개의 파일을 합치고, 합친 파일이나 다른 두 개의 파일을 계속 두 개씩 합쳐나가야 한다. 두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총합을 계산하시오. ex. 40, 30, 30, 50 -> 40, (30 + 30), 50 -> (40 + 50), 60 -> 90, 60 -> 150 이때, 비용은 60 + 90 + 150 = 300 이 된다. 풀이 더보기 우선순위 큐를 사용하는 아주 웰 ..
출처 : www.acmicpc.net/problem/1477 문제 다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 이 때 세울 수 있는 휴게소의 조건은 다음과 같다. 이미 휴게소가 있는 위치는 세울 수 없다. 고속도로의 마지막 점에 세울 수 없다. 정수 위치에만 세울 수 있다. M개의 휴게소를 적절히 배치하여 휴게소가 없는 구간의 최댓값을 최소로 만들어라. 풀이 더보기 이 문제는 휴게소가 없는 구간의 최댓값을 이분 탐색으로 시뮬레이션하는 방법이 있긴 하나, 여기서는 우선순위 큐를 이용해 풀어보겠습니다. 우선 단순하게 생각해서 풀이를 떠올려..
출처 : www.acmicpc.net/problem/7662 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 주어진 정수 값 자체를 우선순위라고 했을 때, 주어진 ..
