코딩생존기

초기 아이디어

각 행에서 최대값을 구하고 그 최대값의 다음행의 값을 0으로 바꿔주면서 최댓값들을 저장하는 방식

=> 코드 구현이 너무 길어진다.

=>DP로 구현하는게 좋다는 힌트를 보고 고민을 해보다가 DP 공부를 할겸 코드분석을 해서 풀어보았다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//DP=>초기값 설정해주고 2,3번째를 어떻게 구할지 생각해보면 된다.
//DP=>모든 경우의 수를 만들어서 사용하는 것
int solution(vector<vector<int> > land)
{
    int answer = 0;
    vector<vector<int>> dp(land.size(), vector<int>(4));     //땅의 사이즈만큼 미리 초기화해주기

    for (int i = 0; i < 4; i++) {
        dp[0][i] = land[0][i];            //초기값은 그대로 => DP 초기값설정
    }

    for (int i = 1; i < land.size(); i++) {
        for (int j = 0; j < 4; j++) {               //2차원 땅배열 순회
            int max = 0;
            for (int k = 0; k < 4; k++) {
                if (k == j) continue;
                if (max < dp[i - 1][k])
                    max = dp[i - 1][k];
            }
            dp[i][j] = land[i][j] + max;        //땅배열과 같은크기의 DP배열을 하나하나 값을 완성시키기
        }
    }

    answer = *max_element(dp.back().begin(), dp.back().end());     //마지막행에 제일큰게 정답
    return answer;
}

주차요금을 계산하는 문제

※핵심

기본시간보다 낮을 떄는 기본요금만

기본시간보다 길어질 때는 기본요금 + 초과한 시간= 단위시간 마다 단위요금 -> 초과시간/단위요금->올림(ceil)하기 

문자열처리 -> sstream

  stringstream ss;                    //빈칸을 경계로 string 나눔
    for(auto record: records){
        ss.str(record);             //records에서 record string 형태로 가져오기
        string time,number,status;  //record string에서 나눠줄 변수들 
        ss>>time>>number>>status;
        
        parks[number].push_back(time);
        ss.clear();
    }

빈칸을 기준으로 문자열 처리하는 공식같은 코드이다. 꼭 기억해두는게 좋을 것같다.

#include <string>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
using namespace std;
int diff_time(string start,string end){
    int h1=stoi(start.substr(0,2));
    int m1=stoi(start.substr(3,2));
    int h2=stoi(end.substr(0,2));
    int m2=stoi(end.substr(3,2));
    
    int diff=(h2-h1)*60+(m2-m1);
    
    return diff;
}
vector<int> solution(vector<int> fees, vector<string> records) {
    vector<int> answer;
    map<string, vector<string>> parks;
    
    stringstream ss;                    //빈칸을 경계로 string 나눔
    for(auto record: records){
        ss.str(record);             //records에서 record string 형태로 가져오기
        string time,number,status;  //record string에서 나눠줄 변수들 
        ss>>time>>number>>status;
        
        parks[number].push_back(time);
        ss.clear();
    }
    
    for(auto it: parks){
        if(it.second.size()&1){         //주차내역 개수가 홀수 일때
            it.second.push_back("23:59");
        }
        
        vector<string>info = it.second;
        int total=0;
         for(int i=0; i<info.size()-1; i+=2) {
            total += diff_time(info[i], info[i+1]);
        }
        
        int price=fees[1];
        if(total>fees[0]){
            price+=ceil((total-fees[0]) / (double)fees[2]) * fees[3];
        }
        answer.push_back(price);
    }
    
    return answer;
}

힙구조를 사용하여 모든 음식의 스코빌 지수를 K 이상으로 만드는 것

힙구조는 priority_queue 를 사용하여 구현

※priority_queue에서 정렬를 부여해두려면 priority_queue<자료형, 구현체, 비교연산자> 로 우선순위 큐를 선언하면 된다. 

