개발자 김수진

[문제]

www.acmicpc.net/problem/1202

[풀이]

보석의 무게, 가격과 가방의 무게가 주어지고 가방에 담을 수 있는 보석 가격 합의 최댓 값을 구하는 문제

무게를 기준으로 보석과 가방을 오름차순으로 정렬하여 , 가방의 무게를 기준으로 담을 수 있는 보석 무게 중 가격이 가장 높은 것을 선택하는 방식으로 풀었다. 원래는 보석 가격이 가장 높은 것을 선택하기 위해 vector를 사용해  43번째 줄의 while문이 끝날 때마다 vector를 오름차순으로 정렬하여 가장 높은 가격의 보석을 알아냈다. 하지만 시간 초과가 발생하여 priority_queue (우선순위 큐)를 사용해 queue에 push 할 때마다 정렬하도록 하여 시간초과 문제를 해결할 수 있었다.

[코드]

시간 : 572ms

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

#define MAX 300001

using namespace std;

struct diamond{
    int weight, value;
};

int bag[MAX]={0,};
int N,K;

bool comp(diamond & a, diamond & b)
{
    return a.weight < b.weight;
}

int main(void)
{
    vector <diamond> v;
    priority_queue <int> q;
    
    cin >> N >> K;
    for(int i=0;i<N;i++){
        int a,b;
        cin >> a>>b;
        v.push_back({a,b});
    }
    for(int i=0;i<K;i++)    cin >> bag[i];
    
    sort(v.begin(),v.end(),comp);
    sort(bag,bag+K);
    
    int idx =0;
    long long int res=0;

    for(int i=0;i<K;i++){
        int weight = bag[i];
        while(idx < N ){
            if(v[idx].weight <= weight){
                q.push(v[idx].value);
                idx++;
            }
            else    break;
        }
        if(q.size()==0 )  continue;
        res+=q.top();
        q.pop();
    }
    cout << res;
    return 0;
}

[문제]

www.acmicpc.net/problem/10800

[풀이]

각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 구하는 문제이다.

단 공의 색깔이 같거나 공의 크기가  같다면 잡을 수 없다.

처음에 단순 이중 for문을 사용해서 풀려고 했다. 그러면 시간 복잡도가 O(N^2)이 된다.

하지만 N의 범위가 1 ≤ N ≤ 200,000 이므로 최악의 경우 시간초과가 발생한다.

따라서 다른 방법을 생각했다.

먼저 공의 크기를 기준으로 오름차순 정렬을 하고 , 현재까지의 모든 공의 크기 합에서 색깔이 같거나 크기가 같은 공의 무게를 빼준다.

(idx)번째 공이 사로잡을 수 있는 공의 크기

= 현재까지 공 크기의 합 - (idx)번째 공과 색깔이 같은 공들의 무게 합 - (idx)번째 공과 크기가 같은 공들의 무게 합 + (idx)번째 공의 무게

단 , 위의 식에서 크기와 색깔이 모두 같은 경우 이전 index의 공이 사로잡을 수 있는 값과 같도록 하였다.  

또한 오름차순 정렬을 할 때 , 공의 크기가 같다면 색깔을 기준으로 정렬하도록 하였다.

색깔을 신경쓰지 않으면 아래와 같은 문제가 발생한다.

Ex)

3

1 4

2 4

1 4

출력 : -4

정답 : 4 

[코드]

시간 : 208ms

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200020

using namespace std;

struct ball{
    int weight, color, idx;
};

int ans[MAX]={0,};
int C[MAX]={0,};
int S[MAX]={0,};
int N;
bool comp(ball &a, ball &b) {

    if (a.weight==b.weight) return a.color < b.color;

    return a.weight < b.weight;
}
int main(void)
{
    vector <ball> v;

    cin >> N;
    for(int i=0;i<N;i++){
        int weight,color;
        cin >> color >> weight;
        v.push_back({weight,color,i});
    }
    sort(v.begin(),v.end(),comp);
    
    int sum=0;
    
    for(int i=0;i<N;i++){
        
        int weight = v[i].weight;
        int color = v[i].color;
        int idx = v[i].idx;
        
        C[color]+=weight;
        S[weight]+=weight;
        sum+=weight;
        
        ans[idx]= sum - C[color] - S[weight] +weight;
        if(i!=0 && (v[i-1].color == color) && (v[i-1].weight == weight))    ans[idx] = ans[v[i-1].idx];
    }
    
    for(int i=0;i<N;i++)    cout << ans[i] <<"\n";
    return 0;
}

