KiTFOx's Notepad 📝

문제

1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 나타낸다.

(1,1)에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸의 수를 구하는 프로그램 작성하시오.

입력 1

4 6
101111
101010
101011
111011

출력 1

15

코드

#include<iostream>
#include<queue>
#include<algorithm>
#define MAX 101

using namespace std;

int MAP[MAX][MAX];
int visited[MAX][MAX];
int dist[MAX][MAX];
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int N, M;
pair<int, int> startP, endP;

queue < pair<int, int>> Q;

void BFS() {
    
    Q.push(make_pair(startP.first, startP.second));

    dist[startP.first][startP.second]++;
    visited[startP.first][startP.second] = 1;

    while (!Q.empty()) {
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];


            if ((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)
                && MAP[ny][nx] == 1 &&!visited[ny][nx]) {
                visited[ny][nx] = 1;
                Q.push(make_pair(ny, nx));
                dist[ny][nx] = dist[y][x] + 1;
            }
        }
    }
    cout << dist[endP.first-1][endP.second-1];
}


void input() {
    string num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        for (int j = 0; j < M; j++) {
            MAP[i][j] = num[j]-'0';
        }
    }
}

int main() {

    cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

    int tmp;
    cin >> N>>M;
    startP = make_pair(0, 0);
    endP = make_pair(N, M);
    
    input();
    BFS();

    return 0;
}

*간단한 해설*

저 input 함수에서 cin을 통해 MAP을 받아옵니다.

주의할 점은 한 줄당 붙어있는 상태로 받아와서 cin으로 받은 다음 끊어서 저장해주어야합니다.

void input() {
    string num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        for (int j = 0; j < M; j++) {
            MAP[i][j] = num[j]-'0';
        }
    }
}

string으로 받은 다음 string에서 인자로 접근해주면 char 형이여서 char형을 int로 바꾸려면 '0'의 숫자를 빼주면 됩니다.

그런다음 BFS 탐색을 통해 최단 경로를 찾아주면 되는데 BOJ 6087번 레이저 통신과 문제가 매우 흡사합니다.

https://dana3711.tistory.com/90

다만 다른점은 목표 지점까지 가는데 걸리는 비용을 출력해야한다는 점입니다. 따라서

if ((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)&& MAP[ny][nx] == 1 &&!visited[ny][nx]) 
{
    visited[ny][nx] = 1;
    Q.push(make_pair(ny, nx));
    dist[ny][nx] = dist[y][x] + 1;
}

4방향 탐색을 할때 만약 맵 안에 있고((nx >= 0 &&nx < M) && (ny >= 0 && ny < N)), 그 칸이 이동할 수 있는 칸이라면(MAP[ny][nx] == 1) 해당 칸을 방문하지 않았을 때

해당 칸으로 자리를 이동하고 가는 비용을 +1 해줍니다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

거울을 설치하면 방향을 90도 회전시킬 수 있다.

*은 벽으로 뚫고 지나갈 수 없다.

거울을 최소로 설치하여서 처음 시작지점 C에서 끝지점 C에 도달할때까지 가야한다.

최소로 설치할 수 있는 거울 수를 출력하라

입력 1

7 8
.......
......C
......*
*****.*
....*..
....*..
.C..*..
.......

출력 1

3

코드

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

using namespace std;

//6087번 레이저 통신

char MAP[101][101];
int visited[101][101];
int w, h;
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

pair<int, int> startP, endP;
queue<pair<int,int>> cntDir;
queue < pair<int, int>> Q;
void BFS() {
    for (int i = 0; i < 4; i++) {
        Q.push(make_pair(startP.first, startP.second));
        cntDir.push(make_pair(0, i));
    }
    visited[startP.first][startP.second] = 0;

    while (Q.empty() == 0) {
        int y = Q.front().first;
        int x = Q.front().second;
        int cnt = cntDir.front().first;
        int dir = cntDir.front().second;
        Q.pop();
        cntDir.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];
            int nCnt = cnt;

            if (nx <0 || nx >= w || ny < 0 || ny >=h) continue;
            if (MAP[ny][nx] == '*') continue;
            if (dir != i) nCnt++;
            if (visited[ny][nx] >= nCnt) {
                visited[ny][nx] = nCnt;
                Q.push(make_pair(ny, nx));
                cntDir.push(make_pair(nCnt, i));
            }
        }
    }
    cout << visited[endP.first][endP.second];
}

void input() {
    bool isFirst = true;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'C') {
                (isFirst) ? startP = make_pair(i, j) : endP = make_pair(i, j);
                isFirst = false;
            }
            visited[i][j] = 10001;
        }
    }
}

int main() {

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> w >> h;
    
    input();
    BFS();


    return 0;
}

*간단한 해설*

void input() {
    bool isFirst = true;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 'C') {
                (isFirst) ? startP = make_pair(i, j) : endP = make_pair(i, j);
                isFirst = false;
            }
            visited[i][j] = 10001;
        }
    }
}

먼저 input 함수에서 cin을 통해 MAP을 받아옵니다.

그 중 만약 C가 입력되었다면 처음인지 아닌지를 판단해서 처음이라면 startP에 해당 위치를 넣고, 처음이 아니라면 endP에 해당 위치를 넣는다.

void BFS() {
    for (int i = 0; i < 4; i++) {
        Q.push(make_pair(startP.first, startP.second));
        cntDir.push(make_pair(0, i));
    }
    visited[startP.first][startP.second] = 0;

    while (Q.empty() == 0) {
        int y = Q.front().first;
        int x = Q.front().second;
        int cnt = cntDir.front().first;
        int dir = cntDir.front().second;
        Q.pop();
        cntDir.pop();
        //좌우위아래 탐색
        for (int i = 0; i < 4; i++) {
            int ny = y + arrow[i][0];
            int nx = x + arrow[i][1];
            int nCnt = cnt;

            if (nx <0 || nx >= w || ny < 0 || ny >=h) continue;
            if (MAP[ny][nx] == '*') continue;
            if (dir != i) nCnt++;
            if (visited[ny][nx] >= nCnt) {
                visited[ny][nx] = nCnt;
                Q.push(make_pair(ny, nx));
                cntDir.push(make_pair(nCnt, i));
            }
        }
    }
    cout << visited[endP.first][endP.second];
}

탐색을 시작할 위치인 startP의 위치를 4번 Q에 옮겨담습니다. 시작 위치에서 위,아래,왼쪽,오른쪽 방향을 탐색하는 방향을 저장해줍니다. 방향이 다르다면 거울의 갯수를 더해줘야하기 때문입니다. 

