12. 다이나믹 프로그래밍-2(행렬 곱셈 문제)
행렬 곱셈 문제 n개의 행렬 곱셈을 최소 비용으로 푸는 문제 만약 무지성으로 pXq , qXr 인 두 행렬을 3개 for루프로 풀면, O(pqr)번 연산이 필요하다.이때 여러개의 행렬이 주어졌을 때는, 행렬을 어느 순서로 곱하느냐에 따라 기본 연산 횟수가 달라진다.a = 1x2, b=2x3, c=3x4 일때, (ab)c와 a(b
Archive: 2021
11. 다이나믹 프로그래밍-1
다이나믹 프로그래밍문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법. divde and conquer와 차이점은? 큰 문제의 답이 작은 문제의 답들의 식으로 표현되지만,그 답을 얻을 때 재귀적으로 얻는게 아니라 미리 계산하여 기록해 놓은 값을 재귀 식에 따라 계산! 즉 원래 문제의 답을 작은 문제들의 재귀 식으로 표현하는 것이 핵심!!!!점화
10. Merge 정렬 알고리즘
Merge 정렬 알고리즘퀵 소트가 피벗을 어떻게 선택하냐에 따라 속도가 달라지는 단점을 상쇄하는 알고리즘 배열은 반으로 나눠 재귀적으로 정렬하고 정렬된 두 배열을 원소 하나씩 비교해서 병합하는 방식.주어진 배열만큼 새로운 배열을 사용해야 하기 때문에 not in-place 알고리즘이다. 먼저 중간 인덱스를 찾는다. 중간 인덱스를 기준으로 나눠서 두 배
7. 프로세스 상태와 스케줄러 알고리즘의 관계
멀티 프로그래밍과 waitwait : 프로세스가 실행 중임에도 불구하고 cpu를 사용하지 않고 기다리는 시간멀티 프로그래밍은 wait 때문에 발생하는 비효율을 줄이는 스케쥴링 알고리즘!그렇다면 이렇게 효율적으로 하기 위해서는 어떻게 해야할까?어떤 시점에 어떤 프로세스를 실행시켜야 될지 판단해야 하는데.. 이때 중요한게 프로세스 상태다!프로세스 상태 run
9. Quick 정렬 알고리즘
퀵 정렬 알고리즘이론적으로는 빠르지 않지만(O(n^2)), 실제로는 가장 빠른 정렬 알고리즘quick selection과 비슷한 원리임. not in-place quick sort algorithm 어떤 list A를 퀵 정렬 하려면… 피벗을 A[0]으로 잡고, S,M,L 세가지 배열을 선언함 A에 있는 모든 수들이 피벗보다 크면 L, 작으면 S, 같으
8. 기본 정렬 알고리즘
파이썬에서 제공하는 정렬 123A = [3,1,2,-5]A.sort() #[-5,1,2,3]A.sort(reverse = True) #[3,2,1,-5] 정렬 알고리즘의 두 가지 특성 stable vs unstable만약 [2,5,2,7]을 오름차 정렬했을 때 ,[2,2,5,7]로 정렬이 될 텐데, 이 두 개의 2가 입력 순으로 정렬되면 stable하
10. 최단경로 알고리즘(벨만포트, 다익스트라)
최단 경로 알고리즘아주 중요한 그래프 문제.엣지에 가중치가 부여된 상황에서 특정 노드에서 다른 노드로 가는 최적의 경로를 찾는 문제. 특징 노드 s에서 v까지 최단 경로 중 엣지(u, v)가 포함되면, 이 경로에서 s부터 u까지 부분도 역시 최단 경로다.M(v)를 s에서 v까지 최단 경로라고 길이라고 하면,M(V) = M(u)+min(u,v)
9. 그래프
그래프G = (V, E)V = vertex set, E = edge set동그라미가 버택스(혹은 노드), 버택스를 잇는 링크를 엣지라 한다. degree(분지수) 어떤 노드의 이웃한 노드 갯수.어떤 그래프의 분지수는 그 그래프의 최대 분지수를 말한다. 인접하다는 의미는 두 노드가 링크로 서로 연결 되어있는 상태를 말한다. 경로는
8. 균형이진탐색트리
균형이진탐색트로(BST)?이진트리는 search, insert, delete 연산들이 O(h) 시간이 걸린다는 걸 기억하자. 즉 이 연산들을 효율적으로 하려면 트리의 높이를 최소화해야 한다.이진트리에서 빼곡히 노드를 채워넣어 높이를 최소로 하면 대략 log n 정도가 되는데,균형이진탐색트리는 노드를 최대한 채워넣어 높이를 log n이 되도록 유지하는 자료구
병렬 데이터 처리와 성능
병렬 스트림컬렉션에 parallelStream을 호출하면 병렬 스트림이 생성된다.병렬 스트림이란 각각의 스레드에서 처리할 수 있도록 스트림 요소를 여러 청크로 분할한 스트림이다.병렬 스트림을 이용하면 모든 멀티코어 프로세서가 각각의 청크를 처리하도록 할당할 수 있다. 예시만약 n을 입력받아 1부터 n까지 합계를 구하는 메서드를 구현한다고 하자. 1234
인스턴스 생성과 힙 메모리
인스턴스클래스는 객체의 속성을 정의하고 기능을 구현하여 만들어놓은 코드 상태. 이 클래스를 기반으로 new 키워드를 사용하여 인스턴스를 생성. 힙 메모리생성된 인스턴스는 **동적 메모리(heap memory)**에 할당된다. c/cpp에서는 프로그래머가 직접 사용한 메모리를 해제해줘야 하지만 자바는 garbage collector가 주기적으로 사용
함수와 메서드
함수 호출과 메모리1234567891011public static int add(int num1, int num2){ int result; result = num1 + num2; return result;}public static void main(String[] args){ int n1 = 20; i
web 개론
웹의 기본 3가지 요소 URI Uniform Resource Identifier. 리소스 식별자다양한 정보에 접근할 수 있는 정보 HTTP Hypertext Transfer Protocol어플리케이션 컨트롤GET, POST, PUT… HTMLHyper Text Markup LanguageXML 바탕으로 한 범용 문서 포맷.브라우저가 사용자가 볼 수
6. 스케쥴링 알고리즘의 기본
프로세스란?메모리에 올려져 실행 중인 프로그램은 프로세스라고 한다.프로세스는 작업, task, job과 혼용되어 사용한다. 하지만 응용프로그램 != 프로세스다.왜냐면, 한 응용프로그램에 여러 개의 프로세스로 이뤄져있을 수 있기 때문! 스케쥴러스케줄러는 프로세스 실행을 관리하는 녀석. RTOS(RealTime OS) 응용 프로그램 실시간 성능 보장
5. 배치 처리, 멀티 태스킹, 멀티 프로세싱, 멀티 프로그래밍
프로세스 스케줄링배치 처리배치 처리는 어플리케이션을 순차적으로 처리하는 방식이다. 마치 큐처럼 FIFO방식을 준수한다. 단점어떤 프로그램은 실행이 너무 오래 걸려서, 다른 프로그램이 실행될 때까지 많이 기다려야 하는 경우가 존재.동시에 여러 작업이 불가능하다.(동시성)여러 사용자가 한 컴퓨터를 사용할 때 비효율적이다.(다중 사용자 지원) 이런 단점을 극
스트림으로 데이터 수집
컬렉터란 무엇인가?일단 예시를 하나 보자. 123456789101112131415//통화별로 트랜잭션을 그룹화한 코드(명령형 버전)Map<Currency, List<Transaction>> transactionsByCurrencies = new HashMap<>();for (Transaction transaction : tr