justgo_developer

행렬 경로 문제 - 정수들이 저장된 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, 마지막 노드..