그 다음 Q가 빌때까지 while문을 돌립니다. Q의 첫번째 인자를 변수에 담고 좌우위아래 탐색을 시작합니다. 탐색에서 *인 벽을 만나거나 맵을 벗어나면 탐색을 건너뛰고, 만약 가던 방향과 현재 방향이 맞지 않다면 거울을 더해줍니다. 현재 방문한 위치에서의 거울을 사용한 갯수를 visited[][] 배열에 저장하기에 만약 사용한 갯수가 현재 카운트보다 높다면 최소로 사용해야하기때문에 변경해줍니다. 이것을 끝지점에 도달할때까지 계속 반복하여서 visited[끝지점.y][끝지점.x] 의 값을 출력하면 답이 됩니다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

입력 1

1000

출력 1

228875

코드

#include<iostream>
#include<cmath>

using namespace std;

//2749번 피보나치 수 3
//피사노 주기를 이용

long long arr[1500050];     //메모이제이션
int m = 1000000;            //나누는 수
int cycle;

int cycle_func() {
    int k=0,tmp=m;
    while (tmp > 1) {
        tmp /= 10;
        k++;
    }

    return 15 * pow(10, k - 1);
}

void pisano_fibo() {
    arr[0] = 0;
    arr[1] = 1;
    //파사노 주기에 의하여 1500000의 값들이 반복된 후에 다시 재 반복됨
    cycle = cycle_func();
    for (int i = 0; i < cycle; i++) {
        arr[i + 2] = (arr[i+1]+arr[i])%m;
    }
}

int main() {

    cin.tie(NULL);cout.tie(NULL);
    ios::sync_with_stdio(false);

    long long n;
    cin >> n;
    pisano_fibo();
    cout << arr[n % cycle];

    return 0;
}

*간단한 해설*

피사노 주기를 이용하여 푸는 문제이다 기본적으로 n의 범위가 1,000,000,000,000,000,000보다 작거나 같은 자연수 이기 때문에 기존에 쓰던 재귀함수를 이용하여서 푸는 방법은 시간이 매우 오래 걸리므로 쓸수가 없다. 따라서 피사노 주기를 통해 반복 주기를 찾고 그 주기동안의 피보나치 수열에서 m으로 나눈 나머지 값들을 배열에 저장한다. 그 후 저장한 배열에서 찾고자 하는 n번째가 주기에서 몇번째 숫자인지 찾아내서 해당 배열의 값을 출력하면 된다. 피사노 주기는

나누는 값을 M이라고 지칭했을 때,

M=10^k , cycle = 15 x 10^(k-1)

이다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

두 다각형이 주어졌을 때, 두 다각형의 민코프스키 합을 구하는 프로그램을 작성하시오. 만약 민코프스키 합이 여러 개의 다각형으로 이루어진다면 다음의 우선순위에 따라 하나의 다각형만을 구하도록 한다. 번호가 작은 것이 우선순위가 높은 것이다.

입력 1

3 3
0 0
1 0
1 1
0 1
0 0
1 0

출력 1

5
0 0
2 0
2 1
1 2
0 1

코드

#include<iostream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;

//2244번 민코프스키 합
//Convex Hull(CCW(Counter Clock Wise)) 사용

typedef pair<long long, long long> Point2f;
Point2f a[1010];
Point2f b[1010];

//counter clock wise : 좌회전하는지 판단
//벡터 AB와 벡터 AC의 CW/CCW
// 0보다 크면 반시계방향으로 도는 것, 0보다 작으면 시계방향으로 도는 것
//int에 1LL을 곱해주면 long long으로 형변환을 쉽게 할 수 있음
int ccw(Point2f a, Point2f b, Point2f c) {
    long long res = a.x * b.y + b.x * c.y + c.x * a.y;
    res -= b.x * a.y + c.x * b.y + a.x * c.y;
    if (res > 0) return 1;          //시계 반대방향
    if (res) return -1;             //시계 방향
    return 0;                           //평면상
}

long long dist(Point2f a, Point2f b) {
    long long dx = 1LL*a.x - b.x;
    long long dy = 1LL * a.y - b.y;
    return dx * dx + dy * dy;
}

int main() {

    vector<Point2f> arr;
    int aNum, bNum;
    int xTmp, yTmp;
    int pIdx = 0;
    cin >> aNum >> bNum;
    pIdx = aNum * bNum;
    for (int i = 0; i < aNum; i++) {
        cin >> xTmp >> yTmp;
        a[i].x = xTmp; a[i].y = yTmp;
    }
    for (int i = 0; i < bNum; i++) {
        cin >> xTmp >> yTmp;
        b[i].x = xTmp; b[i].y = yTmp;
    }
    //모든 가능성이 있는 점들 vector 제작
    for (int i = 0; i < aNum; i++) {
        for (int j = 0; j < bNum; j++) {
            arr.push_back(Point2f{ a[i].x + b[j].x,a[i].y + b[j].y });
        }
    }

    //arr의 최소 값을 찾아서 0번 자리와 바꿈(0번을 제일 작은 값으로 설정)
    swap(arr[0], *min_element(arr.begin(), arr.end()));
    //0번을 제외한 점들을 반시계 방향으로 정렬
    //[&]{}는 람다식으로써 해당 함수에따라서 sort를 할지 말지 결정함
    sort(arr.begin() + 1, arr.end(), [&](Point2f& a, Point2f& b) {
        int cw = ccw(arr[0], a, b);
        //cw가 0 이상이면 반시계 방향이고 true를 반환 0이면 false 반환, cw가 -1인 경우(시계 방향) if문을 들어오지 않음
        if (cw) return cw > 0;          
        return dist(arr[0], a) < dist(arr[0], b); //cw가 -1인 경우 기준점 arr[0]에서의 거리순으로 정렬
        });

    vector<Point2f> hull;
    for (int i = 0; i < arr.size();i++) {
        while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), arr[i]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(arr[i]);
    }
    cout << hull.size() << "\n";
    for (int i = 0; i < hull.size(); i++) {
        cout << hull[i].x << " " << hull[i].y << "\n";
    }

    return 0;
}

*간단한 해설*

convex hull로 구현하면 되는 문제이다.

convex hull은 주어진 점에서 외곽선을 이루는 점들을 찾는 알고리즘인데 민코프스키의 합 또한 공간의 합을 계산하는 것이기 때문에 convex hull 알고리즘을 사용하여 구현하면 된다.

