https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. Logic - 기본적인 LIS문제이다. 이 문제가 LIS인 이유는 전깃줄이 교차하지 않아야한다는 것은 이전 전깃줄의 번호가 다음 전깃줄의 번호보다 커지면 안되고 항상 작은 번호여야하기 때문에 증가하는 부분수열이 될 수 밖에 없다. 다른 LIS문제와 다른점은 단지 입력 값을 pair로 받아 준 다음 A를 기준으로 오름차순 정리해주고 B를 기준으로 LIS를 찾아주면 된다. 공부겸 시간복잡도가 O(nlo..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. Logic 기초적인 Tow pointer 문제지만 여기선 세개의 용액을 구해야하기 때문에 아이디어가 필요하다. 문제를 처음 보고 떠오른 아이디어는 한용액은 고정으로 하고 나머지 두개만 고르면 되겠다! 이거였다. 그리고 내가 생각한 아이디어가 맞았다. 기본 로직을 적어보자면 1. 0번째 인덱스부터 n - 2번째 인덱스 까지 for문을 돌면서 고정할 용액을 정한다. 2. 남..
https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 1. Logic 처음 보면 무슨 문제가 싶지만 문제를 읽으면서 예제를 보면 LIS문제인것을 알 수 있다. 문제 푸는 로직을 나열해보자면 1. 입력을 받은 수들을 vector에 pair로 저장을 하고 A를 기준으로 오름차순 정렬한다. 2. lis vector의 back값과 계속 비교하여 LIS를 이루는 값이 들어오면 lis에 넣어주고 cnt를 올려준다. 혹은 탐색값이 lis의 back보다 더 작..
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. Logic - 기본 구성은 가장 긴 증가하는 부분수열 2, 3과 똑같다. 하지만 여기서는 역추적을 통해 LIS가 어떻게 구성되었는지 경로를 출력해야한다. 경로를 갱신해 줄 때 아무값이나 막 넣어주면 안되기 때문에 첫번째로 LIS인 수열에 대해서 입력해준다. 즉 이전에 들어간 숫자보다 더 큰 숫자가 나올경우 경로를 갱신해준다. 만약 이전에 들어간 숫자보다 작은 숫..
https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. Logic 이전 가장 긴 증가하는 부분 수열 문제에서는 DP를 사용해서 풀었다. DP를 사용하는 풀이에서는 전체를 돌면서 확인 하며 메모이제이션 했기때문에 시간복잡도가 O(N^2)이었다. 하지만 이 문제에서는 입력값이 엄청 많기 때문에 N^2으로 풀지 못하기 때문에 시간복잡도가 O(nlogn)을 가지는 이분탐색 기반으로 풀어야 한다. binary search를 구현해서 푸는 방법과 C++의 ..
https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. Logic 2252번 문제와 동일하게 위상정렬로 푸는 문제지만 살짝 다르다. 1766번 문제집은 문제를 푸는 조건이 있다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 이중 키포인트는 3번이다. 나는 위상정렬을 BFS를 활용하여 푸는데 1..
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. Logic 대표적인 위상정렬 문제 위상정렬이란? 비순환 방향 그래프(DAG: Directed Acyclic Graph)에서 정점을 선형으로 정렬하는 것. 만약 그래프가 순환이 있거나 양방향 그래프에 대해서는 사용하지 못한다. 모든 간선(u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬이 된다. 나는 BFS를 사용하는 방식으로 풀이했다...
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 1. Logic - 전형적인 투포인터 문제이다. 양쪽 끝에서 중간까지 오는 포인터 두개를 선언한 뒤 각 포인터에 해당하는 컨테이너 값을 더한 값이 이전의 sum값보다 작으면 값을 갱신해준다. 현재 포인터에 해당하는 sum값이 0보다 크면 값을 줄여줘야하기 때문에 right 포인터를 하나 줄여주고 이외에는 값을 키워야하기 때문에 left 포인터를 하나 올려준다. 2. Code #include ..
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 1. Logic - 이 문제를 풀기 위한 가장 핵심은 공기가 치즈 외부에 있는 공기인지 내부에 있는 공기인지를 확인해야 한다. 문제의 조건에서 모눈종이의 가장자리는 항상 공기가 있다고 했다. 그렇기 때문에 가장자리부터 즉 (0,0)은 항상 공기이기 때문에 (0, 0)에서부터 BFS를 돌며 치즈를 녹일 수 있는 공기인지 아닌지를 파악해야한다. 이후 정보를 바탕으로 치즈와 맞닿아있는 공기..
https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 1. Logic 해당 문제의 조건을 보면 사무실의 범위가 최대 8 * 8로 아주 작은것을 알 수 있다. 그렇기 때문에 완전탐색으로 구현할 수 있다. 시간복잡도는 모든 사무실을 다 탐색할 경우 8 * 8, CCTV의 4방향을 다 탐색한다는 가정 하 최악의 경우 8 * 8 * 4 정도가 나올 것 같다. 먼저 각 cctv 타입 별 탐색할 수 있는 범위의 경우의 수는 1번 CCTV : 상, 하..
