멘지의 기록장

난이도 🥈 1 링크 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 풀이과정 해당 문제도 그리디 알고리즘을 사용해서 푸는 문제였다. 그리디 알고리즘에 대한 설명은 아래 글에 작성해두었으니 참고하면 좋을 것 같다! https://amepistheo.tistory.com/7 [백준] 1449 : 수리공 항승 (JAVA) 난이도 🥈 3 링크 https://www.acmicpc.net/problem/1449 1449번: 수리..

난이도 🥈 3 링크 https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 풀이과정 해당 문제는 그리디 알고리즘을 사용해서 푸는 문제이다. 그리디 알고리즘 (Greedy Algorithm)이란 "매 선택에서 현재 당장 최적인 답"을 선택하여 전체 적합한 결과를 도출하는 알고리즘이다. 즉, 백트래킹을 통해 추가 점검을 하지 않고 현재 조건에서 선택을 했다면 더 이상 다른 선택 가능 경우는 검증하지 않는다는 것이다! 하지만! 그리디 ..

난이도 🥈 2 링크 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 문제 풀이과정 해당 문제도 이분탐색을 사용해서 푸는 문제이다. 이분탐색에 대해서는 아래 글에서 작성해두었으니 참고하면 좋을거 같다! (풀이 설명도 아래의 글을 참고하면 될 것 같다.) https://amepistheo.tistory.com/4 [백준] 2110 : 공유기 설치 (JAVA) 난이도 🥇 4 링크 https://www.acmicpc.net/problem/2110..

난이도 🥇 4 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 풀이과정 해당 문제는 이분탐색을 사용하는 문제이다. 이분탐색이란 이진탐색, Binary Search라고도 불리며, 순차적 탐색보다 빠른 탐색을 위해 나온 탐색 방법이다. 이분탐색은 범위를 새로 정할 때마다 탐색 범위가 반씩 감소하기 때문에 O(logn)가 걸리지만 순차탐색은 최악의 경우 배열의 끝까지 탐색해야하기 때문에 ..

난이도 🥇 2 링크 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 풀이과정 해당 문제는 아래 문제와 동일하지만 DP를 이용하면 시간초과가 나는 문제이다. https://amepistheo.tistory.com/2#comment19153321 [백준] 11053 : 가장 긴 증가하는 부분 수열 (JAVA) 난이도 실버 2 링크 https://www.acmicpc.net/problem/11053 11053번: ..

난이도 🥈 2 링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이과정 해당 문제는 DP 중에서 최장 증가 부분 수열 (LIS)을 사용하는 문제이다. LIS란 Longest Increasing Subsequence의 약자로, 말 그대로 가장 긴 증가하는 부분 수열을 의미한다. 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 알고리즘으로, 풀이..