뚭

git이 초기화를 시켜주지 않아서 발생하는 오류 

git init

명령어를 gitbash에 넣어주면 해결

https://programmers.co.kr/learn/courses/30/lessons/43162#

정답:

#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
vector <int>q;
vector <bool>bCheck;
int func(vector<vector<int>> computers,int index,int n){
    bCheck[index]=true;
    cout<<"index:"<<index<<endl;
    for(int i=0;i<n;i++){
    if(computers[index][i]==1&&bCheck[i]==false){
           q.push_back(i);
        }
     }
   
    if(!q.empty()){
      int tmp=q[0];
      q.erase(q.begin());
      return func(computers,tmp,n);
    }
     for(int i=0;i<q.size();i++){
          cout<<"q:"<<q[i]<<endl;
     }
    return 1;
    // if(q.size()>0){
         // func(computers,q[0],n);
   //  }
    
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
     for(int i=0;i<n;i++){
         bCheck.push_back(false);
     }
    for(int i=0;i<n;i++){
        if(bCheck[i]==false){
            answer =answer+func(computers,i,n);
            }
    }
    return answer;
}

201008

지난번과 비슷하게 푼듯하다 

여기서 기존 dfs를 사용방법과 달리 stack(vector)을 같이 이용했다

개인적으로 deque를 이용하는것도 좋은 방법일듯하다 

문제를 푸는 와중엔 생각이 안나서 vector로 했는데 다음엔 deque를 이용할것이다. 

stack(vector) 역할은 가야할 경로의 예약이다. 

왜냐하면 

[1,1,0,0,1]

[1,1,0,0,0]

[0,0,1,0,0]

[0,0,0,1,0]

[1,0,0,0,1]

이런 경로의 경우 일반적인 dfs만 사용하면 

1번 경로와 2번경로는 이어지지만 5번 경로의 안이어 질수도 있다 그래서 

미리 내가 가야할 경로를 예약해둔다 

처음 [1,1,0,0,1] 1번 경로 

미리 vector에 

저장한다 배열은 처음이 0이므로 0으로 시작하겠다

0 ,1,4 번이 스택에 저장된다 

  for(int i=0;i<n;i++){
          if(bCheck[i]==false&&computers[index][i]==1){
               bCheck[index]=true;
              computers[index][i]=0;
              q.push_back(i);
          }
      }
  

그렇다면 

저장된 q에 

다음 func로 넘어간다 맨처음은 0이므로 패스 하겠다 

 while(!q.empty()){ 
         int tmp=q[0]; 
         
          q.erase(q.begin()); 
        return func(n, computers,tmp,0);  
           
      }

그러면 0번 (1번노드)는 이미 전부 지나 온 경로이므로 진행은 생략 하겠다 다음

1번을 통해 2번노드 경로로 간다. 

그러면  [1,1,0,0,0] 현재 이런식으로 되어있다

현재 0번인 1번 노드는 이미 지나온 경로이므로 stack에 쌓지 않는다.

지나온 경로는 vector<bool>bCheck로 체크 해주고 있다.

그러면 여기선 1번을 제외하곤 전부 0이며 또한 이미 2번노드(1번)은 들어왔기때문에 stack에 쌓지않는다.

그상태에서 현재 스택 4번을 간다. 

그러면 4번인 5번 경로를 확인한다.

[1,0,0,0,1] 여기도 마찬가지로 이미 0번(1번노드)는 지낫으며 자신을 제외하곤 없으므로 스택을 쌓지않는다.

그러면 더이상 stack이 끝나므로 

while(!q.empty()){
         int tmp=q[0];
        
          q.erase(q.begin());
        return func(n, computers,tmp,0); 
          
      }

while문은 끝난다 그러면서 return 되면서 1을 반환한다. 

다음은 메인함수에 있는

    for(int i=0;i<computers.size();i++){
        if(bCheck[i]==false){
           answer+=func(n, computers,i, 0);
            }
  }

함수에서 이미 지난 0 ,1,4 (1번,2번 5번 노드를 )제외한 다음 노드 3번 노드를 간다.

[0,0,1,0,0]

보면 q에 stack은 비어있다.

그래서 while을 입력되지 않고 

다음 while아래에 잇는 func(n, computers,q[0], count+1);  함수로 가서 다음 옆에 형제노드가 1이 존재하는지 검색한다.

여기선 자신 말곤 없으므로 1이 반환되고 종료된다.

그럼 다시 메인함수로 돌아오면  0 ,1,2,4 (1번,2번,3번, 5번 노드를 )제외한 다음 노드4번 노드를 간다.

[0,0,0,1,0]

마찬가지로 형재노드가 없어서 더이상 진행하지 않고 1로 반환한다 

총 합은 3으로 결정되며 경로 찾기는 종료된다.

여기서 핵심적인 부분은 stack을 이용하여 경로를 예약한다는 개념이다. 

정답:

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

int func(int n, vector<vector<int>> computers,int index,int count){
   // Print(computers);
     
       if(count>=n){
           return 1;
           }
    
      for(int i=0;i<n;i++){
          if(bCheck[i]==false&&computers[index][i]==1){
               bCheck[index]=true;
              computers[index][i]=0;
              q.push_back(i);
          }
      }
  
    
      while(!q.empty()){
         int tmp=q[0];
        
          q.erase(q.begin());
        return func(n, computers,tmp,0); 
          
      }
    
    return func(n, computers,q[0], count+1); 
    
   
    
    
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0;i<computers.size();i++)
    {
        bCheck.push_back(false);
    }
    
    for(int i=0;i<computers.size();i++){
        if(bCheck[i]==false){
           answer+=func(n, computers,i, 0);
            }
  }
    
    
    return answer;
}

