개발자 김수진

[문제]

www.acmicpc.net/problem/17822

[풀이]

시뮬레이션 문제로 조건별로 함수 구현해서 풀었다.

먼저 원판의 크기와 상태가 입력으로 주어지고 x,d,k가 입력으로 주어진다. 

x의  배수인 원판을 d ( 0이면 시계, 1이면 반시계) 방향으로 k만큼 회전한다.

1. 회전

2. 인접하면서 같은 수 0으로 바꿔주기

3. 인접하면서 같은 수가 하나도 없다면 원판 전체 평균 구해서 평균 보다 작은 값은 +1, 큰 값은 -1

따라서 rotate 함수에서 원판을 회전시킨다. 

그 다음 check 함수에서 인접하면서 같은 수를 0으로 바꿔준다.( 이 때 0은 포함이 안되도록 조심해야 된다.)

dx,dy를 통해 범위 내에 있는 상,하,좌,우를 확인했다.

( 추가로 원판이므로 배열의 첫번째 인덱스와 마지막 인덱스도 같은지 확인해야 된다.)

check 함수에서 같은 수가 하나도 없다면 avg 함수에서 원판 전체 평균을 구하고 update( 이 때도 평균 구할 때, 0을 조심)

[코드]

시간 : 4ms

#include <iostream>
#define MAX 51

using namespace std;

int arr[MAX][MAX];
int N,M,T;
int x,d,k;

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

void avg()
{
    int total=0;
    int cnt =0;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(arr[i][j]==0)    continue;
            total+=arr[i][j];
            cnt++;
        }
    }
    
    double average = (double)total/(double)cnt;
    if(average==0 ) return ;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(arr[i][j]==0)    continue;
            if(arr[i][j] > average) arr[i][j]-=1;
            else if(arr[i][j] < average)    arr[i][j]+=1;
            
        }
    }
}

bool check()
{
    int visited[MAX][MAX]={0,};
    
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++){
            if(arr[i][j]==0)   continue;
            
            for(int k=0;k<4;k++)
            {
                int nx = i +dx[k];
                int ny = j + dy[k];
                if(nx < 1 || ny < 1 || nx > N || ny > M )   continue;
                
                if(arr[nx][ny] == arr[i][j]){
                    visited[nx][ny]=1;
                    visited[i][j]=1;
                }
            }
            
        }
        if(arr[i][1] == arr[i][M] && arr[i][1] !=0)
        {
            visited[i][1]= 1;
            visited[i][M]=1;
        }

    }

    bool flag = false;
    
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            if(visited[i][j]==1)
            {
                arr[i][j]=0;
                flag=true;
            }
        }
    }
    if(flag == true)    return true;
    else return false;
    
}

void rotate()
{
    for(int i=1;i<=N;i++)
    {
        if(i%x!=0 ) continue;
        
        int tmp[MAX]={0,};
        
        for(int j=1;j<=M;j++){
            
            if(d==0){
                int idx =(j+k)%M;
                if(idx == 0)    idx = M;
                tmp[idx]=arr[i][j];
            }
            else{
                int idx = j-k;
                if(idx <=0 )    idx+=M;
                tmp[idx] = arr[i][j];
            }
        }
        
        for(int j=1;j<=M;j++)   arr[i][j] = tmp[j];
    }
}

int main(void)
{
    
    scanf("%d %d %d",&N,&M,&T);
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++)    scanf("%d",&arr[i][j]);
    }
    
    for(int i=0;i<T;i++)
    {
        scanf("%d %d %d",&x,&d,&k);
        
        rotate();
        if(check()==false)  avg();
    }
    
    int total=0;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            total+=arr[i][j];
        }
    }
    printf("%d",total);
    
    return 0;
    
}

[문제]

https://www.acmicpc.net/problem/1920

[풀이]

배열이 주어지고 해당 배열에 찾고자 하는 숫자가 있으면 1을 출력하고 없으면 0을 출력하는 문제이다.

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

먼저 입력 받은 배열을 오름차순으로 정렬시킨다.

BinarySearch 함수에서 이진 탐색으로 해당 값을 찾으면 true를 반환하고

존재하지 않는다면 false를 반환 

[코드]

시간 : 72ms

#include <iostream>
#include <algorithm>

#define MAX 100000

using namespace std;

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

