https://www.acmicpc.net/problem/20442 20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net 'left_k_cnt[위치] = 해당 위치 기준 왼쪽에 있는 k의 개수', 'right_k_cnt[위치] = 해당 위치 기준 오른쪽에 있는 k의 개수'를 저장해 놓고, r의 위치들을 목록을 저장해 놓은 뒤 이 목록을 중간에서 만나는 투 포인터를 이용해서 (가운데 껴있는 r의 개수) + (왼쪽 또는 오른쪽에 있는 k의 개수 중 더 작은 k의 개수)의 값을 구해가며, 왼쪽의 k가 더 많을 때는 오른쪽의 포인터(right)를 줄..

https://www.acmicpc.net/problem/2539 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 이분 탐색을 통해 모든 잘못 칠해진 칸을 가리는 가장 작은 색종이의 크기를 구했는데, 이때 특정 크기의 색종이로 모든 잘못 칠해진 칸을 가릴 수 있는지 확인하는 방법은, 색종이를 도화지 밑변에 맞추어 붙인다는 것을 이용하여, 가장 작은 열 번호의 색종이부터 순서대로 가려서 모두 다 가릴 수 있는지 확인하는 방법으로 문제를 해결했다. 코드 #include #include #include using names..

https://www.acmicpc.net/problem/2585 2585번: 경비행기 경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간 www.acmicpc.net 이분 탐색을 이용해 특정 용량의 연료통일 때, k번 이하의 급유로 출발지에서 목적지까지 갈 수 있는지 확인하는 방법으로 k번 이하의 급유에서 출발지에서 목적지로 가는 연료통의 최소 용량을 구했다. 특정 용량으로 k번 이하로 급유해서 출발지에서 목적지까지 갈 수 있는지 확인하는 방법은, 출발지에서 너비 우선 탐색 같은 방식으로 목적지까지 탐색하는 과정을 거쳐 문제를 해결했다. 코드 #include #incl..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net cache[left][right] 에 "left ~ right 파일을 합칠 때 필요한 최소 비용"을 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다. 이때, 파일의 크기를 누적합으로 psum에 저장해 놓고, cache[left][right]의 값을 구할 때, left에서 right-1 값 중 하나를 mid로 확인해 나아가며, 'cache[left][right] = cache[left]..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 임의의 지점(아래 코드에서는 1번 정점)에서 가장 먼 지점인 a를 찾고, a에서 가장 먼 지점인 b를 찾아서 a와 b사이의 거리를 구하는 방법으로 트리의 지름을 구해서 문제를 해결했다. 코드 #include #include #include using namespace std; int n; vector adj[100005]; int visited[100005]; int dist[10..

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 1이 있는 위치를 인접한 칸으로 연결한 것을 하나의 영역으로 다뤄서, 1의 위치마다 어떤 영역에 속하고, 영역마다 영역의 크기를 저장해 놓고, 모든 위치를 확인하며, 해당 위치가 0이면 해당 위치를 1로 만들었을 때 인접한 영역 부분을 고려하여 만들어지는 영역의 크기를 구해서 확인하고, 해당 위치가 1이면 해당 영역의 크기를 확인하는 방법으로 최대 크기를 구해서 문제를 해결했다. 코드 ..