개발자 김수진

[문제]

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

[풀이]

input으로 숫자 number와 number에서 제외할 숫자의 개수인 k가 주어진다.

number에서 k개의 숫자를 제거하여 만들 수 있는 최댓 값을 구하면 된다.

처음에는 DFS를 사용하여 모든 경우에 대해 다 확인해봤는데 생각해보니 number의 길이가 1부터 1,000,000까지이다.

그래서 다른 방법을 생각해보니 number의 시작부터 큰 수를 골라 총 number.size()-k의 숫자를 골라서 answer로 return 하면 된다. 

1. number의 처음부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다.

2. 선택한 수의 다음 index부터 'k+선택된 숫자의 수'까지 중에서 가장 큰 수를 선택한다.

위의 과정을 'number.size() - k' 번 반복한다. 

예를 들어  number= "1234568"이고 k=3인 경우 

총 4개의 숫자를 선택해야 하므로 , 0~3+0 범위 내에서 가장 큰 수를 택해야 된다. 

범위 내에서 가장 큰 수 4를 택하고 , 4~4+1 범위 내에서 가장 큰 수를 택해야 된다. 

이런 식으로 반복하여 4568이라는 가장 큰 수를 구할 수 있게 된다.

[코드]

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    int tmp = number.size()-k;
    int idx =0;
    int tmp_idx=0;
    
    for(int i=0;i<tmp; i++)
    {
        int _max = number[idx]-'0';
        tmp_idx = idx;
        
        for(int j=idx; j<=k+i ; j++)
        {
            if(number[j]-'0' > _max ){
                _max =number[j]-'0'; 
                tmp_idx = j;
            }  
        }
        idx = tmp_idx+1;
        answer += to_string(_max);       
    }
    return answer;
}

[문제]

www.acmicpc.net/problem/2206

[풀이]

NXM으로 표현되는 맵이 문제 입력으로 주어진다.

맵에는 벽이 존재하는데 최대 한번 벽을 부수고 이동할 수 있다.

이 때 시작점에서 (N,M)까지의 최단 거리를 구하면 된다.

최단거리를 구하는 문제라서 BFS를 사용하고 pos 구조체에 crash 변수를 추가하여 이전 경로에서 벽을 부수고 왔는지를 확인했다.

원래 visited 배열은 2차원 배열로 아래와 같이 선언했었다.

int visited[MAX][MAX]

하지만 해당 위치를 이미 방문했더라도 벽을 부수고 왔는지 아닌지에 따라 결과가 달라지므로

벽을 부수고 왔는지 아닌지에 대해서도 확인할 수 있도록 아래와 같이 수정했다.

int visited[MAX][MAX][2]

[코드]

#include <iostream>
#include <queue>

#define MAX 1001

using namespace std;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int N,M;
int map[MAX][MAX]={0,};
int visited[MAX][MAX][2]={0,};

struct pos{
    int x,y;
    bool crash;
};

int BFS()
{
    queue <pos> q;
    q.push({1,1,false});
    visited[1][1][0] =1;
    
    while(!q.empty()){
        
        int x = q.front().x;
        int y = q.front().y;
        bool check = q.front().crash;

        if(x == N && y == M)    return visited[x][y][check];
        
        q.pop();
        
        for(int i=0;i<4;i++){
            
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx<1 || ny <1 || nx >  N || ny > M )  continue;
            if(map[nx][ny] == 1 && check)  continue;
            
            bool flag = false;
            if(map[nx][ny]==1)  flag = true;
            else    flag = check;
            
            if(visited[nx][ny][flag]!=0)    continue;
            
            q.push({nx,ny,flag});
            visited[nx][ny][flag]=visited[x][y][check]+1;
            
        }
    }
    return -1;
}

int main(void)
{
    scanf("%d %d",&N,&M);
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            scanf("%1d",&map[i][j]);
        }
    }
    
    cout << BFS();
}

[문제]

www.acmicpc.net/problem/2193

[풀이]

N이 1인 경우부터 모든 경우의 수를 구하다 보면 규칙을 금방 발견할 수 있다.

규칙을 통해 아래와 같이 점화식을 세워서 DP를 사용해 풀었다.

        DP[i] = DP[i-1]+DP[i-2];

[코드]

시간 : 0ms

#include <iostream>
#define MAX 90

using namespace std;

long long DP[MAX]={0,};
int N;

int main(void)
{
    cin >> N;
    DP[1] = 1;
    DP[2] = 1;
    
    for(int i=3;i<=N;i++)
    {
        DP[i] = DP[i-1]+DP[i-2];
    }
    cout << DP[N];
    return 0;
    
}

[문제]

www.acmicpc.net/problem/2096