bool BinarySearch()
{
    int mid;
    int low =0;
    int high = N-1;
    
    while(low <= high)
    {
        mid = (low + high)/2;
        if(arr[mid] == target)  return true;
        else if(arr[mid] < target)  low = mid +1;
        else    high= mid-1;
    }
    return false;
}


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

    sort(arr,arr+N);
    
    scanf("%d",&M);
    for(int i=0;i<M;i++){
        scanf("%d",&target);
    
        if(BinarySearch()) printf("1\n");
        else printf("0\n");

    }
    return 0;
    
}

지적, 조언, 질문 환영입니다.

댓글 남겨주세요~

[개념]

이진 탐색은 데이터가 정렬되어 있는 상태에서 특정 데이터를 찾는다.

배열의 시작, 중간, 끝 index를 조절해가며 탐색을 한다.

찾고자 하는 값인 x가 배열의 중간 값보다 작으면 중간을 기준으로 왼쪽에 있는 데이터 중에서만 찾고

x가 배열의 중간 값보다 클 경우 중간을 기준으로 오른쪽에 있는 데이터 중에서만 찾는다.

이와 같이 탐색 범위를 좁혀가면서 찾고자하는 값을 찾아낸다.

위의 그림은 이진 탐색의 예시로 정렬된 배열을 가지고 시작한다.

찾고자 하는 값인 13은 처음 mid인 7보다 크므로 

low = mid +1이 되고 , mid = (low+high)/2 = 3 이 된다.

arr[3]이 13이므로 true를 반환하면서 탐색을 종료한다.

[코드]

아래 코드와 같이 low는 배열의 시작, high는 배열의 끝 index부터해서

중간 값인 mid보다 찾고자하는 값인 target이 더 크면 low값을 mid+1 로 update 하고

target 값이 더 작은 경우 high의 값은 mid-1로 update 하여 탐색하는 범위를 좁혀 나갈 수 있다.

bool BinarySearch()
{
    int mid;
    int low =0;
    int high = N-1;
    
    while(low <= high)
    {
        mid = (low + high)/2;
        if(arr[mid] == target)  return true;
        else if(arr[mid] < target)  low = mid +1;
        else    high= mid-1;
    }
    return false;
}

- 선택 정렬 ( Selection Sort)

[ 개념 ]

선택 정렬은 현재 자신의 index보다 뒤에 있는 index들 중에서 배열의 원소 값이 가장 작은 원소랑 자리를 서로 바꿔줍니다.

이러한 방식으로 배열의 처음부터 끝까지 진행하여 정렬을 할 수 있습니다.

아래 그림은 선택 정렬의 예시로 다시 한번 설명해드리겠습니다.

먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다.

첫번째 index부터 시작하여 자신의 값보다 작은 값들 중에서 가장 작은 값을 찾습니다.

해당 배열에서는 '13'보다 작은 값 중에서 제일 작은 '2'를 택하게 됩니다.

제일 작은 값을 찾은 뒤 서로 자리를 swap합니다. 

다음 index로 넘어가 두번째 index를 기준으로 뒤에 있는 값들 중에서 가장 작은 값을 찾습니다.

해당 배열에서는 '7'보다 작은 값 중에서 가장 작은 값인 '3'이 되겠습니다.

마찬가지로 서로 자리를 바꿔줍니다.

마찬가지로 3번째 index를 기준으로 뒤에 있는 index 중에서 가장 작은 값을 찾습니다.

위의 배열에서는 5가 되고 '13'과 '5'의 위치를 서로 바꿔줍니다. 

위와 같은 방식으로 배열의 마지막 index까지 계속 진행합니다.

다음 index에 존재하는 값인 13를 기준으로 뒤에서 가장 작은 값을 찾습니다.

7이 가장 작으므로 '7'과 '13'의 위치를 서로 바꿔줍니다. 

마지막으로 16과 13까지 위치를 바꿔주면 배열이 오름차순으로 정렬된 것을 확인할 수 있습니다.

[ 코드 ]

아래 코드와 같이 selection sort를 구현할 수 있다.

첫번째 index부터 시작하고

idx는 i부터 시작하여 자신보다 작은 값이 없을 경우 자리를 바꿔주지 않을 수 있다. 

void selection_sort(int arr[], int size)
{
    int idx =0;
    
    for(int i=0;i<size-1;i++){
        idx = i;
        
        for(int j=i+1;j<size;j++)
            if(arr[j] < arr[idx] )  idx = j;
        
        int tmp = arr[i];
        arr[i]= arr[idx];
        arr[idx]= tmp;
    }
}

위의 코드와 같이 전체 비교를 진행하므로 시간 복잡도는 O(N^2)이다.