• 블록(Block) 요소와 인라인(Inline) 요소 

1. 블록 요소

- 사용 가능한 가로 너비를 최대한 활용

- 크기를 지정할 수 있다.

( default = width : 100%, height : 0%)

- 수직으로 쌓인다.

- margin, padding 온전하게 사용 가능

- 주로 레이아웃을  다루기 위해 사용

Ex ) DIV, H1, P...

2.   인라인 요소

- 필요한 가로 너비만 사용

- 크기를 지정할 수 없다.

( default = width : 0%, height : 0%)

- 수평으로 쌓인다.

- margin, padding에서 top,down 사용 불가능

- 주로 TEXT에 사용

Ex) IMG, SPAN...

• 여러가지 의미있는 블록 요소 태그들

- header : 홈페이지 가장 상단 부분을 나타내는 태그 , 페이지 상단바

- foooter : 홈페이지 가장 하단, 저작권 데이터 등과 같은 내용이 기재된 부분

- article : 독립적으로 구분 가능하거나 재사용 가능한 영역을 설정 

ex ) 블로그, 매거진 등...

- section : 영역을 나눌 때 많이 사용, 영역에 의미가 있기 때문에 제목을 포함. 주로 h1~h6를 사용해 구분

- aside : 오른쪽, 왼쪽 등 사이드 부분에 광고와 같은 것들을 넣을 때 사용

- nav :   navigation의 약자로 다른 페이지의 링크를 제공. 보통 메뉴를 묶을 때 많이 사용 

- address : 연락처, 주소 등의 정보롤 제공할 때 사용

- div : 아무 의미를 나타내지 않는 태그, 꾸미는 목적으로 많이 사용 

================================================================================

- ol : ordered list. 순서 type, 역순, 시작 값, 등을 지정할 수 있다.

ex)

<ol type="a" reversed="reversed"></ol>

- ul : unordered list

- li : list item, li 단독으로는 사용 못해. ol이나 ul의 자식으로 포함되어야 된다.

- h1 ~ h6 : 제목을 나타낼 때 사용, 순차적으로 사용( h1 다음 h4 말고 h2 사용)

- p : paragraph, 하나의 문단을 설정할 때 사용

- hr : 문단의 분리를 위해 사용( 의미적 표현 ). 수평선을 생성 (시각적 표현)

- pre : preformatted text, 서식이 미리 정해진 텍스트. 텍스트의 공백과 줄바꿈을 유지 가능 

  tab, spacebar 등이 그대로 출력 가능 

• 여러가지 의미있는 인라인 요소 태그들

- a : Anchor,  현재 문서에서 외부 문서로 링크를 걸 때. 버튼 요소로 많이 쓰인다.

    파일 다운로드 등...

    주로 block요소로 전환하여 모양을 입힌다. 

    속성으로  target이 존재하는데 링크 url을 현재 창에 띄울지 , 새로운 창에 띄울지 설정할 수 있다.

    또한 href를 id로 설정하여 해당 id를 지닌 태그가 존재하는 위치로 이동할 수 있다.

    <a href="https://google.co.kr" target="_blanck">google</a>
    <a href="./image1.png">Image Download</a>


<!-- 페이지 내에서 list1이라는 id가 존재하는 위치로 이동 -->
    <ul>
        <li><a href="#list1">list1</a></li>
    </ul>
    <h2 id="list1">list1</h2>

- abbr : abbreviation, 약어

abbr를 사용해 약어를 설명

<abbr title="Hyper Text Markup Language>HTML</abbr>

-

[문제]

www.acmicpc.net/problem/13549

[풀이]

언니의 위치 N, 동생의 위치 K가 입력으로 주어지고 언니가 동생을 찾는데 걸리는 최소 시간을 구하는 문제이다.

숨바꼭질4( www.acmicpc.net/problem/13913) 와 굉장히 유사한 문제이다.

BFS를 사용해서 풀었다. 

원래 BFS는 방문 체크를 하여 이미 방문한 곳이라면 다시 방문하지 않는다.

하지만 이 문제에서는 순간이동이 있으므로 이미 방문했더라도 최솟값을 가질 수 있다.

ex) 5 --> 8

1. 5-> 6-> 7-> 8  : 3초

2. 5-> 10-> 9-> 8  : 2초

따라서 이미 방문했더라도 현재 이동 횟수가 더 작다면 재방문 할 수 있도록 하였다.