코드의 핵심적인 부분은 https://justicehui.github.io/ioi/2019/05/21/BOJ2244/ 에서 따왔다.

몇가지 람다식이라던지 auto와 같은 것들이 나에게 어려워서 for문으로 바꾸거나 주석을 달아서 진행해보았다. 기존의 다른곳에서 찾아서 convex hull을 구현해서 넣어보았는데 예제를 넣어보았을 때는 출력 결과가 잘나왔었다. 하지만 백준에서 테스트 할때마다 

이러한 런타임 에러나 출력 초과가 나와서 뭐가 문제인지 몰라서 다른 분 블로그를 보고 참고해서 해보았는데 아마 sorting하는 과정에서 에러가 난게 아닐까 싶다..

convex hull 알고리즘에 대한 글은 https://kbw1101.tistory.com/50 여기 블로그에 아주 친절하게 설명되어 있다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하시오.

입력 1

5 6
. . . . . .
. . X X . .
. . X . . .
. X X X X .
1
3

출력 1

. . . . . .
. . . . . .
. . X X . .
. . X X . .
. X X X X .

코드

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define y first
#define x second
using namespace std;

//2933번 미네랄

//2차원 배열 선언
char arr[101][101];
int visited[101][101];      //dfs를 위한 방문 배열
int R, C;
vector<pair<int,int>> cluster;
int arrow[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

void DFS(int yIdx, int xIdx) {
    if (arr[yIdx][xIdx] == '.' || visited[yIdx][xIdx]) return;
    visited[yIdx][xIdx] = true;
    cluster.push_back({yIdx,xIdx});
    //좌우위아래 탐색
    for (int i = 0; i < 4; i++) {
        int ny = yIdx + arrow[i][0];
        int nx = xIdx + arrow[i][1];    
        if (nx >= 0 && nx < C && ny >= 0 && ny < R)
            DFS(ny, nx);
    }
}

void checkCluster() {
    memset(visited, 0, sizeof(visited));
    for (int a = 0; a < R; a++) {
        for (int b = 0; b < C; b++) {
            if (arr[a][b] == '.' || visited[a][b]) continue;
            cluster.clear();
            DFS(a,b);
            vector<int> low(C, -1);     //vector(컨테이너 크기, 각각 할당될 값)
            for (int z = 0; z < cluster.size(); z++) {
                pair<int, int> p= cluster[z];
                low[p.x] = max(low[p.x], p.y);
                arr[p.y][p.x] = '.';
            }

            //얼마나 밑으로 옮길지 i에 넣기
            int lowmove = R;
            for (int i, j = 0; j < C; j++) {
                if (low[j] == -1) continue;
                i = low[j];

                //'.'이 아닌경우, 탐색 높이가 높이보다 작은 경우
                while (i < R &&arr[i][j] == '.') {
                    i++;
                }
                lowmove = min(lowmove, i - low[j] - 1);
            }

            for (int i = 0; i < cluster.size(); i++) {
                pair<int, int> p = cluster[i];
                p.y += lowmove;
                arr[p.y][p.x] = 'x';
                visited[p.y][p.x] = true;
            }
        }
    }
    
}

void shoot(int orderNum,int height) {
    //왼쪽인지 오른쪽인지 판단
    height = R - height;
    if (orderNum % 2 == 0) {
        for (int i = 0; i < C; i++) {
            if (arr[height][i] == 'x') {
                arr[height][i] = '.';
                break;
            }
        }
    }
    else {
        for (int i = C-1; i >= 0; i--) {
            if (arr[height][i] == 'x') {
                arr[height][i] = '.';
                break;
            }
        }
    }
    
    checkCluster();
}

int main() {
    
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);


    cin >> R >> C;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> arr[i][j];
        }
    }
    int N,height=0;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> height;
        shoot(i, height);
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cout << arr[i][j];
        }
        cout << "\n";
    }

    return 0;
}

*간단한 해설*

