개발자 김수진

[문제]

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

[풀이]

Union-Find (혹은 Disjoint-Set)을 사용해서 풀었다. 

입력 값이 문자로 주어지기 때문에 map을 사용했다. 

parent 배열에는 해당 index의 부모 노드 index를 저장했고

number 배열에는 부모 index를 기준으로 해당 set에 속한 노드의 개수를 저장했다.

map의  count 함수를 사용해 이미 존재하는 친구인지 아닌지를 확인한다.

존재하지 않는다면 새로 map에 추가해주고 전체 사람의 수인 cnt 변수에 1을 추가해준다.

map에서의 value 값을 기준으로 ( 노드 번호라고 생각하면 이해하기 쉬울 것 같다.) 

unit 함수를 호출

1. 부모 노드를 찾는다.

2. 부모 노드가 다르다면

같은 집합에 속해야 되므로 parent[idx2]  = idx1을 통해

부모를 같게 해주어 같은 집합에 속하도록 한다. 

[코드]

시간 : 132ms

#include <iostream>
#include <map>

#define MAX 200000

using namespace std;

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

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

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

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

        map <string, int> fri;
        
        for(int j=0;j<2*N;j++)
        {
            parent[j] = j;
            number[j]=1;
        }
        
        int cnt =0;
        
        for(int j=0;j<N;j++){
            
            char str1[21],str2[21];
            scanf("%s %s",str1,str2);
            //map에 str1이 존재하지 않는다면
            if(fri.count(str1)==0)  fri[str1] = cnt++;
            int idx1 = fri[str1];
            
            if(fri.count(str2)==0)  fri[str2] = cnt++;
            int idx2 = fri[str2];
            
            printf("%d\n",unit(idx1, idx2));
        }
    }
    return 0;
}

[문제]

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

[풀이]

아기 상어와 물고기가 존재. 

아기 상어는 자신보다 작은 물고기들을 잡아먹을 수 있다.

아기 상어는 자신보다 큰 물고기가 존재하는 칸은 지나가지 못한다.

아기 상어는 1칸 움직이는데 1초 걸린다.

아기 상어가 자신의 크기만큼 물고기를 먹는다면 크기가 1 증가한다.

( 크기가  3인 상어가 물고기 3마리를 먹으면 크기가 4가 된다.)

입력으로는 공간의 크기와 상태가 주어진다.

아기 상어가 먹을 수 있는 물고기들을 모두 먹을 때까지 걸리는 시간을 구해서 출력하면 된다.

BFS를 사용해 아기 상어의 좌표를 기준으로 visited에 아기 상어와 현재 좌표 사이의 거리를 저장했다.

이 때 공간의 범위를 벗어나거나, 이미 상어가 지나간 곳이거나, 상어보다 큰 물고기가 존재하는 곳은 그냥 지나친다.

물고기가 존재하고 물고기의 크기기 상어의 크기보다 작고

거리를 기준으로 현재 최소 거리보다 더 가깝다면 

잡아먹을 물고기의 좌표를 저장해놓은 tx,ty와 최소 거리인 len을 update

[코드]

시간 : 0ms

- 최소 거리 구하는 부분 ( 60번째 line)

원래 if( nx <= tx && ny <= ty)로 했더니 시간이 4ms 나와서 바꿔줬다. 

#include <iostream>
#include <queue>

#define MAX 20
using namespace std;

struct INFO{
    int x,y,size;
    
};
struct pos{
    int x,y;
};

INFO shark;

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


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


bool BFS()
{
    int visited[MAX][MAX]={0,};
    int tx,ty;
    
    int len = 1e9;
    
    queue <pos> q;
    q.push({shark.x , shark.y});
    
    while(!q.empty()){
        int x= q.front().x;
        int y= q.front().y;
        
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx <0 || ny < 0 || nx >= N || ny >= N)   continue;
            if(visited[nx][ny] != 0)    continue;
            if(map[nx][ny] > shark.size)    continue;
            
            visited[nx][ny] = visited[x][y]+1;
            q.push({nx,ny});
            
            if(map[nx][ny] != 0 && map[nx][ny] < shark.size){
                if(len > visited[nx][ny]){
                    tx = nx;
                    ty = ny;
                    len = visited[nx][ny];
                }
                else if(len == visited[nx][ny]){
                    if(nx <tx){
                        tx = nx;
                        ty = ny;
                    }
                    else if(nx == tx){
                        if(ny < ty){
                            tx = nx;
                            ty = ny;
                        }
                    }
                }
            }
        }
    }
    if(len ==1e9) return false;
    map[tx][ty]=0;
    shark.x = tx;
    shark.y = ty;
    total+= len;
    return true;
}

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]);
            if (map[i][j]==9){
                INFO info = {i,j,2};
                shark = info;
                map[i][j]=0;
            }
        }
    }
    int cnt =0;
    while(1)
    {
        if(BFS()){
            cnt++;
            if(cnt == shark.size){
                shark.size++;
                cnt=0;
            }
        }
        else break;
    }
    printf("%d",total);
    
    return 0;
    
}

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