https://programmers.co.kr/learn/courses/30/lessons/43164

미완: 테스트 케이스는 전부 맞았지만 채점에서 1,2번 케이스가 틀려서 원인 분석중에 있습니다.

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
vector<bool> bCheck;
vector<string> stack;
vector<vector<string>> ticketsBackUp;
string lastString;
int ticketsSize;
vector<string> Dfs(vector<vector<string>> tickets,int index,int j){
    
    cout<<endl;
     for(int i=0;i<ticketsBackUp.size();i++){
        cout<<ticketsBackUp[i][0];
        cout<<",";
         cout<<ticketsBackUp[i][1];
        cout<<endl;
    }
    cout<<endl;
    
    stack.push_back(tickets[index][0]);
    ticketsBackUp.erase(ticketsBackUp.begin()+index);
    bCheck[index]=true;
     j++;
    
    if(j==ticketsSize){
        stack.push_back(tickets[index][1]);
        
        
    }
    
    
    for(int i=0;i<tickets.size();i++){
       
        if(tickets[index][1]==tickets[i][0]&& bCheck[i]==0){
             
              Dfs(tickets,i,j);
        }
        
    }
   
  
    return stack;
    
    
}


vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    int j=0;
  
     ticketsSize=tickets.size();
    for(int i=0;i<tickets.size();i++){
        bCheck.push_back(false);
        
    }
   
    
          
  //  sort(tickets.begin(),tickets.end(),greater<vector<string>>());
    
          for(int i=0;i<tickets.size();i++){
              for(int k=0;k<tickets.size();k++){
                  
                  if(tickets[i][0]==tickets[k][0]){
                      if(tickets[i][1]<tickets[k][1]){
                          string tmp;
                          tmp=tickets[i][1];
                          tickets[i][1]=tickets[k][1];
                          tickets[k][1]=tmp;
                      }
                  }
              }
          }
        ticketsBackUp=tickets;
  //  while(tickets.size()>0){
       int start=0;
       for(int i=0;i<tickets.size();i++){
            if(tickets[i][0]=="ICN"){
                start=i;
                break;
            }
       }
    
    
        answer=Dfs(tickets,start,j);
    
    for(int i=0;i<ticketsBackUp.size();i++){
        cout<<ticketsBackUp[i][0];
        cout<<",";
         cout<<ticketsBackUp[i][1];
        cout<<endl;
    }
    
   
      //}
        
    
    
    return answer;
    
    
}

정확한 이유를 알수 가 없어서 

https://programmers.co.kr/learn/questions/7894

질문코너에 테이트 케이스 1,2번이 안되는 질문이 많았습니다 보니까 문제의 지문이 썩 좋지는 않았습니다. 

질문을 보면 테이스트 케이스의 무조건 정렬이 아니라 모든 도시를 방문하게 주어주는것 이것을 지켜야 하는것 같습니다. 

즉 모든 도시의 경로를 갈수 있을시에 정렬을 하라는 의미 인것 같습니다. 

만일 정렬을 먼저 한후에 도시 경로를 탐색 했을때 경로가 남았을 경우 그 경로로 가면 안됩니다.

 즉 미리 경로를 검색해서 최선의 경로를 만들어야 하는것 같습니다.

문제를 정확하게 표현했으면하는데 이부분은 문제를 몇번을 읽어도 이해가 쉽지 않았습니다. 

정답: 

#include <string>
#include <vector>
#include<algorithm>
#include<iostream>

using namespace std;
vector<bool>bCheck;
vector<string>stack;


bool Dfs(string str,vector<vector<string>> &tickets,int cnt){
    
    stack.push_back(str);
    
    if(cnt==tickets.size()){ //끝까지 노드 탐색했으면 true반환
       
        return true;
        
    }
    for( int i=0;i<tickets.size();i++){ //현재 자식노드 존재여부 탐색
        if(tickets[i][0]==str&&bCheck[i]==false){ //현재 노드와 일치하며 아직 진행하지 않는 노드 발견
            bCheck[i]=true; //진행 했다고 알려주는 flag 
            bool bPass=Dfs(tickets[i][1],tickets,cnt+1); //다음 자식노드로 이동 ,만약 모든 노드를 탐색을 완료 했을시 true 반환
            if(bPass==true){ // 모든 노드를 탐색을 완료 했을시 true 반환
                return true;
                }else{
            
            bCheck[i]=false; //만약 탐색이 완료되지 않는경우 현재 노드 false로 flag 변경 진행하지 않는걸로 만듬
            }
        }
    }
    stack.pop_back(); //현재 노드 stack에서 제거 
    return false; //현재노드로 진행방향이 올바르지 않았으므로 false로 반환 
    
    
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
 
    for(int i=0;i<tickets.size();i++){
        bCheck.push_back(false);
    }
    
    sort(tickets.begin(), tickets.end());

    Dfs("ICN",tickets,0);
     answer=stack;
    return answer;
}

200821- 다시 풀려니까 1번문제가 계속해서 틀림 이유를 잘모르겟음

그리고 이전에 풀었던게 훨씬 간결하게 잘풀엇음 참고하여 오답노트 만들예정

#include <string>
#include <vector>
#include<iostream>
#include<algorithm>
using namespace std;
struct PairTicketDataStru{
    
    pair<string, string >trip;
    bool bCheck;
};

bool cmp(const PairTicketDataStru v1,const PairTicketDataStru v2){

    if(v1.trip.first==v2.trip.first){
        if(v1.trip.second<v2.trip.second){
            return true;
            }
    }
    return false;
    
}

