justgo_developer

트리: 부모-자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조부모는 여러 자식을 가질 수 있지만 자식은 하나의 부모를 갖는다.이진트리는 각 노드가 최대 2개의 자식을 가지는 트리위의 그림은 포화이진트리 구조이다. 모든 노드가 2개의 자식을 가지고 있다.트리의 최상단 노드를 루트(root)라고 한다.루트로부터 어떤 노드까지의 거리를 그 노드의 깊이(Depth)라 한다.깊이가 같은 노드끼리의 집합을 레벨(level)이라 한다.같은 부모를 가진 노드들을 형제(Sibling)노드라 한다. 트리의 표현배열표현법 : 각 노드에 인덱스를 부여하여 배열에 저장하는 방법링크표현법 : 다음 노드를 가리키는 포인터 변수를 이용하여 부모노드가 자식노드를 가리키는 방법트리의 순서가 배열의 인덱스가 되어 1번부터..

동적계획법1. 일반적으로 최적화문제(최소값,최대값) 혹은 카운팅 문제에 적용됨2. 주어진 문제에 대한 순환식을 정의한다.3. 순환힉을 memoization 혹은 bottom-up 방식으로 푼다. - subproblem들을 풀어서 원래 문제를 푸는 방식, 그런 의미에서 분할정복법과 공통성이 있음- 분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않음- 즉 서로 overlapping하는 subproblem들을 해결함으로써 원래 문제를 해결 분할정복법동적계획법 Optimal Substructure- 어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말한다.- 분할정복법/탐욕..

행렬 경로 문제 - 정수들이 저장된 n x n 행렬의 좌상단에서 우하단까지 이동한다.단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다.- 방문한 칸에 있는 정수들의 합이 최소화되도록 하라. Recursive algo. int mat(int i, int j){if (i==1 && j==1)return m[i][j];else if(i==1)return mat(1,j-1) + m[i][j];else if(j==1)return mat(i-1,1) + m[i][j];elsereturn Math.min(mat(i-1,j) , mat(i,j-1) ) + m[i][j]; } => 비효율적 Memoization:계산된 결과값을 캐시에 저장int mat(int i, int j){if(L[i][j] != -1)return L..

큐(Queue) 큐는 데이터의 제거는 가장 앞에서 수행되며, 데이터의 삽입은 가장 뒤에서 수행되는 제한된 리스트 구조가장 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO- first in first out)형태의 자료구조이다. 가장 오래전에 입력된 데이터를 front라고 하며가장 최근에 입력된 데이터를 rear라고 한다. 삭제는 front에서 이루어지고삽입은 rear에서 이루어 진다. 삽입 - insert: 리스트 끝 부분을 가리키는 rear에서 발생하며데이터가 삽입 될때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.삭제(추출) - remove: front가 가리키고 있는 데이터를 꺼낸 후 front값을 하나 증가 시키도록 구현한다.front값이 rear를 추월하게 되면 더 이상 제거..

스택(Stack)-배열 이용: 가장 최근에 들어간 데이터가 먼저 나오는 구조후입선출(Last In First Out)이라고 한다. 배열은 사이즈가 정해져 있다.현재 데이터의 위치를 알기 위해 top이라는 변수를 사용(스택포인터) Push : 스택에 데이터를 넣는 작업Pop : 스택에 들어 있는 데이터를 빼내는 작업 실제로 배열을 이용한 스택 구조에서는 top의 위치를 변경함으로써데이터를 빼낸 것처럼 처리한다. Push: 스택에 데이터가 가득 찼는지 확인 후 가득차있지 않다면 데이터를 넣어주는 작업Pop : 스택에 데이터가 있는지 확인 후 데이터 배내는 작업 연결리스트를 이용한 스택: 연결리스트를 이용한 스택 구현은 스택의 크기가 정해져있지 않고 동적으로 늘어날 수 있다. 첫 노드를 head, 마지막 노드..

동적계획법(DP) Fibonacci Numbers->recursion으로 하니 많은 계산이 중복됨Memoization: 중간 계산 결과를 cahing함으로써 중복 계산을 피함bottom-up 방식배열을 이용해 순환식을 bottom-up방식으로 계산하는 것은 동적계획법이라ㅗㄱ 한다. 이항계수(Binomial Coefficient)->많은 계산이 중복됨 Memoization Dynamic Programming Memoization vs Dynamic Programming- 순환식의 값을 계산하는 기법들이다.- 둘 다 동적계획법의 일종으로 보기도 한다.- Memoization 은 top-down방식이며, 실제로 필요한 subproblem만을 푼다.- 동적계획법은 bottom-up 방식이며, recursion에..

가상메모리: 한정된 물리 메모리의 한계를 극복하고자 디스크와 같은 느린 저장장치를 활용해, 더 많은 메모리를 활용할 수 있게 해 주는 것 Principle of Locality(지역성의 원리): 프로그램이 가장 최근에 접근했던 데이터를 다시 접근하거나,최근에 참조했던 데이터 근처의 주소를 참조하는 경향이 있음. *Principle of Locality라는 특성 덕분에 virtual memory가 효과적으로 운영 가능 Thrashing(쓰레싱): 너무 자주 페이지 교체가 일어나는 현상. 어떤 프로세스가 계속적으로 페이지 부재가 발생하여 프로세스의 처리시간보다 페이지 교체 시간이 더 많아 지는 현상 ■ Paging - simple paging 기법에 비해 page number에 해당하는 bit수가 많아졌다...

Floyd-warshall algorithm(all-to-all) - 가중치 방향 그래프 G=(V,E) , V={1,2,...n}- 모든 노드 쌍들간의 최단경로의 길이를 구함- d^k[i,j] : 중간에 노드집합 {1,2,....k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이경로찾기 경로출력하기

import java.util.*; public class Main {static int T;static int M;static int N;static int K;static int[][] map;static boolean[][] visit;static int[] dx = {0,1,0,-1};static int[] dy = {1,0,-1,0}; public static void main(String[] args) {Scanner sc = new Scanner(System.in);T = sc.nextInt();for(int i=0;i

Bellman-Ford 알고리즘 한가지가능의예일뿐 과정은 다를수 있다. Dijkstra의 알고리즘- 음수 가중치가 없다고 가정- s로뷰토의 최단경로의 길이를 이미 알아낸 노드들의 집합 s를 유지. 맨 처음엔 S={공징합}.- Loop invariant : S에 포함되지 않는 u에 대해서 d(u)는 이미 s에 속한 노드들만 거쳐서 s로부터 u까지 가는 최단경로의 길이- d(u)가 최소인 노드 u(s에 속하지않고)를 찾고, s에 u를 추가- s가 변경되었으므로 다른 노드들의 d(v)값을 갱신 d(v) = min{d(v),d(u)+w(u,v)}즉, 에지(u,v)에 대해서 relaxation하면 Loop invariant가 계속 유지됨