이 험난한 세상에서어어~

문제 설명 상근이는 나무를 자르려고 한다. 이때 상근이는 환경에 관심이 많아 필요한 만큼의 나무만 들고가려고 한다. 이때 가질 수 있는 톱의 최대 높이를 구하는 문제이다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 간단히 설명하자면 상근이가 나무를 자르는데, 잘린 나무의 값과 주어진 M의 값의 오차가(무조건 양수) 최소가 되게 하는 높이를 구하는 문제이다. 문제 풀이 이진탐색 자를 높이를 이진탐색으로..

문제 설명 집 N개가 같은 좌표를 가지는 일이 없게 수직선 위에 서 있다. 이때 도현이는 와이파이를 각 집에 설치해서 최대한 많은 곳에서 인터넷을 사용하려고 한다. 와이파이는 한 집에 하나만 설치할 수 있고 가장 인접한 두 공유기 사이의 거리를 최대로 하려고 한다. 해당 값을 구하는 문제이다. 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 문제 풀이 첫 번째 접근 일단 부르트포스(완전 탐색)..

문제 설명 Demi는 야근을 하면 야근 피로도가 쌓인다. 야근 피로도는 남은 작업시간 제곱의 합이며 1시간 야근을 하면 작업량을 1만큼 처리할 수 있다. 이때 야근 피로도는 남은 야근 작업량의 제곱의 합이다. n을 모두 사용할 때 최소의 야근 작업량을 구하시오. https://school.programmers.co.kr/learn/courses/30/lessons/12927?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 첫 번째 접근 첫 번째 예를 한 번 보자. n이 4이고 작업량이 [4, 3, 3]일 때 야근을 하고 ..

문제 설명 두 수열이 주어졌을 때, LCS의 길이와 LCS를 구하는 문제이다. https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 풀이 첫 번째 접근 https://jiwonna52.tistory.com/71 LCS(Longest Common Subsequence, 최장 공통 부분 수열) java LCS란? 부분 수열 LCS는 최장 공통 부분 수열로 두 개의 수열이 주어졌을 때, 공통 수열 중 ..

문제 설명 길이가 N인 계단 수열의 수를 구하는 문제인데, 이때 0부터 9까지의 숫자가 모두 한 번 이상 등장해야 한다. 이때 0으로 시작하는 수는 계단수가 아니다. https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 첫 번째 접근 DP 문제이기 때문에 처음에는 직접 손으로 풀어 써봤다. 이때 계단수의 규칙을 발견했는데, 0혹은 9의 옆 자리에는 1과 8밖에 오지 못한다는 점이다. 일단 0의 경우에는 0과 x를 빼서 절댓값이 1이 되는 경우가 1혹은 -1인데, -1은 오지 못하니 1밖에 없다. 9 또한 10과 8이 있지만, 10은 고려 사항이 아니니 8밖에 오..

LCS란? 부분 수열 LCS는 최장 공통 부분 수열로 두 개의 수열이 주어졌을 때, 공통 수열 중 제일 긴 것을 의미한다. 예를 들어서 abcf와 aebwcd가 있다고 생각해 보자. 그렇다면 여기서 나오는 LCS는 abc이다. abcf aebwcd 위의 굵게 표시된 문자들을 보면 알 수 있을 텐데, 공통 부분 수열은 굳이 문자들의 한 번에 이어질 필요가 없다. 공통된 문자가 얼마나 길게 차례대로 나오느냐를 따지는 문제이기 때문이다. 최장 공통 부분 수열 이제 최장 공통 부분 수열을 구하는 방법을 알아보자. 그러기 전에 아래의 유튜브 비디오를 보고 오는 것을 추천한다. 현재 글도 아래 동영상을 기반으로 작성한 것이다. https://www.youtube.com/watch?v=sSno9rV8Rhg LCS의 ..