vector<string>saveData;
bool Trip(vector<PairTicketDataStru>ticketsPairStru,int totalCount,int index,int count,vector<string>saveTmpData){
    if(totalCount==count){
       
        saveTmpData.push_back(ticketsPairStru[index].trip.first);
         saveTmpData.push_back(ticketsPairStru[index].trip.second);
        saveData=saveTmpData;
       
        return true;
    }
    
    
    for(int i=0;i<totalCount;i++){
        if(ticketsPairStru[index].bCheck==false){
            ticketsPairStru[index].bCheck=true;
           
        }
        
        if(ticketsPairStru[index].trip.second==ticketsPairStru[i].trip.first&&ticketsPairStru[i].bCheck==false){
            cout<<"i."<<i<<":";  
           cout<<"["<<ticketsPairStru[index].trip.first<<","<<ticketsPairStru[index].trip.second<<"]"<<",";
            cout<<"["<<ticketsPairStru[i].trip.first<<","<<ticketsPairStru[i].trip.second<<"]"<<",";
              ticketsPairStru[i].bCheck=true;
              
              saveTmpData.push_back(ticketsPairStru[index].trip.first);
              bool bTmpCheck=Trip(ticketsPairStru,totalCount,i,count+1,saveTmpData);
          
              if(bTmpCheck==true){
                  
                return true;
                  
              }else{
                  cout<<endl;
                 
                  saveTmpData.pop_back();
               
                  ticketsPairStru[i].bCheck=false;
                  ticketsPairStru[index].bCheck=false;
                 
              } 
            
        }
  
    }
   
    
    
               
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<PairTicketDataStru>ticketsPairStru;
  
    for(int i=0;i<tickets.size();i++){  
        PairTicketDataStru tmp;
        pair<string, string >tmpP;
        tmpP.first=tickets[i][0];
        tmpP.second=tickets[i][1];
        tmp.trip=tmpP;
        tmp.bCheck=false;
        ticketsPairStru.push_back(tmp);
    }
    
    sort(ticketsPairStru.begin(),ticketsPairStru.end(),cmp);
    int totalCount=tickets.size();
    int count=1;
    bool bCheckData=false;
    vector<string>saveTmpData;
    for(int i=0;i<ticketsPairStru.size();i++){
        if(ticketsPairStru[i].trip.first=="ICN"){
          
        
            //cout<<i<<":";
           // cout<<i<<","<<totalCount<<","<<count<<",";
            bCheckData=Trip(ticketsPairStru,totalCount,i,count,saveTmpData);
             //cout<<endl;
            if(bCheckData==true){
            
                
                i=ticketsPairStru.size()+1;
                break;
                
            }else{
              //  cout<<"!";
               // cout<<endl;
                
              // cout<<ticketsPairStru[1].bCheck;
            }
        }
        
    }
    
    //for(int i=0;i<saveData.size();i++){
  //   cout<<saveData[i]<<",";
   // }
  answer= saveData;
    return answer;
}

20201008

#include <string>
#include <vector>
#include<iostream>
#include<string.h>
#include<cstring>
#include<algorithm>

using namespace std;
struct pathDataStru{
    string arrive;
    int index;
    
    
};

bool cmp(const pathDataStru &p1,const pathDataStru &p2){
    if(p1.arrive.compare(p2.arrive)<0){
        return true;
    }else if(p1.arrive.compare(p2.arrive)==0){
        return true;
    }
     return false;
    
    
}
vector<string>arriveData;
bool func(vector<vector<string>> tickets,vector<bool>bCheck,string find,int pathCount,int count){
    if(pathCount<count){
       
        if(arriveData.size()>=pathCount){
           // cout<<arriveData.size();
             // cout<<pathCount;
            return true;
               
           }
         return false;
    }
    
    vector<pathDataStru>pathStru;
    //검증
    for(int i=0;i<tickets.size();i++){
        
        if(tickets[i][0]==find&&bCheck[i]==false){
        pathDataStru tmpStru;
        tmpStru.arrive=tickets[i][1];
        tmpStru.index=i;
        pathStru.push_back(tmpStru);
        }
    }
    //cout<<find<<",";
    if(pathStru.size()>0){
        if(pathStru.size()>=2){
           
            sort(pathStru.begin(),pathStru.end(),cmp);
            //cout<<pathStru[0].arrive;
            for(int i=0;i<pathStru.size();i++){
               find=pathStru[i].arrive;
              //   cout<<"+"<<find<<",";
                
                 
                
                arriveData.push_back(pathStru[i].arrive);
               
                
                bCheck[pathStru[i].index]=true; //input시 true
                 
               bool bFuncCheck= func(tickets,bCheck,find,tickets.size(),count+1);
               //   cout<<bFuncCheck;
                if(bFuncCheck){
                    return true;
                }else if(!bFuncCheck){
                    
                 
           //       cout<<"!";
             //      cout<<"-"<<arriveData[arriveData.size()-1]<<",";
                   
                    
                    
                
                 bCheck[pathStru[i].index]=false; //돌아올때 false 경로를 전부 지나는 경로가 아닐경우 
                 arriveData.pop_back();
                    
                      
                  
                
                }
                
            }
           // func(tickets,bCheck,find,tickets.size(),count);
            
            
        }else if(pathStru.size()<2){
             find=pathStru[0].arrive;
             bCheck[pathStru[0].index]=true;
            
                
                arriveData.push_back(find);
            
           
            bool bFuncCheck= func(tickets,bCheck,find,tickets.size(),count+1);
            if(bFuncCheck){
                return true;
            }
            else if(!bFuncCheck){
                 bCheck[pathStru[0].index]=false; //돌아올때 false 경로를 전부 지나는 경로가 아닐경우 
                 arriveData.pop_back();
                    
                return false;
            }
            
        }
        
    }
    
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) {
    vector<string> answer;
    vector<bool>bCheck;
   
    for(int i=0;i<tickets.size();i++)
        bCheck.push_back(false);
    
    
       arriveData.push_back("ICN");
    
    
    func(tickets,bCheck,"ICN",tickets.size(),1);
   
    answer=arriveData;
    
    
    return answer;
}

