yevdev◡̈

동적 계획 알고리즘에 대해 공부하기 전에,, 이전에 포스팅했던 분할정복 방법! 다시 살펴보기 💡분할정복 방법? 하향식 top-down 접근법 상위 레벨의 복잡한 문제를 재귀적으로 작은 문제들로 나누고, 이들의 해를 결합해서 문제를 해결하는 방법 분할된 부분 문제들은 서로 독립적 퀵정렬, 합병 정렬, 이진 탐색 ➰피보나치 수열을 분할 정복으로? 같은 계산이 반복됨 -> 비효율적! 💡동적 계획 알고리즘? 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘 작은 문제에 대한 결과를 테이블에 저장해 놓고, 이를 이용하여 입력의 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 방법 최댓값/최솟값을 구하는 최적화 문제에 적용 부분 문제들 사이에 의존적 관계가 존재한다. 이러한 관계는 문제 또는 입력에 따라 다..

💡작업스케줄링 수행해야할 다수의 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개의 물건 및 각 물건의 무게, 가치, 배낭의 용량 C 출력 : 배낭에 담은 물건 리스트 L, 배낭에 담은 물건의 가치 합 v 1. 각 물건에 대해 단위 무게당 가치를 계산 2. 물건들을..

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

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

커스텀 Hook은 언제 필요? 컴포넌트를 만들다보면, 반복되는 로직이 자주 발생 input을 관리하는 코드는 관리 할 떄마다 꽤나 비슷한 코드가 반복 이번 포스팅 내용은, 위의 상황에 커스텀 Hooks를 만들어서 반복되는 로직을 쉽게 재사용하는 방법을 알아보는 것이다. 커스텀 Hooks 만드는 방법 src 디렉터리에 hooks라는 디렉터리를 만들고, 그안에 useInputs.js 파일을 만든다 커스텀 Hook을 만들대는 보통 이렇게 use 라는 키워드로 시작하는 파일을 만들고 그안에 함수를 작성한다. 파일안에 useState, useEffect, useReducer, useCallback등 Hooks를 사용하여 원하는 기능을 구현해주고 컴포넌트에서 사용하고 싶은 값들을 반환해주면 된다. useInputs..

Study #19 까지의 상태관리는 어떻게 해왔을까? 주요 상태 업데이트 로직을 App 컴포넌트 내부에서 이루어왔다 상태를 업데이트 할 때, useState를 사용해서 새로운 상태를 설정했다. 💡useReduder? useState를 사용하여 상태를 관리하는 것이 아닌 또다른 상태관리 방법 이 Hook 함수를 사용하면 컴포넌트 상태 업데이트 로직을 컴포넌트에서 분리시킬 수 있다. 상태 업데이트 로직을 컴포넌트 바깥에 작성할 수도 있다. 심지어 다른 파일에 상테 업데이트 로직을 작성한 후, 사용할 수 있다. 💡reducer? 현재 상태와 액션 객체를 파라미터로 받아와서 새로운 상태를 반환해주는 함수 function reduer(state, action) { // 새로운 상태를 만드는 로직 // const ..

💡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 가 파라미터로 일치하지 않는 원소만 추출..