뚭

데이터 통신: 컴퓨터의 발달을 배경으로 하여 생겨난 것으로 컴퓨터와 각종 통신기기 사이에서 디지털

                 형태로 표현된 2진 정보 송수신을 말함

정보 통신: 컴퓨터와 통신 기술의 결합에 의해 통신 처리 기능과 정보처리 기능, 정보의 변환 저장과정이

             추가된 형태의 통신

통신의 3요소: 정보원, 수신원, 전송 매체

정의 단계: 무엇(What)을 처리하리하는 소프트웨어를 개발할 것인지 정의하는 단계

개발 단계: 어떻게(How) 에 초점을 두고 실제적으로 소프트웨어를개발하는 단계

유지보수 단계: 소프트웨어를 직접 운용하며 변경에 초점을 두고 여러 환경 변화에 따라 소프트웨어를

적응 및 유지시키는 단계 

소프트웨어 공학은 소프트웨어의 위기를 극복하기 위한 방안으로 연구된 학문

IEEE 소프트웨어 공학 표준용어 사전: 소프트웨어의 개발 , 운용, 유지보수, 폐기 처분에 대한 체계적인 접근 방안

Fairely: 지정된 비용과 기간내에 소프트웨어를 체계적으로 생산하고 유지보수한는데 관련되 기술적이고 관리적인 원리

Boehm: 과학적인 지식을 소프트웨어 설계와 제작에 응용하는 것이며 이를 개발, 운용, 유지보수하는데 필요한 문서 작성 과정

소프트웨어 공학의 기본원칙

  1.현대적인 프로그래밍 기술을 계속 적용

  2.개발된 소프트웨어의 품질이 유지, 지속 검증

  3. 소프트웨어 개발 관련 사항 및 결과 기록

좋은 품질 소프트웨어

 1.사용자 요구대로 작동

 2.하드웨어 자원을 효율적으로 이용

 3.일정 시간 내에 주어진 조건하에 원하는 기능 실행

 4. 애매모호함 없이 처리 절차에 맞게 수행 정확한 결과 산출

 5. 소프트 웨어의 개발, 유지 보수 등 초기예상한 비용이내 수행

 6. 적당한 사용자 인터페이스 제공으로 사용하기 편리해야함

 7. 유지보수 용이

 8. 가능한한 잠재적 에러가 적어야함

 9. 신뢰성이 높고 효율적이어야함

소프트웨어 : 하드웨어를 동작시켜 사용자가 작업을 편리하게 수행하도록 하는 프로그램과 자료구조 등을 총칭함

 특징: 상품성, 견고성, 복잡성, 순응성, 비가시성, 비마모성,비제조성,비과학성

시스템: 공통의 목적이나 목표를 달성하기 위하여 여러가지 상호 관련된 요소들을 유기적으로 결합한 것으로

구성 요소는 입력, 처리 ,출력, 제어 , 피드백으로 나눔

피드백: 출력된 결과가 예정된 목표를 만족시키지 못할경우 목표 달성을 위해 반복처리

 소프트웨어 위기

여러가지 원인에 의해 소프트웨어 개발 속도가 하드웨어 개발 속도를 따라가지 못해 소프트웨어에 대한 

사용자들의 요구사항을 처리 할수없는 문제 

실시간 접근성 : 수시적이고 비정형적인 질의(조회)에 대하여 실시간으로 처리 응답 가능

계속 적인 변화: 새로운 데이터의 삽입 삭제 갱신으로 항상 최신 데이터 유지

동시 공유:여러 사용자가 동시에 원하는 데이터를 이용 할수 있음

내용에 의한 참조:  데이터베이스에 있는 데이터를 참조할때 데이터의 주소나 위치에 의해서가 아니라 

                         사용자가 요구하는 데이터 내용으로 데이터를 찾음 

통합된 데이터 : 자료의 중복을 배제한 데이터의 모임