- 삽입 정렬 ( Insertion Sort)

[개념]

삽입 정렬은 현재 index를 기준으로 앞에 있는 값들 중에서 현재 index에 존재하는 값이 들어갈 위치를 찾아서 삽입한다.

1. 현재 값이 들어갈 위치를 찾는다.

예시를 통해서 삽입 정렬을 다시 한번 설명하겠습니다.

먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다.

삽입 정렬은 현재 위치를 기준으로 앞에 있는 원소들과 비교하므로 배열 index로 1부터 시작합니다.

7을 기준으로 자신보다 앞에 있는 원소들 중에서 삽입될 자리를 찾습니다.

7은 13보다 작으므로 13 앞에 삽입됩니다.

다음 배열 값인 2는 7,13 보다 모두 작으므로 

제일 첫번째 자리에 삽입됩니다.

그 다음 4번째 index의 값인 5를 기준으로 5가 들어갈 자리를 찾습니다.

5는 2보다 크고 7보다 작으므로 2와 7사이에 들어갑니다.

5번째 index에 존재하는  16은 처음부터 16까지 모두 오름차순으로 정렬되어 있으므로 다음 index로 넘어갑니다.

마지막 index에 존재하는 숫자 3은 2보다 크고 5보다 작으므로 2와 5 사이에 삽입됩니다.

이와 같이 삽입 정렬을 통해 배열이 오름차순으로 정렬된 것을 확인할 수 있습니다.

[코드]

아래 코드는 c언어를 사용해 insertion sort 함수를 구현한 것이다.

void insertion_sort(int arr[], int size)
{
    
    for(int i=1;i<size;i++){
        int j = i-1;
        int key = arr[i];
        
        while(j >= 0 && arr[j] > key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

최악의 경우 시간 복잡도는 O(N^2)이다.

하지만 만약 배열이 처음부터 정렬되어 있었다면 while문을 실행하지 않게 되므로 시간 복잡도는 O(N)이다.

- 버블 정렬 ( Bubble Sort)

[개념]

버블 정렬은 인접한 두 원소를 비교해 정렬합니다.

1회전을 수행하면 가장 큰 값이 제일 뒤에 위치하게 됩니다. 

예시를 통해서 버블 정렬을 다시 한번 설명하겠습니다.

먼저 아래와 같이 아직 정렬이 되지 않은 배열이 있습니다.

위의 그림은 버블 정렬을 1회전 실행한 결과로 가장 큰 값이 제일 뒤에 위치한 것을 확인할 수 있습니다.

위의 그림은 버블 정렬 2회전을 하고 난 뒤의 결과로 첫번째 index부터 마지막 index까지 모두 정렬된 것을 확인할 수 있습니다.

[코드]

최상, 평균, 최악의 경우 모두 

N-1, N-2, ... ,1 = N(N-1)/2번 비교를 하게된다.

따라서 시간 복잡도는 O(N^2)이다.

void bubble_sort(int arr[], int size)
{
    for(int i=size-1;i>0;i--)
    {
        for(int j=0;j<i;j++)
        {
            if(arr[j] > arr[j+1])
            {
                int tmp=arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

[문제]

www.acmicpc.net/problem/1976

[풀이]

도시간의 연결 정보가 주어지고, 여행 경로가 주어진다.

도시가 연결되어 있으면 이동할 수 있고 연결되어 있지 않다면 이동할 수 없다. 

여행경로를 통해 여행을 할 수 있는지 구하는 문제이다.

이 문제는 유니온 파인드(Union-Find)를 통해 풀었다.

먼저 parent 배열을 자기 자신으로 초기화 해준다.

연결정보를 입력으로 받으면 두 개의 node에 대해 parent를 같게 해주어 하나의 집합에 속하도록 한다.

여행 경로를 가지고 각 노드에 대해 루트 노드를 확인하여 이동할 수 있는지를 판단한다.

루트 노드가 다르다면 서로 다른 집합에 속하는 것이므로 이동할 수 없다.

따라서 'NO'를 출력하고 끝내면 되고

모든 노드에 대해 루트 노드가 같다면 하나의 집합에 속하는 것이므로 이동할 수 있다.

[코드]

시간 : 4ms

#include <iostream>
#include <vector>

#define MAX 200

using namespace std;

int map[MAX][MAX]={0,};
int parent[MAX];

vector <int> _path;

int N,M;

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

void unit(int idx1 ,int idx2)
{
    idx1 = find(idx1);
    idx2 = find(idx2);
    
    if(idx1 != idx2)
    {
        parent[idx2] = idx1;
    }
}
int main(void)
{
    scanf("%d %d", &N,&M);
    
    for(int i=0;i<N;i++){
        parent[i] = i;
        for(int j=0;j<N;j++)    scanf("%d",&map[i][j]);
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j] == 1)  unit(i,j);
        }
    }
    
    for(int i=0;i<M;i++){
        int v;
        scanf("%d",&v);
        _path.push_back(v-1);
    }
    
    for(int i=0;i<M-1;i++){
        if(find(_path[i]) != find(_path[i+1])){
            printf("NO");
            return 0;
        }
    }
    
    printf("YES");
    return 0;
}

[문제]

www.acmicpc.net/problem/17070

[풀이]

처음에 파이프는 가로 방향을  (1,1)과 (1,2)에 위치한다.

파이프는 회전을 할 수 있으며

파이프가 이동하여 (N,N)에 도달할 수 있는 방법의 수를 출력하면 된다. 

BFS 방법으로 풀어보고 DFS 방법으로도 풀어봤다.

- BFS

visited 배열을 사용해 좌표와 현재 방향과 앞으로 나아갈 방향을 가지고 방문한 곳은 1로 update 해주었다.

이미 확인한 곳은 다시 방문하지 않도록 했는데 틀렸습니다가 나왔다. 아직도 이거는 왜 틀린지 모르겠다.

생각해보니 visited 배열이 굳이 필요하지 않을 것 같아서 없이 풀었더니 맞았습니다가 나왔다.

근데 시간이 너무 오래 걸린다.

- DFS

다음 좌표를 재귀로 호출해가며 (N,N)에 도달하면 끝나도록 했다.

[코드]

- DFS 방법

시간 : 116ms

#include <iostream>

#define MAX 17

using namespace std;
int map[MAX][MAX]={0,};
int N;

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

int cnt= 0;

void DFS(int x, int y, int dir)
{
    if(x == N-1 && y == N-1){
        cnt++;
        return;
    }
    for(int i=0;i<3;i++){
        
        if( dir == 0 && i==2)  continue;
        else if( dir == 2 && i==0)   continue;
        
        int nx =x+dx[i];
        int ny = y+dy[i];
        if(nx >= N || ny >= N ||map[nx][ny] == 1 ) continue;
        if(i==1 && (map[nx][ny-1] !=0 || map[nx-1][ny]!=0)) continue;
        
        DFS(nx,ny,i);
    }
}

int main(void)
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&map[i][j]);
        }
    }
    
    DFS(0,1,0);
    printf("%d",cnt);
    return 0;
}