이와 같은 방식으로 while문을 반복하여 K에 도착하면 map의 값을 return 하면서 BFS 함수를 끝내도록 하였다.

[코드]

시간 : 0ms

#include <iostream>
#include <queue>

#define MAX 200001

using namespace std;

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

int dx[2]={-1,1};

int BFS()
{
    queue <int> q;
    q.push(N);
    map[N]=1;
    
    while(!q.empty()){
        
        int x = q.front();
        q.pop();
        
        if(x == K)  return map[x]-1;
        
        for(int i=0;i<3;i++){
            int npos = x;
            if(i==2)    npos = x*2;
            else    npos= x+dx[i];
            
            if(npos <0 || npos >= MAX)  continue;
            if(i!=2 &&  (map[npos]!=0 && map[npos] <= map[x]+1))    continue;
            if(i==2 &&  (map[npos]!=0 && map[npos] <= map[x]))  continue;
            
            q.push(npos);
            
            if(i==2)    map[npos] = map[x];
            else    map[npos]= map[x]+1;
        }
    }
    
    return 0;
}
int main(void)
{
    cin >> N>> K;
    cout << BFS();
}

[문제]

www.acmicpc.net/problem/2437

[풀이]

추의 무게가 주어지고 추를 사용해서 측정할 수 없는 무게의 최솟값을 구하는 문제이다.

아무리 생각해도 다 더하는 방법 말고는 생각이 안나서 풀이를 봤다.

풀이는 그리디 알고리즘으로 구현했다. 

주어진 추의 무게를 오름차순으로 정렬하고 현재까지의 합을 sum이라고 할 때,

더하려는 추의 무게가 sum+2보다 크거나 같다면

sum+1의 무게는 측정할 수 없다.

풀이를 보니 이해는 되지만 문제를 풀면서 어떻게 이런 방식을 생각해내는지 모르겠다. 

[코드]

시간 : 0ms

#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

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

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++)    cin >> arr[i];
    sort(arr,arr+N);
    
    int sum=0;
    
    for(int i=0;i<N;i++){
        if(sum+2<=arr[i]){
            cout << sum+1;
            return 0;
        }
        sum+=arr[i];
    }
    cout << sum+1;
    return 0;
}

[문제]

www.acmicpc.net/problem/5624

[풀이]

N개의 수열이 입력으로 주어지고, 하나의 숫자가 앞의 3개의 숫자를 더해서 나타낼 수 있을 때 좋은 수라고 한다.

이 때 입력에서 좋은 수의 갯수를 구해서 출력하면 된다.

좋은 수인지 판단하려는 숫자고 D라고 하면 A+B+C=D를 만족하는 수를 찾으면 된다.

좀더 다르게 생각하면 A+B=D-C 를 만족하는 D를 찾으면 된다.

따라서 D 이전의 숫자들 중에서 A+B의 값을 negative, positive 배열에 저장해놓고

D-C를 만족하는 값이 있는지 확인하는 방법으로 구현했다.

입력으로 주어지는 숫자가 -100,000 ≤ Ai ≤ 100,000이므로 A+B가 음수일수도 있다.

음수는 negative 배열에, 양수는 positive 배열에 저장했다.

[코드]

시간 : 8ms

#include <iostream>
#define MAX 100001

using namespace std;

int N;
int arr[5001]={0,};
bool positive[MAX*2]={0,};
bool negative[MAX*2]={0,};

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++)    cin >> arr[i];
    
    int cnt =0;
    for(int i=1;i<N;i++){
        for(int j=0;j<i;j++){
            int num =arr[j]+arr[i-1];
            if(num >=0) positive[num]=true;
            else    negative[num*-1]=true;
        }

        for(int j=0;j<i;j++){
            int num =arr[i]-arr[j];
            if(num >=0 && positive[num]){
                cnt++;
                break;
            }
            else if( num<0 && negative[num*-1]){
                cnt++;
                break;
            }
        }
    }
    cout << cnt;
    return 0;
}

[문제]

www.acmicpc.net/problem/1339

[풀이]

입력으로 주어진 알파벳을 숫자로 바꿔서 알파벳 합의 최댓값을 구하는 문제이다.

먼저 해당 알파벳이 몇번째 숫자로 얼마나 나왔는지에 따라 알파벳에 대한 숫자를 지정했다.

예를 들어 ABCD라면, A->9, B->8, C->7, D->6 이렇게 큰 자릿수가 큰 숫자를 가지도록 해야 최댓값을 구할 수 있다.