댓글 남겨주세요~

[문제]

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

[풀이]

N,M,K가 주어지고 K년 후에 남아있는 나무의 수를 출력하면 된다.

따라서 for 문을 K년 동안 돌리고 for문에서 봄, 여름, 가을, 겨울에 대한 함수를 호출했다.

봄 - 에는 나무가 영양분을 먹는다. 단, 한 좌표에 나무가 2개 이상이면 나이가 어린 순서부터 영양분을 먹는다.

영양분이 부족하다면 먹지 못하고 나무는 죽는다.

여름 - 봄에 죽은 나무가 양분으로 변하게 된다. 해당 좌표에 나이/2 만큼 양분을 남긴다.

가을 - 나이가 5의 배수인 나무가 번식한다.

겨울 - input으로 주어진 양분이 추가된다.

봄,여름에 대한 함수를 하나로 묶고 가을,겨울에 대한 함수를 하나로 묶었다.

map을 벡터로 선언해 해당 좌표에 존재하는 나무의 나이를  벡터에 저장해줬다.

봄,여름 함수에서는 해당 좌표에 나무가 존재한다면 양분을 먹는다.

( 하나의 좌표에 여러개의 나무가 존재한다면 나이순을 오름차순 정렬)

양분이 부족해 나무가 먹지 못한다면 해당 idx를 기준으로 뒤에 있는 나무들은 모두 죽게된다. ( 오름차순으로 정렬된 상태이므로)

가을, 겨울 함수에서는 map에 벡터 사이즈를 기준으로 나무가 존재한다면 나무의 나이가 5의 배수인지 확인

5의 배수라면 나무는 번식한다. 따라서 주변 좌표에 나이가 1인 나무를 추가.

또한 양분을 추가해준다.(겨울)

[코드]

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

#define MAX 11

using namespace std;

int N,M,K;
int A[MAX][MAX]={0,};//추가되는 양분
int nutrient[MAX][MAX]={0,}; // 현재 양분
vector<int> map[MAX][MAX];

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

void SpringSummer()
{
    int visited[MAX][MAX]={0,}; // 현재 양분

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            
            int _size = map[i][j].size();
            
            if(_size==0)    continue;
            else if(_size > 1)  sort(map[i][j].begin(), map[i][j].end());
            
            int idx=0;
            while(idx < _size){
                if(map[i][j][idx] <= nutrient[i][j]) {
                    nutrient[i][j]-=map[i][j][idx];
                    map[i][j][idx]++;
                }
                else    break;
                idx++;
            }
            
            if(idx != _size){
                
                for(int k=_size-1; k>=idx ; k--){
                    nutrient[i][j] += map[i][j][k]/2;
                    map[i][j].pop_back();
                    M--;
                }
            }
        }
    }
}

void FallWinter()
{
    int num = M;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<= N;j++){
            if(map[i][j].size() ==0)    continue;
            
            for(int k=0;k<map[i][j].size();k++){
                int age = map[i][j][k];
                
                if(age%5 == 0){
                    for(int l=0;l<8;l++){
                        int nx = i + dx[l];
                        int ny = j + dy[l];
                        
                        if(nx < 1 || ny < 1 || nx > N || ny > N)    continue;
                        
                        map[nx][ny].push_back(1);
                        M++;
                    }
                }
            }
        }
    }

    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)   nutrient[i][j]+=A[i][j];
    }
}

int main(void)
{
    scanf("%d %d %d",&N,&M,&K);
    
    for(int i=1;i<=N;i++){
        for(int j=1; j<= N;j++) scanf("%d",&A[i][j]);
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1; j<= N;j++) nutrient[i][j]=5;
    }
    
    for(int i=0;i<M;i++)
    {
        int x,y,age;
        scanf("%d %d %d",&x,&y,&age);
        map[x][y].push_back(age);
    }
    
    for(int i=0;i<K;i++){
        SpringSummer();
        FallWinter();
    }
    
    printf("%d",M);
    return 0;
    
}

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

댓글 남겨주세요~

[ 캐시란 ]

Main memory와 CPU 사이에 존재하여 자주 쓰는 데이터를 저장한다.

따라서 데이터를 읽기 위해 Main memory에 접근하지 않아도 된다.

=> 시간 단축

[ 캐시 작동 원리 ]

• 시간 지역성 ( Temporal Reference)

한번 참조된 데이터는 다시 참조될 확률이 높다. 

• 공간 지역성 ( Spatial Reference)

참조된 데이터 주변에 있는 데이터가 다음에 참조될 확률이 높다.

위의 두가지를 반복문을 예로 설명하면 