저장된 데이터 : 컴퓨터가 접근할 수 잇는 저장 매체에 저장된 자료 

운영 데이터 : 조직의 업무를 수행하는데 있어서 반드시 필요한 자료

공용 데이터 : 여러 응용 시스템들이 공동으로 소유하고 있는 자료 

정보시스템 :

 1.조직체에 필요한 데이터 수집

 2.저장해 두었다가 필요시에 처리해서 의사 결정에 유용한 정보 생성,분배하는 수단

 3. 사용하는 목적에 따라 여러 시스템으로 사용

    (ex 경영 정보 시스템, 군사 정보 시스템, 인사 행정 정보 시스템, 의사 결정 지원 시스템)

자료: 현실 세계에서 관찰이나 측정을 통해 수집한 단순한 사실이나 결과값

정보: 의사 결정에 도움을 줄수 잇는 유용한 형태로 자료를 가공해서 얻은 결과물 

자료 처리 시스템 : 정보 시스템이 사용할 자료를 처리하는 정보 시스템의 서비 시스템

(ex 일괄처리 시스템, 온라인 실시간 처리 시스템, 분산 처리 시스템)

데이터웨어 하우스 : 조직이나 기업체의 중심이 되는 주요 업무 시스템에서 추출되어 새로이

생성된 데이터베이스로서 의사결정 지원 시스템

programmers.co.kr/learn/courses/30/lessons/42898

정답:  201009

참고 동적계획법에서 재귀가 아니라 이중for문을 사용해야 해결이 쉬워진다. 

참고링크 : 

www.youtube.com/watch?v=6NCae9uz5Ss

#include <string>
#include <vector>
#include<iostream>
using namespace std;
void Print(vector<vector<int>> path){
    for(int i=0;i<path.size();i++){
        for(int j=0;j<path[i].size();j++){
            cout<<path[i][j]<<",";
        }
        cout<<endl;
    }
    cout<<endl;
}
long long Mod=1000000007;



int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<int>tmpMap(m,0);
    vector<vector<int>>map(n,tmpMap);
    
    for(int i=0;i<puddles.size();i++){
        for(int j=0;j<puddles[i].size();j++){
            puddles[i][j]-=1;
        }
    }
      for(int i=0;i<puddles.size();i++){
          map[puddles[i][1]][puddles[i][0]]=-1;
    }
    
       
    map[0][0]=1;
  
    map[n-1][m-1]=0;
  
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
              
            
            
            if(map[i][j]==-1){
                map[i][j]=0;
                continue;
            }
            
            if(i!=0){
               map[i][j]+=map[i-1][j]%Mod;
            }
                
            if(j!=0){
                map[i][j]+=map[i][j-1]%Mod;
            } 
                
            //map[i][j]=map[index0][j]+map[i][index1];
                
            
          //  Print(map);
        }
    }
   // Print(map);
    
  
  // long long answered=func(n-1,m-1,map);
    
    answer=map[n-1][m-1]%Mod;
   // cout<<answer;
    
    
    return answer;
}

먼저 우리가 지나갈 MAP을 만들어준다.

vector<int>tmpMap(m,0);
vector<vector<int>>map(n,tmpMap);

그러면 NxM 행렬의 map의 경로가 나올것이다.

다음은 지날수 없는 장애물을 map에 설정해준다.

 for(int i=0;i<puddles.size();i++){
        for(int j=0;j<puddles[i].size();j++){
            puddles[i][j]-=1;
        }
    }
      for(int i=0;i<puddles.size();i++){
          map[puddles[i][1]][puddles[i][0]]=-1;
    }
    
       

-1은 현재 갈수없는 곳으로 지정된값이다. 

그렇다면 이제 맵이 전체적으로 완성되었으니 동적계획법을 이용하여 경로를 찾아보자 