가장 기본적인 경로를 따라가는걸 구현할때 

도착지점이 같은 경로들이 존재한다. 

이럴경우 같은 경로중 도착에 알파뱃 순으로 지정한다. 

이때 sort 정렬을 이용해준다 .

만약 

도착 지점에 더이상 도착 하지못하는 경우가 생기면 

그 이전 경로로 돌아가서 다시 길을 찾도록 한다 

여기서 조건은 무조건 경로를 전부 돌아야한다 .

아마 대부분의 사람들이 이것 때문에 시간 낭비를 하는듯 하다.

문제가 별로 안좋다 . 조건을 확실히 적어줘야는데 애매하게 전부 다 갈수있는것처럼 표기되어있다 조건을 잘 설명해준 문제는 아니다.

그 조건을 이용하여 만약에 도착했을경우에 true로 반환 도착하지 못했을경우엔 false로 반환후에 

false인경우에는 이전 도착 경로와 경로를 지낫다는 사실을 없애줘야한다. 

그러면 더이상 알파뱃 순으로 아닌 이후 알파뱃순으로 경로를 찾는다. 

https://programmers.co.kr/learn/courses/30/lessons/42583#

정답:

#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
struct customTru{
    int weight;
    int time; 
};
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int totalWeight=0;
  
    int j=0;
    vector<customTru> bridge;
    vector<int>arrive;
    static int count=truck_weights.size();
  //  queue<int> bridge;
    while( truck_weights.size()>0||bridge.size()>0){
           answer++;
        
         
         //다리위 진행 시간
        for(int k=0;k<bridge.size();k++){
            (bridge.begin()+k)->time=(bridge.begin()+k)->time+1;
           // cout<<"outputTime:";//<<//outputTime<<endl; //각각의 다리위의 트럭의 시간
        }
       
         //길이
        if(!bridge.empty()){  
          if(bridge.begin()->time>bridge_length){ //첫번째 트럭이 다리의 길이를 걷넛을때 
               totalWeight= totalWeight-bridge.begin()->weight; //첫번째 트럭 무게 제거 
              // bridge.pop(); //다리에서 제거 
              arrive.push_back(bridge.begin()->weight);
              bridge.erase(bridge.begin());
              
   
               }
        }
        
        
        //무게
       if(!truck_weights.empty()){
       if(totalWeight+truck_weights[0]<=weight){
           customTru tmp;
           tmp.weight= truck_weights[0]; //현재 트럭 
           tmp.time=1;//들어온트럭 시간
           bridge.push_back(tmp); //다리위
           truck_weights.erase(truck_weights.begin());//truck_weights bridge로 넘어감
           totalWeight=totalWeight+ (bridge.back()).weight;//현재 다리의 총무게 
           
       }
        }
        
     
    }
    
    
    return answer;
}

200819

#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
struct BridgeOnTruckWeightLength{
    int weight;
    int length;
};
vector<BridgeOnTruckWeightLength>bridgeOnTruck;
int bridgeNowWeight=0;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
 
     
  while(truck_weights.size()>0||bridgeOnTruck.size()>0){
      /*
       cout<<"answer:"<<answer;
          cout<<endl;
      cout<<"truck_weights:";
          for(int i=0;i<truck_weights.size();i++){
              cout<<truck_weights[i]<<",";
          }
          cout<<endl;
          cout<<"bridgeNowWeight:"<<bridgeNowWeight<<",";
          cout<<endl;*/
      //bridgeNowWeight=0;
      
  for(int i=0;i<bridgeOnTruck.size();i++){
            bridgeOnTruck[i].length+=1;//현재 존재하는 트럭들 이동
            
   }
      
    for(int i=0;i<bridgeOnTruck.size();i++){
        if(bridgeOnTruck[i].length>=bridge_length){
                bridgeNowWeight-=bridgeOnTruck[i].weight;
                bridgeOnTruck.erase(bridgeOnTruck.begin()+i);//거리에 도달시 pop
                
            }
    } 
    
    
   
  
    
     //들어올 트럭과 이전 트럭 무게의 다리위 무게 체크
      
    if(bridgeNowWeight+truck_weights[0]<=weight&&truck_weights.size()>0){
        
        
        
        
        BridgeOnTruckWeightLength tmpData;
        tmpData.weight=truck_weights[0];
        tmpData.length=0;
        
           //다리위 에 트럭 무게
         bridgeNowWeight+=truck_weights[0];
        
        bridgeOnTruck.push_back(tmpData);//트럭 다리위로 출발 
        
        truck_weights.erase(truck_weights.begin());//출발햇으니 시작점에서 제거 
   
        
        
    }
         
         
    
      answer++;
   }
   
   
    
    
    //다리를 완전히 지남 
    
    
    
    return answer;
}

지난번엔 상당히 시간많이 잡아먹엇는데 생각보다 쉽게 풀엇다 

이부분떄문에

정답이 안되는 코드인데 보면 길이가 도달해서 트럭이 나가면서 bridgeOnTruck 사이즈가 줄어들면서 for문이 최종 2번돌아야는게 1번만 돌고 끝이난다.