i라는 변수는 다시 참조된다. => 시간 지역성

arr 주변 데이터가 참조된다. (arr[0], arr[1], ...) => 공간 지역성 

for(int i=0;i<5;i++)
	cout << arr[i];

CPU가 요청한 데이터가 캐시에 존재하면 Cache HIT

없어서 메모리에서 가져오는 경우 Cache MISS

• Capacity Miss

캐시 Memory가 작아서 발생하는 Miss

• Compulsory Miss

특정 데이터에 처음 접근할 때, 캐시에 존재하지 않아서 발생하는 Miss

• Conflict Miss

캐시메모리에 A데이터, B데이터를 저장해야하는데,

A와 B가 같은 캐시 메모리 주소에 할당되어서 발생하는 Miss

[ 캐시 구조 및 작동 방식 ]

• Direct Mapped Cache

메모리 주소의 index field를 기준으로 캐시 메모리에 Mapping

간단하고 빠르지만 Conflict Miss가 발생한다는 단점이 있다.

• Fully Associative Cache

비어있는 캐시 메모리 아무 공간에 저장

원하는 데이터를 찾기 위해 cache set을 모두 확인해봐야 하므로 시간이 꽤 걸린다.

• Set Associative Cache

Direct + Fully 방식으로 특정  set을 정해놓고 ( Cache line을 묶은 것이 Cache set ) 

그 중 비어있는 곳 아무곳에나 저장한다.

[ Write Strategy ]

[문제]

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

[풀이]

인구 차가 L 이상, R 이하라면 queue와 vector에 넣어서

인구 이동 할 수 있는 좌표 모두 구하고 

마지막에 인구 평균 구하고 map을  평균 값으로 update 해준다. 

queue는 BFS로 풀기 위해서 사용

vector는 나중에 인구 이동 하고 인구 수 update 하기 위한  좌표들 저장

solve 함수에서 평균 인구 수 구하고 vector에 저장된 좌표들 update

시간 : 108ms

[코드]

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

#define MAX 50

using namespace std;


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

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

struct pos{
    int x,y;
};
vector <pos> v;

void solve()
{
    int _size = v.size();
    int avg = sum/_size;
    
    for(int i=0;i<v.size();i++){
        int x = v[i].x;
        int y = v[i].y;
        map[x][y]= avg;
    }
}

int main(void)
{
    cin >> N>>L>>R;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    int cnt =0;
    queue <pos> q;
    
    
    while(1){
        
        bool flag = false;
        int visited[MAX][MAX]={0,};

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                    
                if(visited[i][j]==0){
                    q.push({i,j});
                    v.push_back({i,j});
                    visited[i][j]=1;
                    sum += map[i][j];
                }
                
                while(!q.empty()){
                    
                    int x = q.front().x;
                    int y = q.front().y;
                    
                    q.pop();
                                        
                    for(int k=0;k<4;k++){
                        
                        int nx =x+dx[k];
                        int ny =y+dy[k];
                        
                        if(nx < 0 || ny <0 || nx >= N || ny >= N || visited[nx][ny])   continue;
                        int comp= map[x][y] > map[nx][ny] ? map[x][y] - map[nx][ny] : map[nx][ny]-map[x][y];
                        
                        if(L <= comp && comp <= R){
                            q.push({nx,ny});
                            v.push_back({nx,ny});
                            visited[nx][ny]=1;
                            sum += map[nx][ny];
                        }
                    }
                }
                
                if(v.size() > 1){
                    solve();
                    flag = true;
                }
                v.clear();
                sum=0;
                
            }
        }
        if(!flag )  break;
        else    cnt++;

    }
    printf("%d",cnt);
    return 0;
    
}

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

댓글 남겨주세요~

[문제]

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

[풀이]

sql 문제로 IFNULL을 사용해 이름이 NULL이면 "No name"으로 채워줬다.

또한 ANIMAL_ID를 기준으로 오름차순으로 정렬 

IFNULL(필드명, "대체할 값") : 필드가 Null이면 대체할 값으로 채운다.

[코드]

SELECT ANIMAL_TYPE,IFNULL(NAME, "No name") ,SEX_UPON_INTAKE from ANIMAL_INS
order by ANIMAL_ID ASC

[문제]

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

[풀이]

차량 이동경로를 sort 함수를 사용해 오름차순으로 정렬한다.

첫번째 이동경로의 진출 지점을  CCTV의 위치로 초기화

두번째 이동경로부터 마지막 이동경로까지 

현재 이동경로의 진출 지점이 CCTV의 위치보다 앞에 있는 경우 => CCTV의 위치만 update

현재 이동경로의 진입 지점이 CCTV의 위치보다 뒤에 있는 경우 => CCTV의 위치 update, CCTV 설치 갯수 1 증가.

[코드]

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

using namespace std;

