링크 https://www.acmicpc.net/problem/18353 난이도(solved.ac 참고) 실버2 풀이 앞서 포스팅한 LIS 문제를 이해했으면 어렵지 않게 풀 수 있는 문제다. 다만 차이가 있다면, a[i]의 값이 더 작은 경우에 dp의 값을 배정해 줬다는 것이다. 그 이유는 여기에서는 증가하는 부분수열이아니라 감소하는 부분수열이기 때문이다. 여기에서 우리가 구해야하는 것은, 최대 부분수열의 길이가 아니라 전체에서 최대 부분수열의 길이만큼 빼준 값이기 때문에 대상이 되는 리스트 a의 길이에서 감소하는 최대 부분수열의 길이만큼을 빼준 값이 정답이 된다.
링크 https://www.acmicpc.net/problem/11053 난이도(solved.ac 참고) 실버2 풀이 응용이 많이 되는 유형이다. 이 문제를 먼저 접한 이유는 원래 오늘 풀기로 했던 병사 배치하기를 풀 때 필요한 부분이라고 생각되었기 때문이다. n까지의 범위를 가지는 i와 i까지의 범위를 가지는 j를 돌면서, 증가하는 부분 수열의 길이가 증가하려면 a[i]의 값이 a[j]보다 커야한다. 이 경우 dp의 값은 더 작은 인덱스인 j의 dp 인덱스에 1을 더해준 것과, 기존의 dp[i]의 값중에 더 큰 값이 들어가야 한다. 전자에서 +1이 들어가는 이유는 증가하는 부분수열의 길이가 1 증가했기 때문이다.
오늘은 CRA + TS에서 스타일링과 마크다운 에디터의 값을 가져올 수 있도록 useState 처리를 해줬다. import React, { useState } from "react"; import SimpleMdeReact from "react-simplemde-editor"; export const ControlledUsage = () => { const [value, setValue] = useState("Initial value"); const onChange = (value: string) => { setValue(value); }; return ; }; 마크다운 에디터 React-simplemde-editor에서 직접 값을 다룰 수 있도록 Controlled Usage 컴포넌트를 받아와서 적용시..
링크 https://www.acmicpc.net/problem/14501 난이도(solved.ac 참고) 실버4 풀이 동적계획법은 알고리즘 수업때 풀어본 게 마지막이니까, 대충 2-3달만에 풀어봤는데 역시 쉽지 않다. 실버 4였지만.. 생각하는 힘이 좀 부족하다고 생각한다. 동적계획법 문제는 많이 풀어봐야겠다. dp를 100이나 둔 이유는 16(n의 최대값 + 1)으로 넣어서 했더니 자꾸 인덱스 오류가 나서 짜증나서 그냥 100으로 해버렸다. 물론 메모리 제한이 좀 있었다면 당연히 못 맞았다. dp 배열에 대해 i일 뒤에 받게 될 금액, 그러니까 dp[i] + p_list[i]가 현재 금액 (dp[i+t_list[i]])보다 크다면 큰 값을 반영해주는 방식으로 진행했다. 그리고, 현재 받게 될 금액이 다..
배운 것, 공부한 것, 메모할 것 1. React + TS - Next.js에 관련용어 완성본 반영하기 - MDE 데이터 가져오고 보내는 법 공부하기 2. 동아리 - 다크모드, 투두리스트 발표하기 3. 알고리즘 - 백준: 퇴사(14501번) - 백준: 병사 배치하기(18353번) 하고싶은 말 카카오톡 잔여백신 잡아보려다가 한시간동안 5개 놓치고 실패했다..
풀이 DP문제 중 계단 오르기와 더불어 기초에 해당하는 문제인데, 점화식을 찾지 못하면 좀 어려울 수도 있는 문제이다. DP의 핵심은 우선 부분해를 구한 뒤 그것을 일반화하는 것이라고 생각한다. 그래서, 우선 쉽게 구할 수 있는 2*1과 2*2 각각을 구한 뒤에 3부터 일반화하여 구했다. 한번 생각해보자. 2 * 3의 바닥을 채우는 방법은 2 * 2의 바닥을 채우는 방법(2*1 2개, 1*2 2개, 2*2 1개 해서 총 3가지)에서 옆으로 1*2의 칸이 더 추가가 된 것이다. 이는 즉, (2 * 2의 바닥 채우기 + 1 * 2의 바닥 채우기) 순서와 (1 * 2의 바닥 채우기 + 2 * 2의 바닥 채우기) 순서를 합한 것이 총 2 * 3의 바닥을 채우는 방법이 되는 것이다. 이것을 일반화하면 i-2번째 ..
CRA + JS로 코딩을 마치고 CRA + TS로 바꾸는 과정에서 자꾸 저 에러가 떴다. 한두 군데도 아니고 여러 군데에서 떠서 구글링을 좀 해봤고, 금방 결과를 찾을 수 있었다. 바로 아래 사진에서 Select TypeScript Version을 선택한 뒤 Use Workspace Version을 클릭하는 것.. 나도 그렇게 해결했다면 이런 포스팅을 작성하진 않았을 것이다. 왜냐면 난 Use Workspace Version이 없었기 때문이다. 그래서 vscode typescript use workspace version not found 이런 방식으로 찾아봤으나 해결책을 구하지는 못했고, 그래서 어떻게 하지 하다가 tsconfig.json 파일을 수정함으로써 해결할 수 있었다. CRA를 이용해서 타입스..
링크 https://www.acmicpc.net/problem/1463 난이도(solved.ac 참고) 실버3 풀이 재귀형태의 다이나믹 프로그래밍으로 해결하였는데, 이렇게 푼 사람들이 많은 걸 보면 그냥 이렇게 풀라고 낸 문제 같다. 여기에서 dp배열의 값들은 1로 만드는 데 걸리는 횟수들이다. 여기에서 우선 dp[i] = dp[i-1] + 1은 그냥 1을 빼줬을 때에 해당한다. 그냥 빼기만 하면 이전 횟수에 비해 1회가 추가되는 것이 끝이기 때문. 2와 3으로 나눠질 경우, 횟수가 1회 추가되었으므로 dp[i//3]이나 dp[i//2]의 값에 +1을 해줬다. 그리고 그 값을 기존에 있던 dp[i-1]+1의 값과 비교를 해주었다.
일단 JS + CRA로 수요일 모각코 포스팅에서 구현해야했던 기능 외에 발견되었던 문제는 전부 해결했다. 수요일에 만들었던 코드의 문제는, 아래 세 가지였다. 1. 콤마나 스페이스바를 눌렀을 때 텍스트박스도 비어있게 되어야 정상인데 콤마 및 스페이스바의 값이 텍스트박스에 삽입이 된 채로 비어있게 되었던 문제 2. 영어를 입력했을 때는 콤마(+스페이스바)가 잘 동작하지만 한국어를 입력하고 트리거를 시키려고 하면 꼭 두 번 눌러야만(스페이스바든 콤마든) 트리거가 되었던 문제 3. 배열로 합친 termsArray를 콘솔에 찍으면 방금 입력하고 이벤트를 실행했을 때 그 값도 잘 들어가서 나오는데, setRelatedTerms를 했음에도 불구하고 relatedTerms를 콘솔에 찍으면 그 값이 바로 들어가지 않았..
링크 https://www.acmicpc.net/problem/1300 난이도(solved.ac 참고) 골드3 풀이 처음 봤을 때 골드 3이라는 난이도를 보고서 당연히 쉽게 풀 수 있는 방법대로 풀면 안된다고 생각했지만 그래도 한번 해봤고 역시 메모리 초과가 떴다. 쉽게 풀 수 있는 방법이란 2중 반복문을 돌리면서 [i][j]에 i * j를 넣어주는 것. 그렇게 하면 절대 안된다. 애초에 범위가 10억개였기 때문에 이 문제는 배열을 직접 만들지 않고 풀어야 한다. n * n 배열에서 k보다 작은 수들의 갯수를 구하자. 갯수를 전부 더해준 값을 k와 비교해서 이분 탐색을 진행하면 된다. 5 * 5 배열에서 10보다 작은 수의 갯수를 구하면.. 1 * 1 ~ 1 * 5 (10 // 1과 n중 작은 값) 2 ..