- BFS 방법

시간 : 240ms

#include <iostream>
#include <queue>

#define MAX 17

using namespace std;

struct pos{
    int x,y,dir;
};

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

int dx[3] = {0,1,1};
int dy[3] = {1,1,0};
// dir : 가로 0, 대각석 1, 세로 2

void BFS()
{
    int cnt =0;
    int visited[MAX][MAX][3][3]={0,};

    queue <pos> q;
    
    q.push({0,1,0});
    
    while(!q.empty())
    {
        int x= q.front().x;
        int y= q.front().y;
        int dir = q.front().dir;
        if( x== N-1 && y == N-1)    cnt++;
        q.pop();
        
        for(int i=0;i<3;i++){
            
            if(dir ==0 && i==2) continue;
            else if(dir == 2 && i ==0)  continue;
            
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= N ) continue;
            if(map[nx][ny] == 1)    continue;
            if(i==1 && (map[nx][ny-1] !=0 || map[nx-1][ny]!=0)) continue;
            
            q.push({nx,ny,i});
        }
    }
    printf("%d",cnt);
    return ;
}

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

[문제]

www.acmicpc.net/problem/17143

[풀이]

1. 낚시왕 이동

낚시왕은 열을 기준으로 한칸씩 움직인다. 

2. 낚시왕 낚시

낚시왕은 자신이 존재하는 열에서 가장 가까운 물고기를 잡는다.

3. 물고기 이동

물고기는 1초에 속력만큼 이동한다. 이 때 범위를 벗어나면 방향을 바꿔서 움직인다.

시뮬레이션 문제로 낚시하는 함수인 fishing과 물고기가 이동하는 함수인 move를 구현하여 풀었다.

물고기들의 정보를 구조체에 저장하여 1번 물고기부터 M번 물고기까지 차례대로 이동

이 때, 한 칸에는 한 마리의 물고기만 존재할 수 있으므로 visited 배열을 사용해 처리한다.

