yevdev◡̈

오늘의 포스팅은, 동적계획 알고리즘을 이용한 연속된 행렬곱셈이다. 문제 n개의 연속된 행렬곱셈 M = M1M2M3...Mn에서 스칼라 곱셈 횟수가 최소가 되는 곱셈 순서를 찾는 알고리즘 💡행렬곱셈의 원칙 행렬곱셈 C = AB 의 기본적인 요건은 A의 열의 개수와 B의 행의 개수가 같음 A(p x r) x B(r x q) = C(p x q) 스칼라 곱셈은 모두 ( p x r x q ) 번 무작위 기법 모든 행렬 곱셈 순서를 구하여, 각각의 스칼라 곱셈 횟수를 계산하여 비교 Xn = (n개의 행렬을 곱하는 가능한 모든 곱셈 순서의 수) 라면, Xn은 다음의 세경우의 수를 합한 것 M1을 가장 나중에 곱하는 경우의 수 = M1(M2M3...Mn)의 순서로 곱 = M2M3...Mn을 곱하는 경우의 수 = X(n..

💡작업스케줄링 수행해야할 다수의 Job을 주어진 목적에따라 어떻게 수행할지를 결정하는 문제 주어진 목적에따라 작업스케줄링을 다양하게 정의할 수 있다. 이러한 문제들은 대부분 NP-hard문제이나, 일부 목적에 대해서 또는 문제를 단순화 시킬 경우 polynomial time에 해결할 수 있다. 💡작업스케줄링 문제 작업의 수행시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제이다. n개의 각작업은 시작시간과 종료시간이 있다. 주어진 문제요소 작업의 수 각 작업의 시작과 종료시간 : 이는 정해져 있으므로 작업의 길이도 주어진 것이 된다. 시각시간, 종료시간, 작업의 길이에 대해 그리디 알고리즘을 생각해 볼 수 있는데 빠른 시작시간 작업 우선 배정 빠른 종료시간 작업 우선 배정 짧은 작업..

💡집합커버문제 (Set Covering Problem) n개의 원소를 가진 집합 U U의 부분집합들을 원소로하는 집합 F F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가? 여기서, F에서 선택하는 집합들의 수를 최소화하는 문제이다. ❓최적해를 어떻게 찾아야할까? 가장 단순한 방법 : F에 있는 집합들의 모든 조합을 1개씩 합집합하여 U가 되는지 확인하고, U가 되는 조합의 집합 수가 최소인 것을 찾는 것 Brute Force Algorithm : n개의 원소가 있으면 (2^n -1)개를 다 검사 필요 n이 커지면 최적해를 찾는 것은 실질적으로 불가능 실제로 집합커버문제는 NP-hard 문제로 polynomial time optimal algorithm을 설계하기 매우 어렵..

💡최단 경로 찾기? 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제이다. 💡어떻게 구할까? 무작위 방법 : 모든 도시들이 다 연결되어 있다면 출발점에서 가능한 경로의 수는 θ(n!) 다익스트라 최단경로 알고리즘 그리디 알고리즘 (결과적으로) 출발점에서 가까운 도시부터 차례대로 최단 경로를 탐색 한번 결정된 최단 경로는 절대 바뀌지 않으며 출발점에서 더 먼 도시의 최단 경로를 구할 때 이용 ➰최단 경로 찾기 알고리즘의 종류 단일 시작점 최단 경로 알고리즘 : 출발지점을 하나 선택하면 나머지 다른 모든 지점까지의 최단 경로를 알려주는 유형 모든 쌍 최단 경로 알고리즘 : 모든 지점들간의 최단 경로를 알려주는 유형 최단 경로 찾기 알고리즘은 프림의 최소 신장 트리 알고..

💡신장트리? 주어진 연결 그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리 정점의 수가 n 개, 신장트리의 간선의 수는 n-1 개 💡최소 신장 트리? 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분(간선)들의 가중치 합이 최소인 트리 💡어떻게 최소 신장 트리를 찾을까? 무작위 기법 가능한 신장 트리를 모두 구한 다음, 최소 비용의 신장 트리를 선택 모든 정점 간에 간선이 있는 완전 그래프의 경우 신장 트리의 수는 n^(n-2) 그리디 알고리즘 크리스컬과 프림 알고리즘 있음 알고리즘 입력은 1개의 연결요소로 된 가중치 그래프이다. 💡크리스컬 알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때에만 '욕심내어' 그 선분을 추가 시킨다. 각 단계에서 가중치가 최소인 간..

💡React.memo? 컴포넌트의 props가 바뀌지 않았다면, 리렌더링을 방지하여 컴포넌트의 리렌더링 성능을 최적화 시켜주는 함수! 이 함수를 사용하면, 컴포넌트에서 리렌더링이 필요한 상황에서만 리렌더링을 하도록 설정해줄 수 있다. 사용법은 그냥 감싸주면 됨! CreateUser.js 에 적용 // 컴포넌트 리렌더링 방지를 위한 React.memo export default React.memo(CreateUser); 왕 쉬움! UserList.js 에 적용 import React, {useEffect} from 'react' // user리스트들이 보여지는 부분 const User = React.memo(function User({user, onRemove, onToggle}) { return( onT..

💡useCallback useCallback은 useMemo와 비슷한 Hook useMemo는 특정 결과값을 재사용 useCallback은 특정 함수를 새로 만들지 않고 재사용하고 싶을 때 사용 이전에 App.js 에서 구현했던 onCreate, onRemove, onToggle 함수를 확인해보자 const onCreate = () => { const user = { id: nextId.current, username, email }; setUsers(users.concat(user)); setInputs({ username: '', email: '' }); nextId.current += 1; }; const onRemove = id => { // user.id 가 파라미터로 일치하지 않는 원소만 추출..

이번 포스팅은 useEffect라는 Hook을 사용하여 컴포넌트가 마운트 됐을 때 (처음 나타났을 때), 언마운트 됐을 때(사라질때), 그리고 업데이트 될때 (특정 props가 바뀔 때) 특정 작업을 처리하는 방법에 대한 것이다! 1️⃣ 마운트 / 언마운트 import React, {useEffect} from 'react' // useEffect 불러오기 function User({user, onRemove, onToggle}) { // useEffect 사용! useEffect(() => { console.log('컴포넌트가 화면에 나타남'); return() => { console.log('컴포넌트가 화면에서 사라짐'); } },[]); return( onToggle(user.id)} >{user...

#12 배열에 항목 추가 , #13 배열의 항목 삭제에 이어서 하는 배열 항목 수정하기이다! User 컴포넌트에 계정명을 클릭했을 때 색상이 초록색으로 바뀌고, 다시 누르면 검정색으로 바뀌는 기능을 구현해보자! 1️⃣ App 컴포넌트의 users 배열 안의 객체 안에 active라는 속성 추가 App.js import React,{useRef, useState} from 'react'; import UserList from './UserList'; import CreateUser from './CreateUser'; function App() { const [inputs, setInputs] = useState({ username: '', email: '' }) const {username, email}..

저번 포스팅에서 배열에 항목 추가하기에 이어, 항목을 제거하는 기능을 구현해보겠다! 1️⃣ 삭제 버튼 렌더링 UserList.js import React from 'react' function User({user, onRemove}) { return( {user.username} {user.email} onRemove(user.id)}>삭제 ) } function UserList({users, onRemove}) { return ( {users.map(user => ( ))} ) } export default UserList () => onRemove(user.id) : User컴포넌트의 삭제 버튼이 클릭 될 때, user.id값을 앞으로 props로 받아올 onRemove 함수의 파라미터로 넣어서 호출..