checkCluster() 함수 부분은 https://100100e.tistory.com/152 이 블로그 분의 글을 참고하여서 제작하였다. 제일 나랑 생각이 비슷하기도 했고 알기 쉽게 작성되어있어서 좋았다. checkCluster() 부분을 자세하게 설명해볼까 싶다.

 memset(visited, 0, sizeof(visited));
    for (int a = 0; a < R; a++) {
        for (int b = 0; b < C; b++) {

checkCluster는 부메랑을 던진 후에 떨어지는 클러스터들을 판단하기 위한 함수로써 실행된다. 따라서 DFS를 다시 사용하려면 visited 배열을 초기화 시켜줘야한다. 그를 위해 memset 함수를 이용하였다. 나머지 for문은 R x C 크기의 맵을 for문을 통해 돌린다.

if (arr[a][b] == '.' || visited[a][b]) continue;
cluster.clear();
DFS(a,b);

그 다음에는 해당 맵의 칸이 . 으로 비어있는 칸이거나 이미 방문한 배열일 경우 그대로 밑의 계산을 하지 않고 넘어간다. 그렇지 않은 경우 DFS 함수를 통해서 해당 클러스터를 기준으로 좌우위아래를 탐색해서 cluster 벡터에 넣는다.

vector<int> low(C, -1);     //vector(컨테이너 크기, 각각 할당될 값)
for (int z = 0; z < cluster.size(); z++) {
    pair<int, int> p= cluster[z];
    low[p.x] = max(low[p.x], p.y);
    arr[p.y][p.x] = '.';
}

그 후에  low 라는 땅에 가장 가까운 클러스터를 저장하는 벡터 배열을 선언한다. low(C,-1) 이렇게 선언하면 C 크기 만큼을 -1의 값으로 할당한다는 말이다. 그 다음 for문을 통해서 저장된 cluster만큼 돌려주고 만약 해당 클러스터의 높이 값인 p.y 값이 만약에 기존에 저장된 높이 값인 low[p.x]와 비교했을 때 큰 값을 low[p.x]에 저장해준다. 저장한 다음에는 해당 값은 나중에 다시 떨어진 클러스터 값으로 변경해줄 것임으로 미리 .으로 변경 시켜준다.

int lowmove = R;
for (int i, j = 0; j < C; j++) {
    if (low[j] == -1) continue;
    i = low[j];

    //'.'이 아닌경우, 탐색 높이가 높이보다 작은 경우
    while (i < R &&arr[i][j] == '.') {
        i++;
    }
    lowmove = min(lowmove, i - low[j] - 1);
}

얼만큼 밑으로 옮길지 계산하는 부분이다. lowmove 변수에는 가장 많이 내려갈 수 있는 값 높이 R값을 넣은 다음 비교해가면서 작으면 변경하는 형식이다. if(low[j]==-1) continue; 의 경우 땅에 가장 가까운 클러스터가 없는 경우에는 연산을 하지 않고 넘어간다. 그렇지 않을 경우 i = low[j];로 땅에 가장 가까운 클러스터의 높이를 넣는다. 그 후 while문을 통해서 만약 해당 좌표의 클러스터가 빈공간인 경우 내려가야할 칸의 값인 i를 ++해준다. 해당 while문이 긑나고 나면 min 함수를 통해 기존의 lowmove 값과 i-low[j]-1을 비교한다. arr[i][j]의 경우 아까 위에서 .으로 만들어놓았기 때문에 한개가 더 세어진다. 따라서 내려가야할 칸의 수 i 에서 -1을 한 다음 기존 높이인 low[j]를 빼주면 내려가야할 칸의 갯수가 나온다.

for (int i = 0; i < cluster.size(); i++) {
                pair<int, int> p = cluster[i];
                p.y += lowmove;
                arr[p.y][p.x] = 'x';
                visited[p.y][p.x] = true;
}

마지막으로 클러스터의 갯수 만큼 for문을 돌려서 lowmove 만큼 모든 클러스터를 옮겨준다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력 1

7
1
5
2
10
-99
7
5

출력 1

1
1
2
2
2
2
5

코드

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

using namespace std;

//1655번 가운데를 말해요
//최소힙, 최대힙 사용
int main() {
    
    cin.tie(NULL);
    cout.tie(NULL);

    int N,temp;
    priority_queue<int> max;        //최대힙       우선순위 큐는 default로 less<in>를 사용
    priority_queue<int,vector<int>,greater<int>> min;       //최소힙
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> temp;

        (max.size() == min.size()) ? max.push(temp) : min.push(temp);

        if (!max.empty() && !min.empty()&& max.top() > min.top()) {
            //중간 값의 순서가 달라진다면 값 바꾸기
            int maxVal, minVal;
            maxVal = max.top();
            minVal = min.top();
            max.pop();
            min.pop();
            max.push(minVal);
            min.push(maxVal);
        }

        cout << max.top()<<"\n";
    }
    
    return 0;
}

*간단한 해설*

여러가지 알고리즘 중에서 무엇을 왜 쓰는지가 핵심인데 여기서는 최소힙, 최대힙을 사용한다.

그 이유는 힙은 여러개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르기 때문에 여기서 사용하면 빠른 연산이 가능하다.

힙은 일반적으로 완전 이진트리이므로 배열을 이용하여 구현한다.

최대 힙은 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다. 

최소 힙은 루트 노드로 올라갈수록 값이 작아지는 구조이다.

이 문제의 경우 배열을 반틈으로 나누어서 한쪽은 최소 힙, 한쪽은 최대 힙을 사용하여 빠르게 연산하는 문제이다. 이 경우 priority_queue를 이용하여 구현할 수 있다. priority_queue는 힙을 이용하여 구현되어 있고 옵션을 이용하여 greater<int> 및 less<int>를 이용하여 위와같은 최소힙, 최대힙 구조를 만들 수 있다. 따라서 이를 통해서 중간값을 찾는 것이라 반틈을 나누어서 오름차순, 내림차순으로 정렬되는 최소힙, 최대힙을 이용하면 빠르게 통과하는 코드를 만들 수 있다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.
2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.
3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다.

사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 계산하라.

*처음 봤을때 턴에 관한 개념이 잘 생성되지 않았는데 턴은 무조건 한번만 실행되는 시스템이다.

입력 1

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

출력 1

9

입력 2

10
4
1 2
1 3
1 4
1 5
4
8 D
10 D
11 D
13 L

출력 2

21

입력 3

10
5
1 5
1 3
1 2
1 6
1 7
4
8 D
10 D
11 D
13 L

출력 3

13

코드

#include<iostream>
//#include<Windows.h>
#include<deque>
#include<vector>

using namespace std;

int main() {
    
    int N, K,L;     //N : 보드의 크기, K : 다음 줄에 사과의 개수, L : 뱀의 방향 변환 횟수
    int column, row;
    int currentX=0, currentY=0;
    int arrIdx = 0, turnIdx=0;          //arrIdx : 방향배열 인덱스, turnIdx : 방향 회전배열 인덱스
    int arrow[4][2] = { {1,0},              //오른쪽
                        {0,1},              //아래
                        {-1,0},             //왼쪽
                        {0,-1} };           //위
    deque<vector<int>> body;

    cin >> N;

    //해당 배열만큼 2차원 행렬 만들기
    int** board = new int* [N];
    for (int i = 0; i < N; i++) {
        board[i] = new int[N];
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = 0;
        }
    }

    board[0][0] = 1;
    vector<int> point;
    point.push_back(0);
    point.push_back(0);
    body.push_back(point);

    cin >> K;
    for (int i = 0; i < K; i++) {
        cin >> row >> column;
        board[row-1][column-1] = 2;
    }
    cin >> L;
    int* turn = new int[L];
    int* direction = new int[L];
    int lValue;
    char rValue;

    for (int i = 0; i < L; i++) {
        cin >> lValue >> rValue;
        turn[i] = lValue;
        direction[i] = rValue;
    }

    int time = 0;

    while (time < 10000) {
    
        /* {
            Sleep(1000);
            system("cls");

            cout << "Time :" << time+1 << endl;
            //출력해서 확인하기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    cout << board[i][j] << " ";
                }
                printf("\n");
            }
        }*/
        
        if (time == turn[turnIdx] && time != 0) {
            if (direction[turnIdx] == 'D') {
                arrIdx++;
            }
            if (direction[turnIdx] == 'L') {
                arrIdx--;
            }
            turnIdx++;
        }


        if (arrIdx > 3)
            arrIdx = arrIdx % 4;
        if (arrIdx < 0) {
            arrIdx = 4 + arrIdx;
        }

        //오른쪽으로 이동하는 것
        currentX += arrow[arrIdx][0];
        currentY += arrow[arrIdx][1];
       
        if ((currentX < 0 || currentX >= N) ||(currentY < 0 || currentY >= N))
            break;
        if (board[currentY][currentX] == 1)
            break;

        if (board[currentY][currentX] == 2) {
            //만약 사과가 있다면
            point.clear();
            point.push_back(currentY);
            point.push_back(currentX);
            body.push_front(point);

            for (size_t i = 0; i < body.size(); i++) {
                board[body[i][0]][body[i][1]] = 1;
            }
        }
        else {
            //맨끝의 값의 자리를 0으로 바꿔주기
            board[body.back()[0]][body.back()[1]] = 0;
            //처음의 값을 뒤로 밀어주기

            for (size_t  i = body.size() - 1; i >0 ; i--) {
                int temp = body[i-1][0];
                body[i][0] = temp;
                temp = body[i-1][1];
                body[i][1] = temp;
            }

            //첫번째 머리움직이기
            body[0][0]= currentY;
            body[0][1]= currentX;

            for (size_t i = 0; i < body.size(); i++) {
                board[body[i][0]][body[i][1]] = 1;
            }
        }

        time++;
    }

    cout << time + 1;

    //할당 해제
    for (int i = 0; i < N; i++)
        delete[] board[i];

    return 0;
}