지금은 오름차순으로 정렬해야하니 priority_queue<int,vector<int>,greater<int>> pq 로 선언해 두었다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;          //정렬 조건 오름차순으로
    
    for(int i=0;i<scoville.size();i++){
        pq.push(scoville[i]);
    }
    
    while(pq.size()>=2&&pq.top()<K){
        int first=pq.top();
        pq.pop();
        
       int second=pq.top();
        pq.pop();
        
        answer++;
        pq.push(first+second*2);
    }
    
    if(!pq.empty()&&pq.top()<K) return -1;
    
    return answer;
}

n진법으로 한글자 씩 말하기 게임에서  튜브의 순서에서 말해야하는 숫자를 정답으로 내면된다.

1. 튜브의  순서에서 말해야할 숫자는 p-1 번째  부터 m개를 더해가며 반복해주면된다.

2. n진법을 총 문자열에 더해주는데 이때 중간에 stack에 push 하고 top을 pop하는 과정에서 숫자에서 10이 넘는 경우 A~F로 변환이 가능하도록 한다. 

3. 사람들이 말하는 숫자의 최대 개수는 t*m 이다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

string makestr(int n,int max){          //n진수, max는 길이 최대값 => t*m 
    string str="";
    stack<int> s;               //중간에 수를 저장할 스택변수
    
    for(int i=0;str.length()<=max;i++){
        int x=i;
        
        while(1){
            s.push(x%n);
            x/=n;
            
            if(x==0) break;
        }
        
        while(!s.empty()){
            if(s.top()<10){
                str+=to_string(s.top());
            }else{
                str+=(char)(65+s.top()-10);     //10보다 크다면 A~F로 변환
            }
            s.pop();
        }
    }
    
    return str;
    
}

string solution(int n, int t, int m, int p) {
    string answer = "";
    
    string str=makestr(n,m*t);
    
    for(int i=p-1;t>0;i+=m){
        answer+=str[i];
        t--;
    }
    return answer;
}

단어 배열에서 시작단어와 한 글자만 다른것을 찾아서 변환하고 최종단어까지 도달가능할때까지의 단계를 구하는 문제 

한글자만 다른 것을 찾아가는 과정을 반복하는 것이라 DFS를 생각해보았다. 이 과정에서 한글자만 다른 것을 찾는게 함수 내부에 구현하기보다 따로 함수를 만들어주는 게 편해서 그렇게 해보았다.

그리고 가질 수 있는 최대의 단어개수보다 시도횟수가 많으면 안되고 다 순회했을 때도 답이 없을 경우엔 0을 return하게 해준다.

#include <string>
#include <vector>
#include <algorithm>
int answer = 50;
bool visited[50];

using namespace std;

bool diff_st(string a, string b) {            //두 문자열 비교해서 다른 문자가 1개인지 판별
    int diff = 0;

    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) {
            diff++;
        }
    }

    if (diff == 1) {
        return true;
    }
    else return false;
}
void dfs(string begin, string target, vector<string> words, int cnt) {
    if (answer <= cnt) {
        return;
    }

    if (begin == target) {
        answer = min(answer, cnt);                 //answer은 최대길이 값보다 작은 것 중에 최소값
        return;
    }


    for (int i = 0; i < words.size(); i++) {
        if (diff_st(begin, words[i]) && !visited[i]) {                //다른 문자가 한개라면
            visited[i] = true;
            dfs(words[i], target, words, cnt + 1);
            visited[i] = false;
        }
    }

    return;
}
int solution(string begin, string target, vector<string> words) {

    dfs(begin, target, words, 0);

    if (answer == 50) {             //만약 모두를 탐색했는데도 target에 도달하지 못했을 경우
        return 0;
    }
    return answer;
}

주어진 항공권을 모두 사용해서 여행경로를 만드는 문제 =>

DFS를 통해 그래프 처럼 그려가며 갈 수 있는 모든 경로를 방문하면서 정답에 추가해주면 될 것 같다.

다시 확인하고 넘어가는 DFS => 재귀함수로 구현 visited 를 사용하여 방문한곳 체크해주기!

그리고 알파벳 순서로 정렬-> 기본 sort사용 