따라서 visited 배열에 해당 알파벳의 자릿수를 저장하였다.

위의 예시로는 visited[0]=1000, visited[1] = 100, visited[2] = 10, visited[3] = 1

이와 같은 방식으로 입력으로 주어진 알파벳에 대해 저장하였다.

입력이 ABA인 경우 visited[0] = 101, visited[1] = 10이 된다.

이렇게  visited 배열을 저장하고, visited 배열에 저장된 값을 기준으로 정렬하였다.

그리고 9부터 시작하여 큰 값을 가지고 있는 알파벳에 할당하였다.

이런 식으로 각 알파벳에 대해 숫자를 지정하고 합을 구하여 출력하였다. 

[코드]

시간 : 0ms

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

int N;
vector <string> v;

int alphabet[26]={0,};
int visited[26]={0,};

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        string tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    vector <pair<int,int>> order;
    
    for(int i=0;i<N;i++){
        string str = v[i];
        int _size = str.size();
        int idx = 1;
        for(int j=_size-1;j>=0;j--){
            visited[str[j]-65] += idx;
            idx *=10;
        }
    }
    for(int i=0;i<26;i++)
        if(visited[i] != 0) order.push_back({visited[i],i});
    
    sort(order.begin(),order.end());
    
    int num=9;
    for(int i=order.size()-1 ; i>=0;i--){
        if(alphabet[order[i].second]==0){
            alphabet[order[i].second]=num;
            if(num>0)   num--;
        }
    }
    int ans =0;
    for(int i=0;i<N;i++){
        string str = v[i];
        int _size = str.size();
        int idx = 1;
        for(int j=_size-1;j>=0;j--){
            ans += alphabet[str[j]-65] * idx;
            idx *= 10;
        }
    }
    cout <<ans;
    return 0;
    
}

[문제]

www.acmicpc.net/problem/4179

[풀이]

지훈이가 미로를 빠져나오는데 최소 시간을 구하는 문제로 아래 문제와 굉장히 유사하여 쉽게 접근할 수 있었다.

www.acmicpc.net/problem/5427

불도 매초마다 상,하,좌,우로 퍼지고 지훈이도 상,하,좌,우로 움직일 수 있으므로 BFS를 사용해서 풀었다.

불과 지훈이는 매초마다 움직이므로 BFS함수에서 불이 먼저 퍼지고, 지훈이가 이동하도록 구현을 하였다.

불의 좌표는 fire 변수에 저장하고, 지훈이의 좌표는 person에 저장하여 person이 empty가 아닐 때까지 while 문을 반복하도록 하였다.

person이 empty가 되어 while을 빠져나온다면 지훈이가 탈출할 방법이 없는 것이므로  "IMPOSSIBLE"을 출력하면서 BFS 함수를 끝내도록 하였다,

또한 지훈이의 위치가 가장자리일 경우 탈출을 할 수 있으므로 visited의 저장된 값을 출력하고 BFS 함수를 끝내도록 하였다.

[코드]

시간 :88ms

#include <iostream>
#include <queue>
#define MAX 1001

using namespace std;

struct pos{
    int x,y;
};
     
queue <pos> fire;
queue <pos> person;

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

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

void BFS()
{
    while(!person.empty()){
        
        int fnum = fire.size();
        int pnum = person.size();
        
        while(fnum){
            fnum--;
            int x = fire.front().x;
            int y = fire.front().y;
            
            fire.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>=M||map[nx][ny]!=0)    continue;
                
                fire.push({nx,ny});
                map[nx][ny] = 1;
            }
        }
        
        while(pnum){
            pnum--;
            int x = person.front().x;
            int y = person.front().y;
            
            person.pop();
            if(x == 0 || y ==0 || x==N-1 || y ==M-1) {
                cout << visited[x][y];
                return;
            }
            
            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>=M||map[nx][ny]!=0||visited[nx][ny]!=0)    continue;
                
                person.push({nx,ny});
                visited[nx][ny] = visited[x][y]+1;
            }
        }
    }
    
    cout << "IMPOSSIBLE";
    return;
}

int main(void)
{
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            if(ch == '#')   map[i][j]=-1;
            else if(ch == 'F'){
                fire.push({i,j});
                map[i][j]=1;
            }
            else if(ch == 'J') {
                person.push({i,j});
                visited[i][j]=1;
            }
        }
    }
    BFS();
    
    return 0;
}