*간단한 해설*

턴에 관한 개념이 처음에 잡히지 않아서 반복적으로 생성되는 줄 알고 시간을 많이 사용했다.

    Sleep(1000);
    system("cls");

    cout << "Time :" << time+1 << endl;
    //출력해서 확인하기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j] << " ";
        }
        printf("\n");
    }

이부분의 주석처리를 빼면 어떻게 실행되는지 확인해볼 수 있다.

예제의 3개의 출력 과정은 아래와 같다.

0이 빈칸이고 1은 뱀, 2는 사과이다.

사실 여기까지 와서 예제를 넣어보았을 때 제출을 하니까 틀린것으로 나왔었다.

테스트 케이스를 여러개 해보지 않아서 그런데 반례 케이스를 모아놓은 사이트를 찾았다.

https://www.acmicpc.net/board/view/56469

나의 경우 맨 처음 반례 케이스의 5번째까지 통과를 하니 통과를 할 수 있었다.

다른 분의 알고리즘을 찾아보니 이분꺼가 깔끔하게 정리되어 있었다.

내 코드는 for문을 많이 쓰는데 for문을 많이 쓰지 않도록 생각하는 힘을 좀 더 길러야겠다.

https://velog.io/@nacean/%EB%B0%B1%EC%A4%803190-%EB%B1%80-C-%ED%92%80%EC%9D%B4

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다.

1. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 
2. 같은 눈이 2개만 나오는 경우에는 1,000원+(같은 눈)×100원의 상금을 받게 된다. 
3. 모두 다른 눈이 나오는 경우에는 (그 중 가장 큰 눈)×100원의 상금을 받게 된다.  

예를 들어, 3개의 눈 3, 3, 6이 주어지면 상금은 1,000+3×100으로 계산되어 1,300원을 받게 된다. 또 3개의 눈이 2, 2, 2로 주어지면 10,000+2×1,000 으로 계산되어 12,000원을 받게 된다. 3개의 눈이 6, 2, 5로 주어지면 그중 가장 큰 값이 6이므로 6×100으로 계산되어 600원을 상금으로 받게 된다.

3개 주사위의 나온 눈이 주어질 때, 상금을 계산하는 프로그램을 작성 하시오.

입력 1

3 3 6

출력 2

1300

입력 2

2 2 2

출력 2

12000

입력 3

6 2 5

출력 3

600

코드

#include<iostream>

using namespace std;

bool equals(int rValue,int lValue, int* outValue) {
    if (rValue == lValue) {
        *outValue = rValue;
        return true;
    }
    else
        return false;
}

int main() {
    
    int firstDice, secondDice, thirdDice;
    int value=0;
    cin >> firstDice >> secondDice >> thirdDice;
    
    if (firstDice == secondDice&& secondDice == thirdDice) {     //만약 세개가 같은 값이면
        cout << 10000 + firstDice * 1000;
    }
    else if (equals(firstDice,secondDice,&value)
        || equals(secondDice, thirdDice, &value)
        || equals(firstDice, thirdDice, &value)) {     //만약 두개가 같은 값이면
        cout<<1000+ value *100;
    }
    else {
        //그 중 가장 큰눈
        value = max(max(firstDice, secondDice), thirdDice);
        cout << value * 100;
    }

    return 0;
}

*간단한 해설*

단계별로 풀어보기에서 if문 주제로 추가 분류된 문제여서 풀어보았다.

말그대로 간단하게 if-else if-else문을 통하여 총 3가지로 분류하면 된다.

 if (firstDice == secondDice&& secondDice == thirdDice)

이부분은 첫번째 주사위와 두번째 주사위의 숫자가 같고 두번째 주사위와 세번째 주사위의 숫자가 같을때, 'A와 B가 같고 B와 C가 같으면 A와 C는 같다'라는 공리를 통해 두가지의 원리가 true값을 반환한다면 자연스럽게 세 가지의 값이 모두 같음을 의미한다.

bool equals(int rValue,int lValue, int* outValue) {
    if (rValue == lValue) {
        *outValue = rValue;
        return true;
    }
    else
        return false;
}

equals()함수의 경우 else if문 안에서 만약 두개가 같은 값이면 value에 그 값을 집어넣어서 출력할때 쓸수 있게끔 제작하였다. 그중 outValue만 포인터를 사용한 이유는 rValue와 lValue의 경우 얕은 복사를 통해 숫자값만 들고와서 비교하면 되지만 outValue의 경우 해당 값을 넣어줘야하기때문에 깊은 복사가 필요해서 포인터를 사용하였다.

else {
        //그 중 가장 큰눈
        value = max(max(firstDice, secondDice), thirdDice);
        cout << value * 100;
    }

마지막으로 세개의 값이 모두 다른 경우 max()함수를 통해 먼저 첫번째 수와 두번째 수의 크기를 비교하고, 그 다음 비교한 큰 값과 세번째 수의 값을 비교하여 제일 큰 수를 value에 넣어서 출력하도록 하였다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

입력

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

1 2 4 3
1 2 3 4

코드

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

// 1260번 DFS와 BFS

//깊이 우선 탐색
void dfs(vector<int> inputGraph[], bool *visited,int index) {
	visited[index] = true;		//방문했음을 표시
	cout << index<<" ";
	//dfs 탐색 순서
	int grphSize = inputGraph[index].size();
	for (int i = 0; i < grphSize; i++) {
		int connectIdx = inputGraph[index][i];
		if (!visited[connectIdx])
			dfs(inputGraph, visited, connectIdx);
	}
}