기존코드(테스트 1,2번 실패)

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[10001]={0};
vector<string> answer;
void dfs(vector<vector<string>> tickets,string ap){		//항공권과 현재공항
    answer.push_back(ap);			
    
    for(int i=0;i<tickets.size();i++){
        if(visited[i]) continue;			//방문한곳이면 continue;
        if(tickets[i][0]==ap){				//방문하지않은곳 중에
            visited[i]=true;				//방문처리				
            dfs(tickets,tickets[i][1]);		//연결된 다음공항으로 
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(),tickets.end());
    dfs(tickets,"ICN");				//시작은 언제나 ICN
    return answer;
}

1,2번이 실패했는데 

반례를 보니 

반례
    `입력`
    [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
    `정답`
    ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]

가다가 모든 항공권을 다 사용하지 않았는데 dfs함수가 끝나버리는 경우가 있어서 백트레킹이 필요하다고 한다.

백트레킹은 pop_back과 방문처리하는 배열을 통해 다시 할 수  있다.

고친 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool visited[10001] = { 0 };
bool isall = false;			//항공권 다 사용했는 지 확인할 변수 
int ticketcnt = 0;			//항공권 사용한 횟수
vector<string> answer;
void dfs(vector<vector<string>> tickets, string ap) { //항공권, 현재 공항
    answer.push_back(ap);

    if (ticketcnt == tickets.size()) isall = true;          //항공권을 다 사용했다면
    for (int i = 0; i < tickets.size(); i++) {
        if (visited[i]) continue;                   //방문한곳이면 continue;
        if (tickets[i][0] == ap) {                  //방문하지않은곳 중에
            visited[i] = true;                      //방문처리
            ticketcnt++;                            //항공권사용수 증가
            dfs(tickets, tickets[i][1]);
            if (!isall) {                               //항공권 다 사용하지않았다면
                answer.pop_back();                      //백트레킹
                visited[i] = false;
            }
        }
    }
}

vector<string> solution(vector<vector<string>> tickets) {

    sort(tickets.begin(), tickets.end());
    dfs(tickets, "ICN");                //시작은 언제나 ICN
    return answer;
}

연결된 컴퓨터끼리는 하나의 네트워크이고 연결되지않은 컴퓨터 하나씩 네트워크가 추가된다.

즉 연결된 컴퓨터를 세면 된다 => DFS

#include <string>
#include <vector>

using namespace std;
bool visited[201]={0};
void dfs(int n, vector<vector<int>> computers,int cur){     //연결된함수 모두 방문처리 => 재귀함수로
    visited[cur]=true;
    //재귀함수
    for(int i=0;i<n;i++){               //연결된 함수 찾으려고 전체 순회
        if(!visited[i]&&computers[cur][i]==1){          //연결되고 방문x일때
            dfs(n,computers,i);
        }
    }
}


int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    //연결된 네트워크를 확인해야함. => dfs 로 
    for(int i=0;i<n;i++){
        if(!visited[i]){
            dfs(n,computers,i);
            answer++;
        }
    }
    return answer;
}

전형적인 BFS문제

BFS 문제를 풀어보면서 이런 맵 탐색이나 미로 탐색에는 큐를 써서 많이 푸는 것 같다.

1. 처음으로 방문처리와 거리값을 체크할 배열을 0으로 초기화해준다. (n,m은 각각 1 이상 100이하의 자연수여서 최대101개가 들어갈 수 있게 해준다.)

2. 반시계방향, 시계방향으로 돌면서 맵을 탐색할 때 쓸 방향 배열(x,y)을 선언해준다. 

3. 초기값을 큐에 넣어주고 while문과  for문을 통해 맵을 탐색하고 위치에서 이상이 있을때(지도사이즈 이상의 위치, 방문한 곳, 벽인지 체크) continue 해주고 각 위치에 대한 값을 넣어준다.

#include<vector>
#include<queue>
using namespace std;
int dx[4]={1,0,-1,0};       //반시계방향 아래부터
int dy[4]={0,1,0,-1};
int width,height;
bool visited[101][101]={0};
int bfs[101][101]={0};