[풀이]

DP를 사용해서 이전 경로까지의 최대, 최솟값을 저장해놓고

이전 경로와 현재 위치의 값을 더해서 최대, 최솟값을 구했다.

처음에는 N의 범위가 N(1 ≤ N ≤ 100,000)이므로 DP배열을 [100001][3]의 크기고 잡고 시작했는데 메모리 초과가 나왔다.

생각해보니 문제 조건에서 주어진 메모리 제한은 4MB인데 [100001][3]의 크기로 잡고 풀면

min, max 배열이 2개 이므로 4MB를 넘어버린다.

생각을 해보니 DP의 값을 계산할 때마다 필요한 값은 현재 위치의 값과 이전 위치의 값이므로

DP 배열의 크기를  [2][3]으로 바꾸고 아래와 같이 풀었다.

찾아보니 이러한 기법을 '슬라이딩 윈도우'라고 하는 것 같다.

[코드]

시간 : 24ms

#include <iostream>
#define _max(a,b) ((a) > (b) ? (a) : (b))
#define _min(a,b) ((a) < (b) ? (a) : (b))

using namespace std;

int N;
int map[3];
int DP_max[2][3]={0,};
int DP_min[2][3]={0,};

int main(void)
{
    scanf("%d",&N);
    
    for(int i=1;i<=N;i++)
    {
        scanf("%d %d %d",&map[0],&map[1],&map[2]);

        DP_max[1][0]=map[0] + _max(DP_max[0][0],DP_max[0][1]);
        DP_max[1][1]=map[1] + _max(DP_max[0][0],_max(DP_max[0][1],DP_max[0][2]));
        DP_max[1][2]=map[2] + _max(DP_max[0][1],DP_max[0][2]);
        
        DP_max[0][0]= DP_max[1][0];
        DP_max[0][1]= DP_max[1][1];
        DP_max[0][2]= DP_max[1][2];

        DP_min[1][0]=map[0] + _min(DP_min[0][0],DP_min[0][1]);
        DP_min[1][1]=map[1] + _min(DP_min[0][0],_min(DP_min[0][1],DP_min[0][2]));
        DP_min[1][2]=map[2] + _min(DP_min[0][1],DP_min[0][2]);

        DP_min[0][0]= DP_min[1][0];
        DP_min[0][1]= DP_min[1][1];
        DP_min[0][2]= DP_min[1][2];
    }
    
    cout << _max(DP_max[1][0],_max(DP_max[1][1],DP_max[1][2])) << " "<<_min(DP_min[1][0],_min(DP_min[1][1],DP_min[1][2]));
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/1946

[풀이]

처음에는 2중 for문 사용해서 하나를 기준으로 현재 지원자를 기준으로 서류 점수가 더 우수한 지원자가 있다면 면접 점수를 비교하는 방식으로 풀었다.

모든 면접자에 대해서 한번씩 모두 비교해야 하므로 당연히 시간초과가 나왔다.

따라서 두번째에는 서류 점수를 기준으로 오름차순으로 정렬하고 한명의 지원자를 기준으로 앞에 있는 지원자보다 면접 점수도 낮다면 제외하였다. 이렇게 풀었는데도 시간초과가 발생했다.

마지막으로는 서류 점수를 기준으로 정렬하고 현재 지원자보다 서류 점수가 우수한 지원자들 중에서 가장 낮은 면접 점수를 임의의 tmp 변수에 저장해두어 반복문을 한번만 사용해서 풀 수 있었다.

다행히 시간초과가 발생하지 않았다. 

[코드]

시간 : 544ms 

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

#define MAX  100000

using namespace std;

int main(void)
{
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int T,N;
    
    cin >> T ;
    
    for(int i=0;i<T;i++){
        
        int res =1;
        
        vector <pair<int,int>> v;
        
        cin >> N;
        
        for(int j=0;j<N;j++){
            
            int a,b;
            cin >> a >> b;
            v.push_back({a,b});
        }
        
        sort(v.begin(),v.end());
        int tmp = v[0].second;
        
        for(int k=1;k<N;k++){
            if(v[k].second < tmp )  res++;
            if(tmp > v[k].second)   tmp = v[k].second;
        }
        cout << res <<"\n";
    }
    return 0;
}

[문제]

www.acmicpc.net/problem/1197

[풀이]

MST의 가중치를 구하는 문제로 Kruskal 알고리즘을 사용해서 풀었다.

정점간의 연결 정보를 입력 받고 벡터에 저장했다.

가중치를 기준으로 벡터를 정렬하고 , 가중치가 작은 것부터 Union-Find를 사용해 묶어줬다.

Union을 하기 전에 Find를 통해 부모가 같은지 미리 확인한다.

( 부모가 같은 상태에서 union을 해버리면 사이클이 발생하므로 )

[코드]

시간 : 48ms

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

#define MAX 10000

using namespace std;

int parent[MAX]={0,};

int Find(int idx)
{
    if(idx == parent[idx])  return idx;
    else{
        parent[idx] = Find(parent[idx]);
        return parent[idx];
    }
}

void Union(int idx1, int idx2)
{
    idx1 = Find(idx1);
    idx2= Find(idx2);
    if(idx1  != idx2)   parent[idx2] = idx1;
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E;
    cin >> V >> E;
    
    vector <pair<int, pair<int, int>>> v(E);

    for(int i=1;i<=V;i++)   parent[i] = i;
    
    for(int i=0;i<E;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        
        v.push_back(make_pair(c, make_pair(a,b)));
    }
    
    sort(v.begin(),v.end());
    int ans=0;
    
    for(int i=0;i<v.size();i++){
        
        int tmp1 = v[i].second.first;
        int tmp2 = v[i].second.second;
        
        if(Find(tmp1) != Find(tmp2)){
            Union(tmp1,tmp2);
            ans+= v[i].first;
        }
    }
    
    cout << ans;
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/3020

[풀이]

처음에는 반복문을 사용해서 풀려고 했지만 N,H 범위를 생각해서 따지면

반복문 10억번에 1초라고 생각하면 20,000 * 50,000 이므로 1초를 훨씬 넘길 것이다. 

따라서 이분 탐색 방법으로 풀어야겠다고 생각했다.

 lower_bound는 x 이상인 값이 처음 나오는 index를 return하고

upper_bound는 x 이하인 값이 처음 나오는 index를 return 하므로 

전체 갯수에서 return 된 값을 빼면 파괴하는 장애물의 수를 구할 수 있다.

[코드]

시간 : 60ms

( 이분 탐색 직접 구현해서 다시  풀어봐야겠다.)

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

#define MAX 100000

using namespace std;

int N,H;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int res = 1e9;
    cin >> N >> H;
    
    vector <int> up(N/2);
    vector <int> down(N/2);
    
    for(int i=0;i<N/2;i++)  cin >> down[i]>> up[i];

    int total=1;
       
    sort(down.begin(),down.end());
    sort(up.begin(),up.end());
    
    for(int i=1;i<=H;i++)
    {
        int cnt = down.size() - (lower_bound(down.begin(), down.end(),i)-down.begin());
        cnt += up.size() - (upper_bound(up.begin(), up.end(),H-i)-up.begin());
        
        
        if(res == cnt ) total++;
        else if(res > cnt ){
            res = cnt;
            total=1;
        }

    }

    cout << res << " " << total;
    return 0;
    
}

[문제]

www.acmicpc.net/problem/11660

[풀이]

표의 크기 N과 합을 구해야 하는 횟수 M이 입력으로 주어진다.

그 다음으로 표의 값이 주어지고 구간의 시작 좌표, 마지막 좌표가 주어진다.

이 구간의 합을 구해서 출력하면 된다.

처음에는 이중 for문을 사용해서 시작점인 (x1,y1)부터 구간의 마지막 부분인 (x2,y2) 까지의 합을 구했다.

당연히 시간초과가 나왔고 다른 방법을 찾아봤다.

찾아보니 DP를 사용해서 구간 합을 구할 수 있었다. 

(1,1)부터 (x,y)까지의 구간 합을 배열 DP[x][y]에 저장한다.

DP[N][N]까지 구하고 M번만큼 반복문 하여 각 구간에 대해 구간 합을 출력하면 된다.

위의 그림에서 우리가 구하고 싶은 구간 합의 영역이 4번 영역이라면

4번 영역의 구간 합은 4 = 3+2-1이 된다.

각 영역의 오른쪽 아래 부분이 (그림 2에서 진하게 표시된 부분)

해당 영역의 구간 합이므로 아래와 같이 구할 수 있다.

 DP[x2][y2]-DP[x2][y1-1]-DP[x1-1][y2] + DP[x1-1][y1-1]

[코드]

시간 : 228 ms

#include <iostream>
#define MAX 1025


int map[MAX][MAX]={0,};
long long int DP[MAX][MAX]={0,};

int N,M;


int main(void)
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d",&map[i][j]);
            DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + map[i][j];
        }
    }
    
    DP[1][1]=map[1][1];
     
    for(int i=0;i<M;i++)    {
        
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        std::cout << DP[x2][y2]-DP[x2][y1-1]-DP[x1-1][y2] + DP[x1-1][y1-1] << "\n";
    }
    
    return 0;
    
}