//너비 우선 탐색
void bfs(vector<int> inputGraph[],bool *visited,int index) {
	queue<int> que;
	que.push(index);
	visited[index] = true;
	//bfs 탐색 순서
	while (!que.empty()) {
		int visitIdx = que.front();
		que.pop();
		cout << visitIdx<<" ";
		int grphSize = inputGraph[visitIdx].size();
		for (int i = 0; i < grphSize; i++) {
			//방문한 Idx와 연결된 원소들을 que에 넣기
			int connectIdx = inputGraph[visitIdx][i];
			if (!visited[connectIdx]) {		//만약 연결된 원소를 방문하지 않았다면
				que.push(connectIdx);		//방문할 노드로 선정
				visited[connectIdx] = true;
			}
		}
	}
	
	
}

int main() {

	int N, M, V;		//정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호

	cin >> N >> M >> V;

	int size = N + 1;
	//N개만큼의 배열 만들기
	bool* visited = new bool[size] {false, };			//방문 유무를 저장하는 배열
	vector<int>* graph = new vector<int>[size];
	graph->push_back(1);

	for (int i = 0; i < M; i++) {
		int origin, connect;
		cin >> origin >> connect;
		graph[origin].push_back(connect);
		graph[connect].push_back(origin);
	}

	//정렬
	for (int i = 0; i < size; i++) {
		sort(graph[i].begin(),graph[i].end());
	}

	dfs(graph,visited, V);
	cout << endl;
	visited = new bool[size]{ false, };		//방문유무를 다시 초기화해줌(재사용 위해)
	bfs(graph, visited,V);

	delete [] visited;		//메모리 해제 
	//vector 메모리 해제
	graph->clear();
	vector<int>().swap(*graph);

	return 0;
}

*간단한 해설*

DFS와 BFS를 구현하였다. DFS는 모든 노드를 탐색하도록 작성하였고, BFS는 연결된 노드를 통해서 해당 노드와 연결된 노드 중 방문하지 않은 노드만 다시 탐색해서 탐색이 끝나면 종료되도록 작성하였다. DFS와 BFS의 경우 

https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

해당 포스팅을 통해 자세하게 배울 수 있었다. DFS와 BFS에 대해 알고싶으면 위의 블로그를 참조하면 좋을듯하다.

for (int i = 0; i < M; i++) {
    int origin, connect;
    cin >> origin >> connect;
    graph[origin].push_back(connect);
    graph[connect].push_back(origin);
}

연결된 노드들을 입력받는 과정에서 연결된 2개를 입력 받을시 서로 각자의 노드에 연결 정보를 입력시키도록 한다.

//정렬
for (int i = 0; i < size; i++) {
    sort(graph[i].begin(),graph[i].end());
}

입력시킨 정보들을 sort를 통해 정렬을 시켜준다. 정렬을 하지 않으면 원하는대로 결과값이 나오지 않기 때문에 정렬을 꼭 해준다.

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

출력

1
2
2
0
1
2
-1
0
1
-1
0
3

코드

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

// 10845번 큐

//큐 구현
class QueueS {
public:
	int front;
	int back;
	int size;
	int *values;		//모든 값들을 담은 배열을 가리키는 포인터

	//생성자
	QueueS() {
		size = 10001;		//큐의 사이즈 
		values = new int[size];
		front = 0;
		back=0;
	}
	//소멸자
	~QueueS() {
		delete[] values;
	}

	void push(int data) {
		if ((back+1)%size!=front) {
			values[back] = data;
			back = (back + 1) % size;
		}
	}

	void pop() {
		front = (front + 1) % size;
	}

	bool empty() {
		if (back == front)
			return true;
		else
			return false;
	}
};

QueueS st;

void getNumSize(string str) {
	int temp;

	if (str == "back") {
		if (st.back - st.front != 0) {
			cout << st.values[st.back - 1] << "\n";
		}
		else cout << "-1\n";
	}
	else if (str == "front") {
		if (st.back - st.front != 0) {
			cout << st.values[st.front] << "\n";
		}
		else cout << "-1\n";
	}
	else if (str == "size") {
		cout << st.back-st.front << "\n";
	}
	else if (str == "empty") {
		cout << ((st.back - st.front==0)?true:false) << "\n";
	}
	else if (str == "pop") {
		if (st.back - st.front!=0) {
			cout << st.values[st.front] << "\n";
			st.pop();
		}
		else {
			cout << "-1\n";
		}
	}
	else if (str == "push")
	{
		cin >> temp;
		st.push(temp);
	}
}

int main() {

	int n;
	string str;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str;
		getNumSize(str);
	}

	return 0;
}

*간단한 해설*

큐를 클래스를 이용하여 구현하였다. 큐 클래스의 front,back은 일종의 맨 앞의 index 번호를 말하는 것이고, back은 맨 뒤의 index번호를 말하는 것이다. 그리고 int* values를 통해서 입력 받은 값들을 back을 늘려가면서 저장하였다.

C 구조체와 C++의 queue 라이브러리를 이용하여 구현하신 분도 있었다.

https://blockdmask.tistory.com/119

내 코드는 헤더를 추가하지 않는데 시간이 너무 길어서.. 블로그 글을 참고하다 보니 아무래도 cout문제도 있을 것 같아서 printf로 한번 다 바꿔보았다.

그렇게까지 영향을 준건 아닌가보다 싶어서 좀 더 찾아보니

https://coding-insider.tistory.com/entry/cin-cout-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EC%86%8D%EB%8F%84-%EB%B9%A0%EB%A5%B4%EA%B2%8C%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95

cin의 속도가 생각보다 엄청 느리다는것! 

ios_base :: sync_with_stdio(false); 
cin.tie(NULL); 
cout.tie(NULL);

이 코드를 추가해주면 빨라진다고는 하나 scanf,printf와 같이 사용하면 안되고 싱글쓰레드 영역에서만 사용 가능해서 실제 코드 영역에서는 사용하는 것을 지양하라고 한다.

일단 싱글 쓰레드 영역이니 쟤들을 추가해서 한번 돌려보았다.

속도는 빨라졌지만 메모리는 늘어났다.. 그러면 scanf,printf로 다 바꿔보겠다.

결과적으로는 메모리도 줄어들었다. 아무래도 scanf,printf로 출력하는 방식으로 앞으로도 써야겠다.

코드(scanf,printf)

#include<iostream>
#include<string.h>
using namespace std;

// 10845번 큐
//큐 구현
class QueueS {
public:
	int front;
	int back;
	int size;
	int *values;		//모든 값들을 담은 배열을 가리키는 포인터

	//생성자
	QueueS() {
		size = 10001;		//큐의 사이즈 
		values = new int[size];
		front = 0;
		back = 0;
	}
	//소멸자
	~QueueS() {
		delete[] values;
	}