맨처음 우리는 0,0에서 시작하므로 1을 입력해준다 그리고 마지막 도착지점은 혹시 장애물이 지정되어 있을수도 있으므로 미리 0으로 지정해둔다. 

 map[0][0]=1;
  map[n-1][m-1]=0;

여기서 돌아가는 원리는 하나하나 따져보자 

1,0,0,0,
0,-1,0,0,
0,0,0,0,

위의 같이 생긴 맵이라고 가정하자

 for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
              
            
            
            if(map[i][j]==-1){
                map[i][j]=0;
                continue;
            }
            
            if(i!=0){
               map[i][j]+=map[i-1][j]%Mod;
            }
                
            if(j!=0){
                map[i][j]+=map[i][j-1]%Mod;
            } 
                
            //map[i][j]=map[index0][j]+map[i][index1];
                
            
          //  Print(map);
        }
    }

처음엔 (0,0)은 이 두조건에 걸리므로 패스하고 다음 으로 넘어간다.

if(i!=0),if(j!=0) 

그다음 (0,1)로 돌아간다. 

이 조건에 걸리게 되어 현재 

map[0][1]+=map[0][1-1]; 이된다. 

  if(j!=0){
map[i][j]+=map[i][j-1]%Mod;
 } 

그렇게 되면 아래와 같은 형태가 된다. 즉 오른쪽으로 한칸 이동하고 그 경로를 누적하여 기억하는것이다.

1,1,0,0,
0,-1,0,0,
0,0,0,0,

여기선 j가 끝까지 가는동안 i는 계속 0이므로 이전 j값과 다음 이동 j값으로 누적한다 그러면 

아래와 같이 될것이다

1,1,1,1,
0,-1,0,0,
0,0,0,0,

. 이제 j가 끝나고 다시 i값이 증가한다. 이때 i는 0이 아니므로 

아래의 조건에 만족한다 j는 초기화 되서 0이므로 j의 위의 조건에 부합하여 패스 된다. 

if(i!=0){
  map[i][j]+=map[i-1][j]%Mod;
    }

아래와 같은 결과가 나온다.

1,1,1,1,
1,-1,0,0,
0,0,0,0,

그렇다면  i값은 1로 고정되어 있는 상태에서 다시 j값이 증가하면서 아래의 조건이 만족한다. 

if(i!=0){
  map[i][j]+=map[i-1][j]%Mod;
    }
if(j!=0){
map[i][j]+=map[i][j-1]%Mod;
 } 

원래는 위의 조건이 맞아야하지만 장애물 -1이 있으므로 

이 조건이 들어가게 된다.

continue에 의해서  j값은 증가하지만 아래의 조건은 패스하게 된다. 

if(map[i][j]==-1){
     map[i][j]=0;
    continue;
  }

패스 했다는거는 더이상 값에 영향을 주지 않기위해 0으로 바꾸엇다.

그러면 아래와 같다.

1,1,1,1,
1,0,1,0,
0,0,0,0,

이상태에서 다음 j값을 증가시키는데 이 두조건이 모두 해당된다.

현재 i=1,j=3 이므로 

if(i!=0){
  map[i][j]+=map[i-1][j]%Mod;
    }
if(j!=0){
map[i][j]+=map[i][j-1]%Mod;
 } 

map[0][3],map[1][2]의 값을 map[1][3] 에게 누적해준다 

그러면

1,1,1,1,
1,0,1,2,
0,0,0,0,

이러한 결과가 누적된다.

다음엔 마찬가지로 반복하면 

1,1,1,1,
1,0,1,2,
1,1,2,4,

이상태의 결과가 나오며 마지막 지정 값이 4가지의 경우로 길을 찾을수 있다는것을 알게된다. 

마지막에 배열의 크기가 클수 있으므로 조건에서 1,000,000,007 나머지를 계산해준다.

==========================================================================

재귀로 시도했으나 효율성 문제로 인해 안됨 

그래서 이중for문을 사용한  DP를 이용해야하는듯하다. 