for(int i=0;i<bridgeOnTruck.size();i++){
            bridgeOnTruck[i].length+=1;//현재 존재하는 트럭들 이동
              if(bridgeOnTruck[i].length>=bridge_length){
                bridgeNowWeight-=bridgeOnTruck[i].weight;
                bridgeOnTruck.erase(bridgeOnTruck.begin()+i);//거리에 도달시 pop
                
            }
   }
      
   

이를 해결을 위해서 길이를 먼저 더해서 계산해주고 

이제 다리를 지난 트럭들을 뺴주는 식으로 가야한다. 

for(int i=0;i<bridgeOnTruck.size();i++){
            bridgeOnTruck[i].length+=1;//현재 존재하는 트럭들 이동
            
   }
      
    for(int i=0;i<bridgeOnTruck.size();i++){
        if(bridgeOnTruck[i].length>=bridge_length){
                bridgeNowWeight-=bridgeOnTruck[i].weight;
                bridgeOnTruck.erase(bridgeOnTruck.begin()+i);//거리에 도달시 pop
                
            }
    } 
    

201007

이번에 dequpe를 이용해서 풀어보았다

다리위가 즉 들어올땐 push_back 나갈때 pop_front를 이용하였으며 

while문 돌릴때 truch_weights 값이 전부다 빠지면truch_weights[0] 를 사용이 불가하니 이때 꼭 체크를하자 truch_weights.size()>0이상체크를해주자

#include <string>
#include <vector>
#include<iostream>
#include<deque>
using namespace std;
struct truckState{
  int weight;
   int length; 
};


int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int bridgeWeightLimit=weight;
    int bridgeWeightNowState=0;
    int count=0;
    deque<truckState> bridge_state; //다리 현재 상태
    for(int i=0;i<truck_weights.size();i++){
      //  cout<<truck_weights[i];
    }
    
  while(truck_weights.size()>0||bridge_state.size()>0){
     answer++;
    if(truck_weights.size()>0){
    if(bridgeWeightNowState+truck_weights[0]<=bridgeWeightLimit){
         bridgeWeightNowState=bridgeWeightNowState+truck_weights[0];  //들어오는 트럭 
        
         truckState tmpState;
         tmpState.weight=truck_weights[0];
         tmpState.length=1;
      //  cout<<truck_weights[1]<<",";
      //  cout<<truck_weights[0]<<",";
        bridge_state.push_back(tmpState);
        truck_weights.erase(truck_weights.begin());
       //  count++;
    }
 }
      
      
    if(bridge_state.size()>0){
    if(bridge_state[0].length<=bridge_length){
        for(int i=0;i<bridge_state.size();i++){
             
            bridge_state[i].length+=1;
          //  cout<< bridge_state[i].weight<<",";
           //  cout<< bridge_state[i].length<<",";
            
           
        }
      //   cout<<":";
     //  cout<<answer;
      //  cout<<endl;
        
        
    }
        
    if(bridge_state[0].length>bridge_length){
        bridgeWeightNowState-=bridge_state[0].weight;
        bridge_state.pop_front();
       
    }
        
    }
     
    
       
    }
 
 answer++;
    
    return answer;


}

https://programmers.co.kr/learn/courses/30/lessons/42576

정확성 정답 -> 효율성에서 틀림 

#include <string>
#include <vector>

#include<algorithm>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    sort(participant.begin(),participant.end());
    sort(completion.begin(),completion.end());
    
    int saveHash=0;
   for(int i=0;i<participant.size();i++){

       
       for(int j=0;j<completion.size();j++){
           if(participant[i].compare(completion[j])==0){

              participant[i]=" ";
              completion[j]=" ";
               
               continue;
           }
             }
  }
          
     
    for(int i=0;i<participant.size();i++){
        if( participant[i]!=" "){
    
        answer=participant[i];
           }
    }

    
  
    return answer;
}

2020/04/01 - [C++(Math&알고리즘)] - Hash STL

이용을 해서 효율성 문제를 해결

#include <string>
#include <vector>
#include<unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string ,int > key;
    for(auto&i:participant)
        key[i]++;
    
    for(auto&i:completion)
        key[i]--;

    for(auto&i:key){
        if(i.second>0){
            answer=i.first;
            break;
        }
    }
    
    return answer;
}

200816 

지난번과 비슷하게 푼것같다.

#include <string>
#include <vector>
#include<unordered_map>
#include<iostream>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
  string answer = "";  
unordered_map<string,int>part;
    for(int i=0;i<participant.size();i++){
        part[participant[i]]++;
        }
     for(int i=0;i<completion.size();i++){
         
         part[completion[i]]--;
     }
    
    for(int i=0;i<participant.size();i++){
     if( part[participant[i]]==1){
         answer=participant[i];
     }   
    }
    
    return answer;
}

unordered_map은 일반적으로 

문자와 숫자가 같이 혼용될때 사용하기 좋은것같다.

특히나 내가 원하는 string 자료들 비교 할떄 굉장히 유용한것같다. 

201007

해시가 키가 같으면 동시에 값이 들어간다는걸 잊지말자 

#include <string>
#include <vector>
#include <string.h>
#include<unordered_map>
#include<cstring>
#include<iostream>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string,int>ready;
     unordered_map<string,int>finish;
       for(int i=0;i<participant.size();i++){
            ready[participant[i]] +=1;
       }
    
      
       
    
      for(int i=0;i<completion.size();i++){
           ready[completion[i]] -=1;
      }
  
  
    
    for(int i=0;i<participant.size();i++){
        if(ready[participant[i]]==1){
           answer=participant[i];
            i=participant.size();
        }
   }
     
      
  //  answer="";
    return answer;
    
}