int solution(vector<vector<int>> routes) {
    int answer = 1;
    sort(routes.begin(), routes.end());
    
    int pos = routes[0][1];
    
    for(int i=1;i<routes.size();i++){
        if(routes[i][1] < pos)  pos = routes[i][1];
        else if(routes[i][0] > pos){
            answer++;
            pos = routes[i][0];
        }
    }
    return answer;
}

진짜 간단하게 풀 수 있는 문제인데 처음에 너무 복잡하게 생각했다.

[문제]

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

[풀이]

 DFS를 사용해 각 CCTV에 대해 모든 경우의 수를 따져주고 최솟값을 구하면 된다. 

[그림 1]과 같이 DFS 함수에서 visited 배열에 CCTV가 감시할 방향을 저장해놓고

모든 CCTV에 대해 저장했다면 solve 함수에서 방향에 맞게 감시 진행

이런 방식으로  spread 함수에서 좌표랑 방향을 인자 값으로 넘겨주고

벽을 만나기 전까지 감시할 수 있는 좌표에 -1을 저장해준다.

모든 CCTV에 대해 확인하면 마지막으로 0의 갯수를  count

현재 사각지대의 최솟값이랑 비교하면 더 작으면 최솟값을 update

[코드]

#include <iostream>
#include <vector>

#define MAX 8
using namespace std;
/*
지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호
 */

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

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

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

int cnt=0;
vector <pos> CCTV;
int MIN =1e9;

void spread(int x, int y, int dir)
{
    while(1){
        if(tmp[x][y]==6)    return;
        if(x < 0 || y < 0 || x >= N || y >= M ) return;
        tmp[x][y]=-1;
        
        x += dx[dir];
        y+= dy[dir];
    }
}


void solve()
{
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)    tmp[i][j] = map[i][j];
    }
    
    for(int i=0;i<cnt;i++){
        
        int x = CCTV[i].x;
        int y = CCTV[i].y;
        
        if(CCTV[i].num==1){
            spread(CCTV[i].x, CCTV[i].y, visited[i]-1);
        }
        else if(CCTV[i].num==2){
            if(visited[i]==1){
                spread(x, y, 1);
                spread(x, y, 3);
            }
            else{
                spread(x, y, 0);
                spread(x, y, 2);
            }
        }
        else if(CCTV[i].num==3){
            if(visited[i]==1){
                spread(x, y, 0);
                spread(x, y, 1);
            }
            else if(visited[i]==2){
                spread(x, y, 1);
                spread(x, y, 2);
            }
            else if(visited[i]==3){
                spread(x, y, 2);
                spread(x, y, 3);
            }
            else if(visited[i]==4){
                spread(x, y, 3);
                spread(x, y, 0);
            }
        }
        else if(CCTV[i].num==4){
            if(visited[i]==1){
                spread(x, y, 0);
                spread(x, y, 1);
                spread(x, y, 2);
            }
            else if(visited[i]==2){
                spread(x, y, 1);
                spread(x, y, 2);
                spread(x, y, 3);

            }
            else if(visited[i]==3){
                spread(x, y, 2);
                spread(x, y, 3);
                spread(x, y, 0);

            }
            else if(visited[i]==4){
                spread(x, y, 3);
                spread(x, y, 0);
                spread(x, y, 1);

            }
        }
        else if(CCTV[i].num==5){
            spread(x, y, 0);
            spread(x, y, 1);
            spread(x, y, 2);
            spread(x, y, 3);

        }
    }
    int tmp1=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(tmp[i][j]==0)    tmp1++;
        }
    }
    
    if(tmp1 < MIN)  MIN = tmp1;
}

void DFS(int idx)
{
    if(idx == cnt)
    {
        solve();
        return;
    }
    
    if(CCTV[idx].num == 1){
        for(int i=1;i<=4;i++){
            visited[idx]=i;
            DFS(idx+1);
        }
    }
    else if(CCTV[idx].num == 2){
        for(int i=1;i<=2;i++){
            visited[idx]=i;
            DFS(idx+1);
        }
    }
    else if(CCTV[idx].num == 3){
        for(int i=1;i<=4;i++){
            visited[idx]=i;
            DFS(idx+1);
        }
    }
    else if(CCTV[idx].num == 4){
        for(int i=1;i<=4;i++){
            visited[idx]=i;
            DFS(idx+1);
        }
    }
    else if(CCTV[idx].num == 5) DFS(idx+1);
    
    return;
    
}
int main(void)
{
    cin >> N >> M;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
        {
            cin >> map[i][j];
            if(map[i][j] != 0 && map[i][j]!=6){
                CCTV.push_back({i,j,map[i][j]});
                cnt++;
            }
        }
    }
    
    DFS(0);
    
    cout << MIN << endl;
    
    
    return 0;
    
}

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

댓글 남겨주세요~