아래는 깊이우선 탐색과 dp 재귀로 풀었을떄 방식이다.

일단 효율문제 제외하고 정확성 문제는 다 맞는듯하다.

정확성 8번도 시간초과인걸로 봐서 효율성 문제인듯 

#include <string>
#include <vector>
#include<iostream>
#include<deque>
using namespace std;
long nor=1000000007;
deque<int>dq;
long long anwerdd;
void Print(vector<vector<int>> path){
    for(int i=0;i<path.size();i++){
        for(int j=0;j<path[i].size();j++){
            cout<<path[i][j]<<",";
        }
        cout<<endl;
    }
    cout<<endl;
}

long long  func( vector<vector<int>> path,int m,int n,long rightIndex,long downIndex){
    if(rightIndex>m-2&&downIndex>n-2){
        anwerdd++;
    }
    if(path[downIndex][rightIndex]==1){
        return 0;
    }
    path[downIndex][rightIndex]=2;
   // Print(path);
   // 
     if(rightIndex<m-1){ 
       
       //  path[downIndex][rightIndex]=2;
    func(path,m,n,(rightIndex+1),downIndex);//rigt
    }
    if(downIndex<n-1){
        
        // path[downIndex][rightIndex]=2;
    func(path,m,n,rightIndex,(downIndex+1));//down
     }
    
    return anwerdd%1000000007; 
}

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    
    vector<vector<int>> lake;

 
    vector<int>tmps(m,0);
    vector<vector<int>> path(n,tmps);
  
    
    for(int i=0;i<puddles.size();i++){
        for(int j=0;j<puddles[i].size();j++){
           
           puddles[i][j]-=1;
            
        }
    }
    //Print(puddles);
   for(int i=0;i<puddles.size();i++){
      
       
           if(puddles[i][0]<m&&puddles[i][1]<n){
           path[puddles[i][1]][puddles[i][0]]=1;
               }
       
     
     
   }
   path[0][0]=0;
  path[n-1][m-1]=0;
  
    
    long long answered=func(path,m,n,0,0);
    
    answer=answered;
    
    return answer%nor;
}

기존에는 깊이 우선 탐색 이용했으나 이번엔 

개선 된 DP 이용 상황 현재  테스트 5를보면 이전엔 18초 걸리던게 9초 줄임 

#include <string>
#include <vector>
#include<iostream>
using namespace std;
void Print(vector<vector<int>> path){
    for(int i=0;i<path.size();i++){
        for(int j=0;j<path[i].size();j++){
            cout<<path[i][j]<<",";
        }
        cout<<endl;
    }
    cout<<endl;
}
long long Mod=1000000007;
long long func(int n,int m,vector<vector<int>>map){

    if(map[n][m]==-1){
        return 0;
    }
    
    if(m<=0&&n<=0){
        return 1;
    }
    
    
  //  long right=0;
 //   long down=0;
//    if(m>0){
  //  right=func(n,m-1,map)%Mod;
  //      }
//    if(n>0){
 //   down=func(n-1, m,map)%Mod;
    //    }
    
    return  (((m>0)?func(n,m-1,map):0)+((n>0)?func(n-1, m,map):0))%Mod;//right+down;    //func(n,m-1,map)%Mod+func(n-1, m,map)%Mod;
}


int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    vector<int>tmpMap(m,0);
    vector<vector<int>>map(n,tmpMap);
    
    for(int i=0;i<puddles.size();i++){
        for(int j=0;j<puddles[i].size();j++){
            puddles[i][j]-=1;
        }
    }
      for(int i=0;i<puddles.size();i++){
          map[puddles[i][1]][puddles[i][0]]=-1;
    }
    
       
    map[0][0]=0;
    map[n-1][m-1]=0;
    
   // Print(map);

   long long answered=func(n-1,m-1,map);
    
    answer=answered;
    
    
    
    return answer;
}