#include <unordered_map>

 unordered_map<자료형,자료형> d;
 

ex)

unordered_map<string,int >d;

d["leo"]=1;

cout<<d["leo"]<<endl;
//->1

d["leo"]=6;

cout<<d["leo"]<<endl;
//->6

문제를 잘못 이해 했습니다. 

문제를 천천히 잘 읽도록 하겠습니다.

그런데 문제의도와는 다르지만 비슷하게 단어 별로 압축법을 만들었습니다. 

예를들어

aabbccc

2a2b3c ->7개

abcabcdde

2abcdde->2개

abcdabcdeef

4abcdeef->4개

저는 이런식으로 최대로 압축한 갯수를 구했습니다.

보니까 문제의 의도에서는 압축했을때 문자열이 가장 줄수가 가장 적은 문장을 고르는거였습니다. 

200818

 해결함

https://programmers.co.kr/learn/courses/30/lessons/60057 

해결 정답 200818

#include <string>
#include <vector>
#include<iostream>
#include <string.h>
#include <string>
#include<cstring>
using namespace std;
int Divide(string s,int count){
    vector<char>c;
     vector<char>str;
    string delS=s;
    string strm="";
   int confirm=1;
   int nor=s.length()%count;
    int totalNum=0;
   // cout<<nor;
  
    static int tmpCounts=s.length(); 
    for(int i=0;i<s.length();i=i+count){
        
    for(int j=i;j<count+i;j++){
         if(s[j]!='!'||s[j]!=' '){
             
               
               c.push_back(s[j]); //비교 데이터 push
               totalNum++;
         
         }
      
      
      
    }
       // cout<<",";
   for(int j=i;j<count+i;j++){
           if(s[j+count]!='!'||s[j+count]!=' '){
               str.push_back(s[j+count]);// 원본 데이터 push
         }
   
   }
       
        
        
        bool bCheck=false;
        for(int j=0;j<c.size();j++){
        if(c[j]==str[j]){
             bCheck=true;
          }else{
             bCheck=false;
              break;
          }
         }
        
        if(bCheck){
            confirm++;
             
        }else if(!bCheck){
            if(confirm!=1){
             strm+=to_string(confirm);
             
            }
            
            tmpCounts=tmpCounts-c.size(); //현재 나눠준 범위가 넘어갔는지 체크
                                          //ex) 10을 3으로 나누면 1개가 남아서 한번더 3으로 나눌때
                                          // 333 +1  인데 여기서 c size 는 문자열과 관계없이 쓰레기값이 들어감
                                          //그래서 3 3 3 3으로 들어가 마지막 2자리가 쓰레기값이 들어감 
                                          // 이걸 없애기 위해 전체 길이를 구해서 c가 카운팅 될때 제거해서 음수값이 
                                          // 나오면 범위가 넘어간거여서 strm 값 입력시 3 3 3 1 이 들어가도록 +ns값을 넣어준다
          //  cout<<endl;
            //cout<<"c.size()"<<c.size()<<",";
            cout<<"tmpCounts"<<tmpCounts<<",";
          int ns=0;
          if(tmpCounts<0){
              ns=tmpCounts;
          }  
            
          for(int j=0;j<c.size()/confirm+ns;j++){ // confirm비교데이터의 중복데이터를 제거 하기위해 
                                                   //confirm 즉 현재 나눠지는 갯수로 나눠서 
                                                 //넣어줌 현재 c는 비교 데이터를 가지고 잇어서 중복데이터가 잇음
                
                   strm+=c[j];
                  // tmpCounts++;
                        
                  
                    //cout<<c[j];
                  
               }
          //  cout<<",";
        
          
            confirm=1;
           
            str.clear();//비교 원본 끝난 pop
            c.clear();//비교 끝난 pop
        }
     //   cout<<",";
     
    }
    cout<<endl;
  
    for(int i=s.length()-nor;i<s.length();i++){
       // strm=strm+s[i];
        str.clear();//비교 원본 끝난 pop
        c.clear();//비교 끝난 pop
    }
    
    
 
    
       fflush(stdin);
   
       if(strm!=""){
      //   cout<<"strm:"<<strm;  
        //  cout<<endl;
        
    
        
            }
     // cout<<"strm:"<< strm.length(); 
  tmpCounts=s.length();
   return strm.length();
}

int solution(string s) {
    int answer = 0;
    int min=Divide(s,1);
    for(int i=2;i<s.length()/2+1;i++){
       int tmp;
        tmp=Divide(s,i);
        if(tmp<=min){
            min=tmp;
        }
        
    }
    
    answer=min;
    
  //  if(s.length()%2==1)
        //answer=s.length();
    
    return answer;
}

상당히 어려웟다 그래도 일단 리뷰 하려한다 내코드여서 효율성은 좋은지 잘모르겟다

일단 통과는햇으니 천천히 해보자 

필자는 기본적으로 이걸 나눠서 생각했다

int min=Divide(s,1);
    for(int i=2;i<s.length()/2+1;i++){
       int tmp;
        tmp=Divide(s,i);
        if(tmp<=min){
            min=tmp;
        }
        
    }

그래서 재귀함수를 이용하였고

설명하자면 Divide 함수에 이렇게 나눠서 분배햇다 abcdefg는 예시이다.

for(int i=0;i<s.length();i=i+count)

여기서 count는 내가 나눠준 갯수이다.

즉 한글씩 나누는 거라면 1이 들어가고 두글자씩이면 2가 들어간다. .... 결국 재귀 돌리는 for문의 절반으로 나누는거다