	void push(int data) {
		if ((back + 1) % size != front) {
			values[back] = data;
			back = (back + 1) % size;
		}
	}

	void pop() {
		front = (front + 1) % size;
	}

	bool empty() {
		if (back == front)
			return true;
		else
			return false;
	}
};

QueueS st;

void getNumSize(char str[]) {
	int temp;

	if (!strcmp(str, "back")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.back - 1]);
		}
		else printf("-1\n");
	}
	else if (!strcmp(str,"front")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.front]);
		}
		else printf("-1\n");
	}
	else if (!strcmp(str ,"size")) {
		printf("%d\n", st.back - st.front);
	}
	else if (!strcmp(str,"empty")) {
		printf("%d\n", ((st.back - st.front == 0) ? true : false));
	}
	else if (!strcmp(str, "pop")) {
		if (st.back - st.front != 0) {
			printf("%d\n", st.values[st.front]);
			st.pop();
		}
		else {
			printf("-1\n");
		}
	}
	else if (!strcmp(str,"push"))
	{
		scanf("%d", &temp);
		st.push(temp);
	}
}

int main() {

	int n;
	char str[6];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", str);
		getNumSize(str);
	}

	return 0;
}

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내느 프로그램을 작성하시오. 대,소문자 구분 X

예제 입출력

입력

Mississipi

출력

?

코드

*간단한 해설*

알파벳갯수만큼의 배열을 만들어서 문자열을 체크하여 갯수만큼 저장한 후 45~56번 라인에서 제일 큰 알파벳을 뽑는다

나머지는 주석을 통해 설명해놓았다

이 코드보다 훨씬 빠른 방법이 있지 않을까 싶긴하다

*메모리*

2840KB

*시간*

36ms

*언어*

C++14

*코드길이*

1878B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

문자열 S를 입력받은 후, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오.

즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다.

입력

첫째 줄에 테스트 케이스의 개수 T(1≤ T ≤ 1000)가 주어진다. 각 테스트 케이스는 반복 횟수 R(1 ≤ R ≤ 8), 문자열 S가 공백으로 구분되어 주어진다. S의 길이는 적어도 1이며, 20글자를 넘지 않는다. 

예제 입출력

입력

출력

코드

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.

입력

첫번재 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

예제 입출력

입력 : baekjoon

출력 : 1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

코드

*간단한 해설*

4~7번 라인 : array배열(출력 배열)을 -1로 먼저 초기화 해줌

9~11번 라인 : for문을 100번 돌리는데 만약 입력된 값이 없다면 for문을 빠져나오도록 break를 적용함

12~13번 라인 : 만약 입력된 값이 있다면 해당 값을 static_cast를 이용하여 int 값을 변경해주고 해당되는 array자리가 -1상태(즉, 먼저 확인되지 않은 상태)라면 해당 배열의 자리에 i(몇번째 수인지 알려주는 idx)를 삽입해줌

P.S

if(word[i]==NULL)로 쓰니까 warning 문구가 떳다. 아마 컴파일러에 따라서 NULL이라는 예약어가 없을 수 있기 때문에 '\0' 으로 수정하였다.

*메모리*

2016KB

*시간*

0ms

*언어*

C++17

*코드길이*

442B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.

출력

입력으로 주어진 숫자 N개의 합을 출력한다.

코드

*간단한 해설*

int로 받을 시 공백없이 받을 수 없어서 char 배열로 받았다

for문을 이용해서 배열을 한개씩 받아온다

받아온 결과는 다음과 같을 것이다

10번째 줄에서 sum은 한개씩 받아온 char를 static_cast<int>를 통해서 int로 바꾸고 0의 아스키 코드 값인 48을 빼준 값을 더해준다

*메모리*

1984KB

*시간*

0ms

*언어*

C++14

*코드길이*

416B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

알파벳 소문자, 대문자, 숫자 0~9중 하나가 주어졌을 때, 주어진 글자의 아스키 코드값을 출력하는 프로그램을 작성하시오

입력

알파벳 소문자 대문자, 숫자 0~9중 하나가 첫째 줄에 주어진다

출력

입력으로 주어진 글자의 아스키 코드 값을 출력한다

코드

*간단한 해설*

문자를 받아서 해당하는 아스키코드의 번호를 출력하는 문제이다

C++에서는 해당하는 숫자로 변환시켜주는 static_cast<int>() 함수를 쓰면 간단하게 변경할 수 있다

이 함수를 쓰게 되면 컴파일러에서 타입 오류를 측정할 수 있고 업캐스팅, 다운캐스팅을 제외한 포인터의 형 변환이 불가능하다는 장점이 있다

*메모리*

1984KB

*시간*

0ms

*언어*

C++14

*코드길이*

146B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다

등차수열은 연속된 두 개 수의 차이가 일정한 수열을 말한다

N이 주어졌을 대, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오

입력

첫째 줄에 1000보다 작거나 같은 자연수 N이 주어진다

출력

첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다

코드

*간단한 해설*

한수라는 용어 자체가 너무 이해가 안되서 헤매게 된 문제이다

한수는 예를 들자면 1자리 수인 1은 한 개 밖에 없기 때문에 무조건 한수이다(등차수열을 비교할 대상이 없기 때문)

2자리 수인 10,11,12 같은 경우 (1,0) (1,1) (1,2) 이렇게 나누어 진다

등차수열은 각각 -1,0,1 로 되고 무조건 한수이다(비교할 대상이 없기 때문)

그래서 3자리 수 이하는 모두 다 한수이기 때문에 12번줄에 보면 100부터 for문이 시작된다

while문이 돌 동안 123의 경우 123%10=3 (일의 자릿수 구하기) 그 다음 123/10=12 을 한 후 12%10=2(십의 자릿수)

이런식으로 반복하여 각 자릿수를 구한다

자릿수를 구한 다음 그 전에 구한 자릿수를 빼주어 등차수열의 증감값을 구하고 그 값이 끝날때까지 동일하다면

isHanSu=true로 유지한다

*메모리*

1984KB

*시간*

0ms

*언어*

C++14

*코드길이*

777B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

셀프 넘버는 1949년 인도 수학자 D.R Kaprekar가 이름을 붙였다

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자

예를 들어 d(75)=75+7+5=87이다

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n),d(d(n)),d(d(d(n))),....과 같은 무한 수열을 만들 수 있다

생성자가 없는 숫자를 셀프 넘버라고 한다

