전체 글
지식에 정성을 들이는 습관을 갖자 대충 절대 금지
[BackTracking] 백준 18428번 감시 피하기 - JAVA
오늘은 23.11.23에 풀었던 알고리즘 스터디의 첫 번째 문제! 지연이가 요청했던 그 문제!!! 감시피하기 문제를 다시 보고 리뷰하는 시간을 갖도록 하겠다. 다시 보니까 꽤 난이도 있는 문제여~ 1. 출처 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net N*N 복도에 학생과 선생님의 위치가 주어짐 3개의 장애물을 설치해서 학생들을 선생님 감시 하에서 피하게 해야함 선생님은 자신의 4방을 거리 제한없이 감시할 수 있음 단, 선생님은 장..
[DP] 백준 1495번 기타리스트 - JAVA
수학적인 공식이 아닌 논리 공식을 이끄는 dp는 어렵다 ㅎㅎ 오늘의 오답노트는 바로 기타리스트~ 1. 출처 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 공연의 새로운 파트가 시작되기 전 볼륨을 바꿀 수 있음 파트의 수, 가장 먼저 실행되는 볼륨, 올릴 수 있는 최대 볼륨 3가지가 주어짐 볼륨은 0에서 최대 볼륨 사이로 실행시킬 수 있음 이 때, 가장 마지막 파트에서 틀 수 있는 가장 큰 볼륨을 구하는 문..
[DP+Math] 백준 17626번 Four Squares - JAVA
내 수준은 딱 골드 5인 것 같아서 요즘은 알고리즘 스터디 문제 중 실버 ~ 골드5 문제를 열심히 풀고 있다. 오늘은 맞춘 문제이지만, 내가 취약해하는 요소 DP + Math 2개가 모두 섞여있어서 복습을 해보고자 한다. 1. 출처 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 모든 자연수는 최대 4개의 제곱수의 합로 나타낼 수 있음 26 = 5^2 + 1^2 혹은 4^2 + 3^2 + 1^2 이런식 최소 ..
[DP] 백준 1309번 동물원 - JAVA
오랜만에 시간초로 낚인 문제가 있었으니... 바로 동물원... 2초라는 시간대가 여유롭다고 착각하고, PowerSet으로 돌렸다가 N=100000이 시간초과로 안돌아가는 상황을 목격했다. 충격~ 15초 내로 N=21까지만 돌아간다 ㅋㅋ 그래서 아... 이거 DP였구나를 깨달아버렸다. 1. 출처 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net N이 주어진다. N은 행이다. 열은 2로 고정이다 (N,2) 행렬에서 사자를 우리에 넣을 수 있는 경우의 수를 구하는 것 한 사자를 넣을 때 근접한 가로, 세로에 사자가 들어있으면 그 위치에 사자를 넣을 수 없음 (4방 탐색) 2. 설계 그래서 DP면 공식이 뭐지?... 이중그래프를 그려놓고, 한칸 한칸 ..
[DFS+DP] 백준 1520번 내리막 길 - JAVA
DFS와 DP의 조합은 어렵다 ㅠ 다시 공부해야짓! 1. 출처 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 지도 상에 건물의 높이가 주어짐 높이가 현재 건물보다 낮은 곳만 이동할 수 있음 내리막길로만 가고 싶음 (우, 하, 좌) 갈 수 있는 경로는 몇 개인지 계산하는 문제 2. 설계 처음엔 BFS로 좌, 하, 우 방향 탐색해서 갈 수 있는 경로가 몇 개인지 계산하고자 하였다. 그런데 16%만에 메모리 초과가 났다. 가로x세로 = 500x500이기..
useState lazy init 기법
state가 초기화될 때 함수가 단 1회만 실행되어 값이 할당되는 방식을 lazy init이라고 한다. - Bad const getNumbers = () => { const candidates = [1,2,3,4,5,6,7,8,9]; const array = []; for(let i=0; i { const [answer, setAnswer] = useState(getNumbers()); } 4개의 숫자를 랜덤으로 돌려 answer에 할당하고자 할 때 getNumber()을 넣어주게 되면, 컴포넌트가 재렌더링될 때마다 다시 getNumbers()함수가 실행된다. 이 함수가 정말 무거운 함수였다면 시스템 전체의 부담이 되었을 것이다. (비효율적, 불필요한 반복) - good const getNumbers =..
웹팩 데브 서버와 핫 리로딩
1. 웹팩 데브 서버와 핫 리로딩 설정 왜 해주는 건데? react로 개발을 하다가 수정을 할 때 변경 사항을 확인하기 위해 계속 빌드를 반복해야한다. 개발자한테 이 반복작업은 매우 귀찮으며, 시간이 걸리는 작업이다. 하지만, 빌드 작업과 테스트를 위한 클릭 및 입력 작업이 생략될 수 있다면?획기적인 시간 단축을 기대할 수 있을 것이다. 우린 이것을 웹팩 데브 서버를 설치하고, 핫 리로딩 설정을 해줌으로써 빌드 과정을 자동화한다. 2. 핫 리로딩하는 2개의 패키지 npm i react-refresh @pmmmwh/react-refresh-webpack-plugin -D 그런데 이 핫 리로딩 패키지 없어도 리액트에서 그냥 리로딩되는데? 구지해줘야하나? 그것은 그냥 리로딩이다. 핫리로딩이랑은 다르다. 리로딩..