즉 8글자를 나눌때 최종적으로 count는 4로 해서 나누는것 까지한다.

여기선 미리 비교해줄 테이터를 뽑는다 즉 내가 맘대로 다루기 편하도록 만들기 위해서 stack 공간에 미리 나눠둔 글자만 따로 저장한다 예를들어 한글자씩이면 count에 따라 한글자 세글자면 카운터는 세번돈다. 

그럼 세글자가 저장된다.

for(int j=i;j<count+i;j++){
         if(s[j]!='!'||s[j]!=' '){
             
               
               c.push_back(s[j]); //비교 데이터 push
               totalNum++;
         
         }
      
      
      
    }
       // cout<<",";
   for(int j=i;j<count+i;j++){
           if(s[j+count]!='!'||s[j+count]!=' '){
               str.push_back(s[j+count]);// 원본 데이터 push
         }
   
   }
       

  bCheck는 문자열 검사하는 bool이다 즉 true면 confim++( 압축된 갯수) 이고 아니면 false로 반환된다. 

즉 한글자씩이면 true false만 가능하지만 만약 세글자면 true,true ,false면 이미 이 세글자의 비교에선 틀린거여서 더이상 for문이 돌지 않고 같지않는 단어로 판단한다. 

더이상 같지 않는단어와 이미 압축된 갯수가 1이상이면 strm+=to_string(confirm);  숫자를 먼저 string 변환하여 넣어준다

for문은 글자의 크기이다 즉 세글자면 세번 네글자면 네번이 for문으로 돈다

bool bCheck=false;
        for(int j=0;j<c.size();j++){
        if(c[j]==str[j]){
             bCheck=true;
          }else{
             bCheck=false;
              break;
          }
         }
        
        if(bCheck){
            confirm++;
             
        }else if(!bCheck){
            if(confirm!=1){
             strm+=to_string(confirm);
             
            }
            
            tmpCounts=tmpCounts-c.size(); //현재 나눠준 범위가 넘어갔는지 체크
                                          //ex) 10을 3으로 나누면 1개가 남아서 한번더 3으로 나눌때
                                          // 333 +1  인데 여기서 c size 는 문자열과 관계없이 쓰레기값이 들어감
                                          //그래서 3 3 3 3으로 들어가 마지막 2자리가 쓰레기값이 들어감 
                                          // 이걸 없애기 위해 전체 길이를 구해서 c가 카운팅 될때 제거해서 음수값이 
                                          // 나오면 범위가 넘어간거여서 strm 값 입력시 3 3 3 1 이 들어가도록 +ns값을 넣어준다
          //  cout<<endl;
            //cout<<"c.size()"<<c.size()<<",";
            cout<<"tmpCounts"<<tmpCounts<<",";
          int ns=0;
          if(tmpCounts<0){
              ns=tmpCounts;
          }  

그다음 divide 함수 맨 위에 static int tmpCount=s.length(); 가 있는데 

tmpCounts=tmpCounts-c.size();

해준 이유가 글자수 때문이다 예를들어 10글자를 3글자씩 나눠서 압축할때

3 + 3+ 3+1  하고 한글자가 부족하다 이때 문자열은 관계없이 쓰레기 값이 들어가서 

이를 방지하기위해서 tmpCounts 미리 문자열을 받아서 현재 10 -3 =7 다음 7-3=4 다음  4-3=1 다음 1-3=-2 

이런식으로 음수를 측정합니다.

음수가 나왓으면 문자열을 초과한거로 인지합니다.

초과한 ns에 음수 -2를 넣어줍니다.  

원래의  tmpCounts 양수면 ns는 0입니다.

  if(tmpCounts<0){
              ns=tmpCounts;
          }  
            

넣어주 c.size()는 현재 비교 문자 갯수 confirm 압축 갯수입니다. ns는 글자 초과시 현재 길이를 뺴줍니다.

예를들어 1글자 비교만하면되는 3 + 3+ 3+1 맨마지막c.size()는3이고

두글자가 쓰레기값 즉  ex)a, 쓰레기 값  , 쓰레기값 confim 은 당연히 1이고요 그럼 3-2(ns) 1만 나오게 됩니다.

그리고 최종 string strm에 입력 해줍니다.

confim 다시 1로 초기화 str,c도 초기화해줍니다. tmpCounts도 초기화 strm을 길이를 리턴합니다.

for(int j=0;j<c.size()/confirm+ns;j++){ // confirm비교데이터의 중복데이터를 제거 하기위해 
                                                   //confirm 즉 현재 나눠지는 갯수로 나눠서 
                                                 //넣어줌 현재 c는 비교 데이터를 가지고 잇어서 중복데이터가 잇음
                
                   strm+=c[j];
                  // tmpCounts++;
                        
                  
                    //cout<<c[j];
                  
               }
          //  cout<<",";
        
          
            confirm=1;
           
            str.clear();//비교 원본 끝난 pop
            c.clear();//비교 끝난 pop
        }
        
        tmpCounts=s.length();
   return strm.length();

여기서 어려웟던점은 쓰레기값들이 들어갈때 처리하는 방법이었습니다. 

201017

훨씬 간단하게 해결 하였고 

아이디어는 지난번과 비슷함

깊이 우선 탐색과 정렬 그리고 스택을 조합함 

마지막 예외처리가 좀 중요한데 

문자열 비교이기 때문에 하나도 안들어가는 경우랑 

그리고 문자열이 하나만 들어가는 경우이다. 

이것만 주의하면됨 기본적인 아이디어는 지난번과 비슷함 