queue<pair<int,int>> q;
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    width=maps[0].size();           //가로
    height=maps.size();              //세로
    
    q.push({0,0});              //시작
    visited[0][0]=1;
    bfs[0][0]=1;
    
    while(!q.empty()){
        
        int curX=q.front().first;
        int curY=q.front().second;
        
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx=curX+dx[i];
            int ny=curY+dy[i];
            
            if(nx>=height||nx<0||ny>=width||ny<0) continue;     //사이즈 이상
            
            if(visited[nx][ny]) continue;           //방문여부 체크
                
            if(maps[nx][ny]==0) continue;              //벽인지 체크
            
            visited[nx][ny]=1;
            q.push({nx,ny});
            bfs[nx][ny]=bfs[curX][curY]+1;
        }
    }
    
    if(!bfs[height-1][width-1]) answer=-1;
    else answer=bfs[height-1][width-1];
    
    return answer;
}

문제 설명만을 보고선 어떻게 풀어야할지 감이 잘 안왔는데 다른 사람의 풀이 중 DFS를 활용하여 풀면 된다는 문제 설명을 보고 DFS 문제 연습을 하는 겸 주석을 넣으면서 풀어 보았다.

answer은 전역 변수를 통해 함수에서 값을 추가될때마다 반영되도록 하였다.

지금까지 생각해봤을 때 DFS 는 재귀함수로 구현하는 데 이렇게 구현할 알고리즘을 짜는 능력이 필요하다..

#include <string>
#include <vector>

using namespace std;
int answer = 0;

 void dfs_target(vector<int> numbers, int target,int sum,int index){        //dfs=> 재귀함수로 구현, 종료조건 필요
     //종료조건
    if(index==numbers.size()){
        if(sum==target){
            answer++;
        }
        return ;
    }
    //재귀함수
     dfs_target(numbers,target,sum+numbers[index],index+1);             //양수일때
     dfs_target(numbers,target,sum-numbers[index],index+1);             //음수일때
 }

int solution(vector<int> numbers, int target) {
    
    dfs_target(numbers,target,0,0);         //시작값 index,sum 0부터
    return answer;
}

초기생각

문제의 설명을 읽어보면 A가 1이고 Z가 26이라 Map을 사용하여 1부터 26까지 사전으로 등록해주는게 좋을 것 같다고 생각하였다. 

그리고 LZW압축 과정이 처음에는 이해가 잘 되지않았는데 천천히 읽어보니  문자열에서 사전에 등록돼있는 것 중 가장  긴 문자열을 찾은 후 그 문자열에 맞는 사전에서의 번호를 answer에 추가하고 사전에 없는 단어를 추가해주면 되는 것이었다.

근데 이렇게 생각하니 사전에 등록돼있는 것 중 가장 긴 문자열을 어떻게 찾아야하나 고민을 하다가 사전에 등록되어 있는 것을 찾을 생각보다 사전에 등록되어 있지않은 걸 찾으면 그 전에까지는 등록된 것이니 그 부분만 잘라서 쓰면 되겠다라는 해답이 나왔다.

● 사전에 등록하는 부분에서는 num이라는 전역변수를 사용하여 뒤에 수도 추가될 수 있게 하였다.

알고리즘은 생각하면서 하나의 방법도 좋지만 여러 방법을 생각해보는게 좋을 것 같다.

#include <string>
#include <vector>
#include <map>
using namespace std;
map<string, int> dic;
int num = 1;
vector<int> solution(string msg) {
    vector<int> answer;
    //A ~ Z 까지 사전에 등록
    for (char c = 'A'; c <= 'Z'; c++) {
        string s = "";
        s += c;
        dic[s] = num++;
    }
    //사전추가 과정
    string sum="";
    for(int i=0;i<msg.length();i++){
        sum+=msg[i];
        if(dic[sum]==0){            //만약 사전에 등록되지않은 단어라면
            dic[sum]=num++;             
            sum=sum.substr(0,sum.length()-1);           //사전에 등록되지않은거 바로 앞에까지는 등록된 단어
            answer.push_back(dic[sum]);                 //등록된 단어의 번호 push_back
            sum="";                                     //단어 초기화
            i--;                                        //사전에 등록되지 않은 수의 인덱스에서 시작 
        }
    }
    answer.push_back(dic[sum]);             //마지막 단어
    
    return answer;
}