개발자 김수진

[문제]

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;
    
}

[문제]

www.acmicpc.net/problem/2252

[코드]

N 명의 학생들을 M번 비교하고 그 결과가 입력으로 주어진다.

이를 통해 학생들을 줄을 세우는 결과를 출력하면 된다.

학생들의 키가 모두 주어진 것이 아니고 일부만 주어졌으므로 '위상 정렬'을 사용해서 풀었다.

Degree에 각 노드에 대한 연결 차수를 저장하고

연결 차수가 0인 노드만 queue에 push 하여 순서대로 출력했다.

[풀이]

시간 : 44ms

#include <iostream>
#include <queue>
#include <vector>

#define MAX 32001

using namespace std;

int N,M;
int Degree[MAX]={0,};

vector <int> v[MAX];


int main(void)
{
    queue <int> q;
    
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++)
    {
        int x1,x2;
        scanf("%d %d",&x1,&x2);
        
        Degree[x2]++;
        v[x1].push_back(x2);
    }
    
    for(int i=1;i<=N;i++)    if(Degree[i]==0)    q.push(i);
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        printf("%d ",x);
        
        for(int i=0;i<v[x].size();i++){
            int tmp = v[x][i];
            Degree[tmp]--;
            if(Degree[tmp]==0)  q.push(tmp);
        }
    }
    return 0;
}

[문제]

programmers.co.kr/learn/courses/30/lessons/49994#

[풀이]

입력으로 움직이는 방향이 주어지고 이에 알맞게 움직이면 된다.

걸어간 길의 길이를 출력하면 된다.

단, 이미 지나왔던 경로는 포함하지 않는다.

또한 범위를 벗어나는 경우 움직이지 않는다.

따라서 좌표와 방향을 가지고 visited 배열을 사용해 이미 방문한 길은 포함하지 않도록 하였다.

문제에서 범위가 -5부터 5까지인데 배열은 index가 0부터 가능하므로

(0,0) ~ (10, 10)으로 변경했다.

[코드]

#include <string>

#define MAX 11

using namespace std;

int solution(string dirs) {
    
    int answer = 0;
    int visited[MAX][MAX][4]={0,};
    
    int x=5;
    int y=5;

    int _size = dirs.size();
    
    for(int i=0;i<_size;i++)
    {
        int dir=0;
        int nx=x;
        int ny=y;
        
        switch(dirs[i])
        {
            case 'U':
                ny +=1;
                dir =0;
                break;
            case 'D':
                ny -=1;
                dir=1;
                break;
            case 'R':
                nx +=1;
                dir=2;
                break;
            case 'L':
                nx -=1;
                dir=3;
                break;
        }
        if(nx<0 || ny<0 || nx >10 || ny>10) continue;
        
        if(visited[x][y][dir]==0){
            answer+=1;
            visited[x][y][dir] =1;
            
            if(dir==0)  dir=1;
            else if (dir==1)    dir=0;
            else if(dir==2) dir=3;
            else if(dir==3) dir=2;
            
            visited[nx][ny][dir]=1;
        }
        x=nx;
        y=ny;
    }
    return answer;
}

[문제]

www.acmicpc.net/problem/1463

[풀이]

DP를 사용해서 2부터 N까지의 1을 만들 때 필요한 연산의 최소 횟수를 구했다.

bottom-up 방식을 사용해 2부터 N까지의 최솟 값을 구했다.

연산은 아래와 같이 3가지 연산이 있다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

따라서 1을 빼는 연산은 모든 숫자에 대해 가능하므로 구하고 

X가 2로 나눠지는 경우, 3으로 나눠지는 경우에는 이에 대한 경우도 구해서 최솟 값을 구했다.

[코드]

시간 : 4ms

#include <stdio.h>
#define MAX 1000001


int MIN(int a, int b)
{
    if(a>b )    return b;
    else    return a;
}

int main(void)
{
    int N;
    int DP[MAX]={0,};
    
    scanf("%d",&N);
    
    for(int i=2;i<=N;i++)
    {
        DP[i] = DP[i-1]+1;
        if(i%2 == 0)    DP[i] = MIN(DP[i], DP[i/2]+1);
        if(i%3 == 0)    DP[i] = MIN(DP[i], DP[i/3]+1);
    }
    printf("%d",DP[N]);
    return 0;
    
}

[문제]

www.acmicpc.net/problem/2003

[풀이]

N,M이 주어지고 길이가 N인 배열에서 구간합이 M인 경우의 수를 찾아서 출력하는 문제

구간합 문제길래 이중 for문을 사용해서 풀려고 했다.

하지만 시간 제한이 0.5초인데 M의 범위가 1부터 3억이라서 이중 for문을 사용하면 시간초과가 발생한다.

따라서 구간합 구하는 알고리즘인 투 포인터 알고리즘을 사용해서 풀었다.

start , end 를 배열의 첫번째 index부터 시작해서

현재 구간 합이  M보다 작으면 end를 +1, M보다 크면 start를 +1 

이런 방식으로 start, end 의 index를 조절하면서 구간 합을 구했다.

[코드]

시간 : 0ms

#include <iostream>
#define MAX 10000
using namespace std;

int N,M;
int arr[MAX];


int main(void)
{
    int total=0;

    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++)    scanf("%d",&arr[i]);
    
    int start =0 ;
    int end =0;
    int sum =arr[0];
    
    
    while(start <= end && end < N)
    {
        if(sum < M) sum += arr[++end];
        else if( sum > M)
        {
            sum -= arr[start++];
            if( start > end && start <N){
                end=  start;
                sum= arr[start];
            }
        }
        else if (sum == M)
        {
            total++;
            sum += arr[++end];
        }
    }
    
    printf("%d",total);
    return 0;
    
}