단지 좀더 효율적으로 잘짠듯하다 

#include <string>
#include <vector>
#include<iostream>
#include <string.h>
#include<cstring>
#include<algorithm>
using namespace std;

int func(string s,int size,int confirm,string totalStr){
    //cout<<endl;
    if(s.size()<size){
        if(s.size()>0){
            for(int i=0;i<s.size();i++){
            totalStr+=s[i];
                }
        }
     //   cout<<size<<":"<<totalStr;
        return totalStr.length();
    }
    
    string str1="";
     string str2="";
   for(int i=0;i<size;i++){
       str1+=s[i];
   }
    
    for(int i=size;i<s.size();i++){
       str2+=s[i];
   }
   // cout<<str1;
    //cout<<endl;
    //cout<<str2;
    //cout<<endl;
    
    
       
    if(strncmp(str1.c_str(),str2.c_str(),size)==0){
        confirm++;
    }else{
        if(confirm>1){
            totalStr+=to_string(confirm);
        }
        totalStr+=str1;
        confirm=1;
        
    }
         
     
    for(int i=0;i<size;i++){
        s.erase(s.begin());
    }
    
  //
    return func(s,size,confirm,totalStr);
}
int solution(string s) {
    int answer = 0;
    int size=s.size();
    vector<int>saveData;
 //   cout<<size;
    string totalStr="";
    if(s.size()==0){
        return 0;
    }
    if(s.size()==1){
        return 1;
    }
    for(int i=0;i<size/2;i++){
        
        int tmpStr=func(s,i+1,1,totalStr);
        saveData.push_back(tmpStr);
            cout<<endl;
       // cout<<"=======================";
        // cout<<endl;
         //cout<<"=======================";
          //  cout<<endl;
    }
    sort(saveData.begin(),saveData.end());
    //cout<<saveData[0];
    answer=saveData[0];
    
    return answer;
}

삼각 함수  :

삼각함수 항등식 :

2019/09/02 - [C++(Math&알고리즘)] - Rotation Matrix

구면 좌표계 :

그림을 보시면서 천천히 따라 가시면 될것 같습니다 .

먼저 OA 직선을 구하려고 할떄 OP의 직선과 파이를 알고 있다면 

$$OA=OP*\cos(\pi/2-\phi)$$

여기서 삼각함수 항등식에 의하면 

$$OA=OP*\sin(\phi)$$

다음은 P의 좌표인 (x,y,z)를 구해보겠습니다.

$$x=OA*\cos(\theta)$$

왜냐하면 삼각형을 떼서 보면

위의 그림과 같다. 그렇다면 코사인세타는

$$OX/OA=\cos(\theta)$$

이다

그래서

$$x=OA*\cos(\theta)$$

$$OX/OA=\cos(\theta)$$

$$OA*OX/OA$$

입니다.

그러면 

$$OX$$

가 남습니다.

즉  x좌표는 

$$x=OA*\cos(\theta)$$

입니다.

그렇다면

위에서 OA 값은

$$OA=OP*\sin(\phi)$$

였습니다. 

그걸 변경을 하면 

$$x=OA*\cos(\theta)$$

$$x=OP*\sin(\phi)\cos(\theta)$$

이런식으로 변경이 됩니다. 

다른 좌표들도 마찬가지로 

정리해보면 

x좌표 

$$x=OA*\cos(\theta)$$

$$x=OP*\sin(\phi)\cos(\theta)$$

y좌표는 

$$y=OA*\cos(\pi/2-\theta)$$

$$y=OP*\sin(\phi)*cos(\pi/2-\theta)$$

$$y=OP*\sin(\phi)\sin(\theta)$$

 z 좌표는 

$$z=OP*\sin(\pi/2-\phi)$$

$$z=OP*\cos(\phi)$$

이다.

그렇다면 구의

$$x^2+y^2+z^2=OP^2$$

를 증명하자면 

위에 구한 좌표값을 전부 넣어보니다.

$$x^2+y^2+z^2=OP^2$$

$$x^2+y^2+z^2=(OP*\sin(\phi)\cos(\theta))^2+$$

$$(OP*\sin(\phi)\sin(\theta))^2+(OP*\cos(\phi))^2$$

식을 풀면 

$$(OP^2*\sin(\phi)^2*(\cos(\theta)^2+\sin(\theta)^2)$$

$$+OP^2\cos(\phi))^2$$

$$\cos(\theta)^2+\sin(\theta)^2=1$$

그러므로

$$OP^2*\sin(\phi)^2*1+OP^2\cos(\phi))^2$$

가 됩니다. 

정리하면

$$OP^2*\sin(\phi)^2+OP^2\cos(\phi)^2$$

다시한번 

$$OP^2$$

으로 묶으면

$$OP^2*(\sin(\phi)^2+cos(\phi)^2)$$

됩니다.

그러면 마찬가지로 1이 되므로 

$$OP^2*1$$입니다. 

즉

$$x^2+y^2+z^2=OP^2$$

입니다.

그렇다면 각도의 값들은 어떻게 구할까요 

위의 그림의 각도인

$$\theta , \phi$$

구해보겠습니다.

$$\phi=\arccos(z/OP)$$

$$\theta=\arctan(y/x)$$

인데 이를 증명해보이겠습니다.

먼저 

$$z=OP*\cos(\phi)$$

이용하여  구해보겠습니다.

$$z/OP=cos(\phi)$$

$$\arccos(x)=cos (y)$$

$$\phi=acrccos(z/OP)$$

다음에는 

$$\tan \theta=(y/x)$$

$$\arctan (x) =\tan (y)$$

$$\theta=\arctan (y/x)$$

이다