100보다 작은 셀프 넘버는 1,3,5,7,9,20,31,42,53,64,75,86,97 총 13개가 있다

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다

출력

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 즐가하는 순서로 출력한다

코드

*간단한 해설*

이 문제의 경우 재귀함수를 만들 수 있냐를 물어보는 문제이다

10000개의 bool 배열을 만든 후 셀프 넘버를 체크하는 함수에서 만약 해당 숫자가 나온다면 그 자리에 true를 넣는다

모든 체크가 끝난 후 false 값을 가진 배열의 자리 값을 출력하면 된다

예외 체크 같은 경우 셀프 넘버를 계산하는 과정에서 10000을 넘는 경우와 idx가 10000을 넘는 경우 두 개이다

그림과 같은 프로세스를 거쳐서 진행된다

지금 보니 이미 true 값을 가지고 있는 idx들은 체크 하지 않는 것이 더 계산에 효율적일 것 같다

*메모리*

1984KB

*시간*

20ms

*언어*

C++14

*코드 길이*

484B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

정수 n개가 주어졌을 때, n개의 합을 구하는 함수를 작성하시오

C++, C++11, C++14, C++17, C++ (Clang), C++11 (Clang), C++14 (Clang), C++17 (Clang): long long sum(std::vector<int> &a);

• a: 합을 구해야 하는 정수 n개가 저장되어 있는 배열 (0 ≤ a[i] ≤ 1,000,000, 1 ≤ n ≤ 3,000,000)
• 리턴값: a에 포함되어 있는 정수 n개의 합

코드 (더보기를 눌러 확인하세요)

*메모리*

13704B

*시간*

4ms

*언어*

C++ 14

*코드 길이*

152B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

반의 갯수를 입력받고 반의 학생수를 입력받고 각각 학생들의 점수를 입력받은 후 그들의 평균을 구해서 반에서 평균을 넘는 학생들의 비율을 출력하라

출력

각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다

입력

5

5
5 50 50 70 80 100
7 100 95 90 80 70 60 50
3 70 90 80
3 70 90 81
9 100 99 98 97 96 95 94 93 91

출력

40.000%

57.143%

33.333%

66.667%

55.556%

코드 (더보기를 눌러 확인하세요)

*메모리*

1984B

*시간*

0ms

*언어*

C++ 14

*코드 길이*

532B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

O는 문제를 맞은 것이고, X는 문제를 틀린 것이다 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다 예를 들어 "OOXXOXXOOO" 의 점수는 1+2+0+0+1+0+0+1+2+3=10점이다 

OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오

출력

각 테스트 케이스마다 점수를 출력한다

입력

5

OOXXOXXOOO

OOXXOOXXOO

OXOXOXOXOXOXOX

OOOOOOOOOO

OOOOXOOOOXOOOOX

출력

10

9

7

55

30

코드

#include <iostream>

int main() {
    int N,sum=0,comboStack=0,idx=0;
    bool combo=false;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        char temp[80];   //scanf는 string을 받을 수 없기 때문에
        scanf("%s",&temp);    
        while(temp[idx]!='\0'){
            if(temp[idx]=='O') {
                if(combo){ sum+=comboStack;} //콤보일 경우 추가 점수
                else {combo=true;}
                comboStack++;
                sum++;        //O일때 기본적으로 추가되는 점수
            
            }
            else if(temp[idx]=='X')
            {
                combo=false;
                comboStack=0;
            }
            idx++;
        }
        printf("%d\n",sum);
        sum=0;
        idx=0;
        comboStack=0;
    }
    return 0;
}

*간단한 해설*

이 글은 게임의 콤보 시스템과 유사하다. 문자열을 받아서 문자열이 null('\0')이 아닐때까지 실행해서 결과값을 도출한다. 콤보일경우 comboStack의 값을 추가로 더해주도록 하며 O인 경우에는 comboStack을 ++로 쌓아주도록 한다. 한줄의 카운트가 다 끝난 경우 27~29의 값을 보면 index,sum(합)과 comboStack을 초기화 시켜주어야 한다.

*메모리*

1984B

*시간*

0ms

*언어*

C++ 14

*코드 길이*

607B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

세준이는 자기 점수 중에 최댓값을 골랐다 그리고 나서 모든 점수를 점수/M*100으로 고쳤다

새로 계산한 세준이의 성적의 평균을 구하는 프로그램을 작성하시오

출력

첫째줄에 새로운 평균을 출력한다 실제 정답과 출력값의 절대오차 또는 상대오차가 1/100 이하이면 정답이다

입력

3

40 80 60

출력

75.0

코드 (더보기를 눌러 확인하세요)

*메모리*

1984B

*시간*

0ms

*언어*

C++ 14

*코드 길이*

299B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.

출력

첫째 줄에, 42로 나누었을 때, 서로 다른 나머지가 몇 개 있는지 출력한다

입력

39               (39)

40               (40)

41               (41)

42               (0)

43               (1)

44               (2)

82               (40)

83               (41)

84               (0)

85               (1)

출력

6

코드 (더보기를 눌러 확인하세요)

*메모리*

1984B

*시간*

0ms

*언어*

C++

*코드 길이*

589B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

세 개의 자연수 A,B,C가 주어질 때 A x B x C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오

출력

첫째 줄에는 A x B x C의 결과에 0이 몇 번 쓰였는지 출력한다. 1부터 9까지의 숫자가 각각 몇 번 쓰였는지 차례로 한 줄에 하나씩 출력한다

입력

150

266

427

출력

3

1

0

2

0

0

0

2

0

0

코드 (더보기를 누러 확인하세요)

*메모리*

1984B

*시간*

0ms

*언어*

C++ 14

*코드 길이*

499B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*

문제

주문할 때, 자신이 원하는 햄버거와 음료를 하나씩 골라, 세트로 구매하면, 가격의 합계에서 50원을 뺀 가격이 세트메뉴 가격이 된다 햄버거는 총 3종류, 음료수는 총 2종류가 있다

햄버거와 음료의 가격이 주어졌을 때, 가장 싼 세트 메뉴의 가격을 출력하는 프로그램을 작성하시오

입력

800

700

900

198

330

출력

848

입력

1999

1999

100

189

100

출력

150

코드 (더보기를 눌러 확인하세요)

*메모리*

1984B

*시간*

0ms

*언어*

C++ 14

*코드 길이*

428B

*이 방법만이 맞는 정답은 아닙니다.

훨씬 좋고 빠른 다른 알고리즘을 구현할 수 있습니다.

알고리즘 공부하시는 분들 화이팅! '0'/*