AtraFelis's Develop Diary

https://www.acmicpc.net/problem/27527keyword : 슬라이딩 윈도우문제현대오토에버는 현대자동차그룹의 모빌리티 소프트웨어 전문 기업으로서, In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라를 안정적, 효율적, 혁신적으로 지원하는 'Mobility SW Provider' 역할을 수행하고 있다. 당신은 현대오토에버의 다양한 소프트웨어 기술을 선보이기 위한 행사를 준비하고 있으며, 행사는 현대오토에버 본사가 위치한 서울 삼성역 인근에서 개최될 예정이다.이 행사를 홍보하기 위한 배너를 걸어야 하는데, 마침 당신은 현대오토에버의 MMS 기술을 사용하여 제작한 정밀 지도를 갖고 있다. MMS(Mobile Mapping System)란 차량 운전 지원용 지도 생성을 위해 고성..

신청 계기방학 시즌이 시작되고 뭐라도 해야겠다는 마음에 거의 반년만에 백준에 접속했었다. 그러다가 백준 메인 페이지의 광고 배너에 99클럽 코테 스터디의 광고가 올라와 있는 것을 발견했다. 평소라면 무시했을텐데 그때는 왜 그랬을까? 그냥 아무 생각 없이 클릭해서 살펴보았다.역시 가장 먼저 눈에 들어온 것은 일정과 참가비였다. 한 달에 3만원. 가격이 엄청 비싸지는 않아 보였다. 다음에 본 것은 진행 방식이었는데, 나라는 놈은 원래 반쯤은 강제성이 있어야 열심히 하기 때문에 참여해보는 것도 괜찮겠다는 생각을 했더랬다. (자세한 건 직접 읽어 보시길. https://hanghae99.spartacodingclub.kr/99club-codingtest)그리고 이때는 몰랐는데, 스터디 시작 전 진행했던 오리엔테..

99클럽 코테스터디 25일차 TILKeyWord : DP, Map문제무한 수열 A는 다음과 같다.$A_0 = 1$$A_i = A_{⌊i/P⌋} + A_{⌊i/Q⌋} (i ≥ 1)$N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.입력첫째 줄에 3개의 정수 N, P, Q가 주어진다.출력첫째 줄에 AN을 출력한다.제한$0 ≤ N ≤ 10^{12}$$2 ≤ P, Q ≤ 10^9$  풀이매우 간단한 DP 문제이다. 처음부터 문제에 수열의 점화식도 주어졌으므로, 그대로 메모제이션을 하면서 코드를 구현하면 될 듯하다. (bottom-up 방식이 아닌, top-down의 재귀 방식으로 구현하면 쉽다.)하지만 이 정도만 고려하고 곧장 코드를 구현한다면 반드시 실패할 것인데, 아래의 조건 때문이다.$0 ≤..

99클럽 코테스터디 24일차 TILKeyWord : DP문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.입력첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.출력첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.  풀이N과 K의 크기를 1부터 증가시키며 메모제이션 하여 해결할 수 있다.dp[k+1][n+1]라는 배열을 선언한 후, dp[i][j]에 각 경우의 수를 저장해가는 식으로 진행하자.문제에서 주어진 예제입력 6 4를 기준으로 dp 배열을 시각적으로 나타내보았다.K\N01..

99클럽 코테스터디 23일차 TILKeyWord : DP문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.풀이DP 문제에 익숙하지 않다면 아이디어를 떠올리는 것이 힘들었을 법한 문제였다.시간제한이 0.1초이니 완전탐색으로는 절대 불가능해 보인다. 또 그리디로 해결하는 것도 잠깐 고민해보니 불가능할 것 같다. 그래서 DP로 ..

99클럽 코테스터디 22일차 TILKeyWord : 동적프로그래밍(DP)문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 $A_i$가 주어진다. (1 ≤ $A_i$ ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.  풀이 메모제이션 기법으로 해결할 수 있는 문제이다.일단, 수열 {1, 2}와 수열 {4, 3, 6, 10, 32, 13, 10,..