(자신보다 큰 물고기가 있을 경우 죽도록) 

[코드]

시간 : 44ms

#include <iostream>

#define MAX 101

using namespace std;

struct FISH{
    int x,y,s,d,z;
    bool die;
};

int R,C,M;
int score=0;
int map[MAX][MAX]={0,};
FISH fish[MAX*MAX];
int idx =0;

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

void move()
{
    int visited[MAX][MAX]={0,};

    
    for(int i=1;i<=M;i++){
        
        if(fish[i].die) continue;

        int dir = fish[i].d;
        int x = fish[i].x;
        int y = fish[i].y;
        int s = fish[i].s;
        int nx;
        int ny;
        
        while(1){
            
            nx = x+ dx[dir] * s;
            ny = y+ dy[dir] * s;
            
            if( nx >=1 && ny >=1 && nx <= R && ny <= C) break;
            else if ( dir == 1 )    {
                s = s - (x-1);
                x = 1;
                dir = 2;
                
            }
            else if ( dir == 2 )    {
                s = s - (R-x);
                x = R;
                dir =1;
            }
            else if ( dir == 3 )    {
                s = s - (C-y);
                y = C;
                dir = 4;
            }
            else if ( dir == 4 )    {
                s = s- (y-1);
                y =1;
                dir= 3;
            }
            fish[i].d = dir;
            
        }
        
        fish[i].x = nx;
        fish[i].y = ny;
        
        if(visited[nx][ny] != 0)
        {
            int num  = visited[nx][ny];
            
            if( fish[i].z < fish[num].z)    fish[i].die = true;
            else{
                visited[nx][ny]=i;
                fish[num].die = true;
            }
        }
        else    visited[nx][ny]=i;
    }
    
    for(int i=1;i<=R;i++){
        for(int j=1;j<=C;j++)   map[i][j] = visited[i][j];
    }
}

void fishing(int idx)
{
    for(int i=1;i<=R;i++)
    {
        if(map[i][idx] != 0){
            int num= map[i][idx];
            score+=fish[num].z;
            map[i][idx]=0;
            fish[num].die=true;
            return;
        }
    }
}

int main(void)
{
    scanf("%d %d %d",&R,&C,&M);
    
    for(int i=1;i<=M;i++){
        int x,y,s,d,z;
        scanf("%d %d %d %d %d",&x,&y,&s,&d,&z);
        map[x][y]=i;
        fish[i] = {x,y,s,d,z,false};
    }
    
    for(int i=1;i<=C;i++){
        fishing(i);
        move();
    }
    
    printf("%d",score);
    return 0;
    
}

[ 유니온 파인드란 ? ]

합집합을 찾는 대표적인 알고리즘 

Disjoint-Set이라고도 부른다.

- Union : 노드 X가 포함된 집합과 노드 Y가 포함된 집합을 하나로 합친다.

- Find :  노드 X가 포함된 집합을 찾아준다.

[ 구현 ]

- i는 노드번호, parent[i]는 i 노드의 부모 노드를 저장 

[그림 1]과 같이 처음에는 parent[i] 를 자기 자신인  i로 초기화한다.

Union(1,2) Union(3,4)을 통해 그림 2와 같이 변한다. 

노드 2의 부모 노드는 1이 되고 , 노드 4의 부모 노드는 3이 된다. 

Union(1,3)을 통해 노드 3의 부모 노드는 1이 된다. 

따라서 1,2,3,4가 하나의 집합에 포함되는 것을 확인할 수 있다.

[ Find 함수 ] 

위에서 설명한 것과 같이 parent[i]는 처음에 i로 초기화 한다.

	for(int j=0;j<N;j++)
        {
            parent[j] = j;
        }
        

find 함수는 해당 노드의 부모 노드를 return 한다.

루트 노드는 자신의 index와 parent[idx]가 같으므로

idx == parent[idx] 를 만족할 때까지 재귀를 통해 find 함수를 호출한다.

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

[ Union  함수 ]

idx1과 idx2의 부모 노드를 find 함수를 통해서 찾는다.

이 때 indx1 ,idx2 가 다르다면 부모 노드가 다른 것이므로

idx2의 부모 노드를 idx1으로 update해주어 같은 set에 속하게 된다.

int unit(int idx1, int idx2)
{
    idx1 = find(idx1);
    idx2 = find(idx2);
    
    if(idx1 != idx2 ) // 서로 부모가 다르다면
    {
        parent[idx2] = idx1;        
    }
}