전체 글

https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 문제 https://katastrophe.tistory.com/70 이전 포스팅 참고 ( 단절점 ) 풀이 단절점 찾기랑 원리가 같다. 다른점은 DFS를 진행할때 부모노드를 기록해 나가는 것. 만약 정점 A의 자식노드보다 더 낮은 값이 DFS결과로서 리턴이 되면 우회로가 존재 그렇지 않다면 해당 노드는 단절점이므로 , 이 단절점의 부모노드와의 Edge를 list에 넣고 ..

https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 문제 풀이 단절점이란 쉽게말해 아무 정점 X 가 있고 X의 자식들끼리 서로 이동할 때 , 꼭 X를 지나야만 왕래가 가능하면 단절점이라고 부른다. 즉 , X를 지나지 않고 다른 우회경로를 통해서 지날 수 있다면 X는 단절점이 아니게 된다. 그럼 우회경로가 있는지 어떻게 알아낼수 있을까 아무 정점 하나 잡아서 DFS를 돌리면서 정점이 처음 방문될때 마다 방문순서를 매겨주자..

https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 문제 풀이 두 통나무 차이를 최소로 했을 때의 , 차이의 최대값을 구하면되는 문제이다. 난이도 차이가 크게 나지 않게하려면 우선 내림차순으로 정렬을 한 다음 양쪽으로 하나씩 넣어주면 된다. 양쪽으로 교차로 넣어줘야 하기때문에 Deque를 써서 addFirst와 addLast 메서드를 이용했다. 넣기전에 원래 있던 값과 새로 들어가야할 값 두개의 차이값이 최대값이면 갱신을 해주는식으로 하고 마지막..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 풀이 [마감일 , 점수] 쌍으로 여러 입력이 주어지는데 , 예제를 보자 [6 , 5] [4, 60] 의 경우 6일마감 과제는 4일차 때 수행할 수 있지만 , 4일마감 과제는 6일차 때 수행할 수 없다. 즉 , 마감일이 늦은 순으로 처리를 먼저 하되 그때 처리할 수 있는 과제 중에서 점수를 가장 많이 주는것을 해야한다. 결론적으로는 주어진 입력에 대해서 1. 마감일이 늦은 순으로 내림차순 정렬 2. 점수를 많이주는 순으로 내림차순 정렬 ..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제 풀이 단순 그리디 접근 방법으로 풀 수 있다. 1. 상자랑 크레인을 입력받아 무거운 순 으로 정렬 2. 크레인 갯수 만큼 상자를 순회하여 만약 크레인이 이 상자를 적재 가능하면 상자리스트에서 제거 3. 다음 크레인으로 상자를 순회하여 적재가능하면 또 제거 .. 이런식으로 반복 4. 크레인을 순회할때마다 시간1초씩 늘려주고 , 상자리스트가 is.Empty()면 끝 1 2 3 4..

https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 문제 풀이 학생들이 각자 받고싶은 책의 범위들에서 적절하게 분배 해 줘야하는데 만약 1번 학생이 1,2,3 의 책 번호를 골랐고 2번 학생이 2,3 책 번호를 골랐다고 하면 2번 학생은 1번책을 받지 못하기때문에 1번 학생에게 우선 1번책을 주고 그다음 2번학생에게 2번 or 3번의 책을 줘야한다. 다른예시로 1번학생이 1,2의 책 번호를 골랐고 2번학생이 2,3의 책 번호를 3번 학생이 2,3을 골..

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 문제 풀이 처음엔 한 가방에 하나의 보석밖에 못넣는다고 적힌것 못 보고 Knapsack 문제 + 가방이 여러개 ..? 라고 접근할 뻔 했다가 산으로 갈 뻔 했다.. 접근방법 용량이 작은 가방과 무게가 작은 보석 순으로 천천히 순차적으로 보고 , 조건에 맞으면 그 가방에 보석을 넣는 방식으로 하면 된다. => 그리디 접근 가령 , 예제 2..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 풀이 그냥 완전 그리디 노가다.. 1보다 큰 수들 => 높은 수 순으로 2개씩 묶음 , 나머지들은(1이 있거나 하나 남았거나) 그냥 합산 0보다 작은 수들 => 2개씩 묶으면 양수가 되기때문에 제일 작은 수 순으로 2개씩 묶음. 하나 남은 음수는 0 이 있으면 그냥 패스 하거나 0이 없으면 그냥 더해주면 끝 1보다 큰수 , 0 , 0보다 작은수를 list 3개 만들어서 각각 따로 넣어주고 ..