코딩생존기

https://school.programmers.co.kr/learn/courses/30/lessons/169198

각 좌표에 따른 조건을 나눈 다음 거리값 계산을 피타고라스를 통해 하면 된다.

거리값의 계산을 수직거리의 제곱과 수평거리의 제곱을 더해주면 된다.

#include <cmath>
#include <vector>
#include <climits>

using namespace std;
int calc_dist(int m, int n, int a, int b, int c, int d)
{
    int total = INT_MAX;
    //수평거리제곱 + 수직거리제곱
    //현재 공보다 위에 있을때
    if (a != c || b <= d) total = min(total, (int)(pow(a - c, 2) + pow(b + d, 2)));
    //현재 공보다 오른쪽에 있을 때
    if (a >= c || b != d) total = min(total, (int)(pow(a - 2 * m + c, 2) + pow(b - d, 2)));
    //현재 공보다 아래에 있을 때
    if (a != c || b >= d) total = min(total, (int)(pow(a - c, 2) + pow(b - 2 * n + d, 2)));
    //현재 공보다 왼쪽에 있을때
    if (a <= c || b != d) total = min(total, (int)(pow(a + c, 2) + pow(b - d, 2)));
    return total;
}
vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls)
{
    vector<int> answer;

    for (int i = 0; i < balls.size(); i++)
        answer.push_back(calc_dist(m, n, startX, startY, balls[i][0], balls[i][1]));

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/12902

문제를 봤을 때 DP로 풀면 좋을 것 같다고 생각을 했다. 그러려면 일반 점화식을  도출해내야한다. 

문제를 생각해보면 짝수에서만 가능하다는 것을 알 수 있다. 그리고 일반적인 경우를 생각해보자면

• n=0인 경우:
  • 타일을 채울 수 없는 경우로, 한 가지 방법이 존재-> 아무것도 하지 않는 방법.
• n=2인 경우:
  • 가로로 타일 3개 배치
  • 세로로 2개를 위로 쌓아 배치
  • 세로로 2개를 아래로 쌓아 배치 
• n=4인 경우:
  • 3×2 크기의 바닥을 두 번 채우는 경우와 유사하게 생각할 수 있다.

이제 점화식을 도출해보자 

3×n 크기의 바닥을 채우는 방법을 찾기 위해 3×(n−2) 혹은 그 이하의 크기에서 타일을 어떻게 배치하는지 생각해보자

n의 경우의 수를 구하려면 일단 n-2번째와 n-4.. 0이 될때까지의 경우의 수를 모두 더 해주어야한다. 이때 n-4의 패턴부터는 좌우 대칭적으로 배치할 수 있기 때문에 곱하기2를 해준다.

코드로 구현하면 다음과 같다

#include <string>
#include <vector>
#define MOD 1000000007
using namespace std;
//dp활용 
//짝수일때만 계산가능

int solution(int n) {
   if (n % 2 != 0) return 0; // 홀수일 경우 0 반환
    
    vector<long long> dp(n + 1, 0);
    dp[0] = 1; // base case
    dp[2] = 3; // 기본적인 2x3 타일 배치 방법의 수
    
    for (int i = 4; i <= n; i += 2) {
        dp[i] = dp[i - 2] * dp[2];
        for (int j = i - 4; j >= 0; j -= 2) {
            dp[i] += dp[j] * 2;
        }
        dp[i] %= MOD;
    }
    
    return dp[n];
}

https://school.programmers.co.kr/learn/courses/30/lessons/87377

교점을 찾아서 사각형 격자판을 만들어야하는 문제이다.

어떻게 교점을 찾는지가 핵심이다.

이때는 행렬 방정식을 이용해보도록 하자.

#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    set<pair<int, int>> points;          //교점 저장할 변수

    //교점계산
    for (int i = 0; i < line.size(); i++) {
        for (int j = i + 1; j < line.size(); j++) {
            long long a1 = line[i][0], b1 = line[i][1], c1 = line[i][2];
            long long a2 = line[j][0], b2 = line[j][1], c2 = line[j][2];
            long long inc = a1 * b2 - a2 * b1;              //행렬식
            if (inc == 0) continue;

            //교점계산
            long long x_num = b1 * c2 - b2 * c1;
            long long y_num = a2 * c1 - a1 * c2;

            //정수부분인지 계산
            if (x_num % inc == 0 && y_num % inc == 0) {
                int x = x_num / inc;
                int y = y_num / inc;
                points.insert({ x,y });
            }
        }
    }

    //격자판범위계산
    int min_x = INT_MAX, max_x = INT_MIN;
    int min_y = INT_MAX, max_y = INT_MIN;
    for (auto point : points) {
        min_x = min(min_x, point.first);
        max_x = max(max_x, point.first);
        min_y = min(min_y, point.second);
        max_y = max(max_y, point.second);
    }

    //격자판만들기
    int wid = max_x - min_x + 1;
    int height = max_y - min_y + 1;
    vector<string> grid(height, string(wid, '.'));            //.으로 격자판초기화
    for (auto point : points) {
        int x = point.first - min_x;            //x좌표 계산
        int y = max_y - point.second;           //y좌표 계산
        grid[y][x] = '*';
    }
    return grid;
}

https://school.programmers.co.kr/learn/courses/30/lessons/250136

석유덩어리를 찾는데 BFS를 사용하는 것은 알았는데 이걸 어떻게 활용할지가 생각이 정말 안났다. 

일단 전체를 순회하면서 덩어리를 찾는데 BFS를 사용 - 이 과정에서 덩어리로 인식할 수 있게 아이디를 부여 

열을 기준으로 행을 순회하면서 아이디에 해당하는 그룹의 사이즈가 아직 시추되지 않았다면 시추하고 사이즈를 저장한다.

마지막으로 이 중에서 가장 큰 값을 결과값으로 둔다.

#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int DIRS[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

int n, m;
vector<vector<int>> land;
vector<vector<bool>> visited;
vector<vector<int>> component;      //같은 그룹묶어주기
unordered_map<int, int> component_size;     //그룹의 사이즈

//같은 그룹찾기 -> BFS로 
int bfs(int x, int y, int comp_id) {            //x,y,그룹아이디
    queue<pair<int, int>> q;
    q.push({ x, y });
    visited[x][y] = true;
    component[x][y] = comp_id;
    int size = 0;

    while (!q.empty()) {
        auto [cx, cy] = q.front(); q.pop();
        size++;

        for (int d = 0; d < 4; d++) {
            int nx = cx + DIRS[d][0];
            int ny = cy + DIRS[d][1];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && land[nx][ny] == 1) {
                q.push({ nx, ny });
                visited[nx][ny] = true;
                component[nx][ny] = comp_id;
            }
        }
    }

    return size;
}

int solution(vector<vector<int>> land_input) {
    land = land_input;
    n = land.size();
    m = land[0].size();
    visited.assign(n, vector<bool>(m, false));
    component.assign(n, vector<int>(m, -1));
    component_size.clear();

    int comp_id = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 석유가 있고 방문하지 않은 위치에서 BFS 실행
            if (land[i][j] == 1 && !visited[i][j]) {
                int size = bfs(i, j, comp_id);
                component_size[comp_id] = size;
                comp_id++;
            }
        }
    }

    vector<int> oil_per_column(m, 0);

    for (int j = 0; j < m; j++) {
        unordered_map<int, bool> touched;  // 현재 열에서 이미 포함된 덩어리를 추적하는 맵
        for (int i = 0; i < n; i++) {
            // 석유가 있고 현재 열에서 아직 포함되지 않은 덩어리라면 
            if (land[i][j] == 1 && !touched[component[i][j]]) {
                oil_per_column[j] += component_size[component[i][j]];  // 덩어리 크기를 현재 열의 석유량에 추가
                touched[component[i][j]] = true;  // 컴포넌트 아이디에 해다아하는 값이 없을때 -> 현재 덩어리를 포함했다고 표시
            }
        }
    }

    return *max_element(oil_per_column.begin(), oil_per_column.end());
}

https://school.programmers.co.kr/learn/courses/30/lessons/150369

결국에는 그리디하게 접근하는게 중요할 것 같다

제일 먼집부터 순회하면서 배달 및 수거를 진행하고 이를 통해 해당 집에 대한 왕복횟수를 계산하면서 최종적인 이동 거리를 계산해주면 된다.

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

using namespace std;
//결국은 그리디
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    int delivery_load = 0;  // 현재 트럭에 실린 배달 상자 수
    int pickup_load = 0;    // 현재 트럭에 실린 수거 상자 수

    // 가장 먼 집부터 순회
    for (int i = n - 1; i >= 0; --i) {
        // 해당 집에 배달하거나 수거할 상자가 있는 경우에만 작업
        if (deliveries[i] > 0 || pickups[i] > 0) {
            int rounds = 0;  // 해당 집에 대한 왕복 횟수

            // 배달 또는 수거할 상자가 트럭 용량보다 많은 경우 추가로 왕복해야 함
            while (delivery_load < deliveries[i] || pickup_load < pickups[i]) {
                rounds++;
                delivery_load += cap;  // 트럭에 최대 용량만큼 배달 상자를 추가로 실음
                pickup_load += cap;    // 트럭에 최대 용량만큼 수거 상자를 추가로 실음
            }

            // 해당 집에서 배달할 상자를 트럭에서 내림
            delivery_load -= deliveries[i];
            // 해당 집에서 수거할 빈 상자를 트럭에 실음
            pickup_load -= pickups[i];

            // 왕복 거리를 답에 추가 (집까지의 거리 * 2 * 왕복 횟수)
            answer += (i + 1) * 2 * rounds;
        }
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/72412

문제가 굉장히 길다 

잘 읽어보면 유저에 관한 정보를 주고 쿼리에 맞는 점수이상의 유저가 몇명인지 찾아야하는 문제이다. 

여기서 중요한 것은 유저에 대한 정보를 저장할 때 유저의 정보에 대한 조합을 미리 만들어두고 쿼리를 split해서 이게 맞는 유저의 수를 찾으면 된다.

중요포인트

1. 문자열 나누기 

2. 조합만들기

3. 쿼리에 대한 정보 lower_bound로 찾지

lower_bound는 정렬된 범위에서 특정 값 이상이 처음 나타나는 위치를 찾는 데 사용

이를 통해 몇명인지 찾을 수 있다.

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <sstream>

using namespace std;

// 지원자 정보를 저장하기 위한 해시맵
unordered_map<string, vector<int>> info_map;

// 모든 가능한 조건 조합을 생성하여 해시맵에 저장하는 함수
void add_info(const vector<string>& info_tokens, int score) {
    string languages[] = {info_tokens[0], "-"};
    string jobs[] = {info_tokens[1], "-"};
    string careers[] = {info_tokens[2], "-"};
    string foods[] = {info_tokens[3], "-"};
    
    // 각 조건별로 가능한 모든 조합을 생성
    for (const string& lang : languages) {
        for (const string& job : jobs) {
            for (const string& career : careers) {
                for (const string& food : foods) {
                    string key = lang + job + career + food;
                    info_map[key].push_back(score);  // 해당 조합의 키에 점수 추가
                }
            }
        }
    }
}

vector<int> solution(vector<string> info, vector<string> query) {
    // 1. 지원자 정보를 파싱하고 info_map에 저장
    for (const string& inf : info) {
        istringstream iss(inf);
        vector<string> info_tokens((istream_iterator<string>(iss)), istream_iterator<string>());
        int score = stoi(info_tokens.back());  // 점수를 추출
        info_tokens.pop_back();  // 점수를 제외한 나머지 정보들만 남김
        add_info(info_tokens, score);  // 정보를 해시맵에 추가
    }
    
    // 각 키에 대해 점수 리스트를 정렬하여 이진 탐색을 가능하게 함
    for (auto& [key, scores] : info_map) {
        sort(scores.begin(), scores.end());
    }

    vector<int> answer;

    // 2. 각 쿼리를 처리
    for (const string& qry : query) {
        istringstream iss(qry);
        string lang, job, career, food, temp;
        int score;
        iss >> lang >> temp >> job >> temp >> career >> temp >> food >> score;
        
        string key = lang + job + career + food;  // 쿼리에 해당하는 키를 생성
        const vector<int>& scores = info_map[key];  // 해당 키에 저장된 점수 리스트를 가져옴
        
        // lower_bound를 사용하여 주어진 점수 이상인 첫 번째 위치를 찾음
        auto it = lower_bound(scores.begin(), scores.end(), score);
        // 해당 위치부터 끝까지의 개수가 조건을 만족하는 지원자의 수
        answer.push_back(scores.end() - it);
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/42860

그리디하게 접근하는 것이 중요하다고 생각했다.

1.알파벳 기준 절반이상이면 왼쪽으로 이동하는것이 이득, 아니라면 오른쪽으로 이동하는것이 이득

2.커서도 동일하게 길이의 절반이상이면 왼쪽으로 이동하는 것이 이득, 아니라면 오른쪽으로 이동

이렇게 생각하고 min으로 A부터 움직였을 때와 Z부터 움직였을 때의 최소값을 구한다.

그리고 커서를 움직이는 것을 생각해보면 

왼쪽으로 움직일때와 오른족으로 움직일때의 최솟값을 계산하면 된다. 

#include <string>
#include <algorithm>
using namespace std;
//알파벳 기준 절반이상이면 왼쪽으로 이동하는것이 이득, 아니라면 오른쪽으로 이동하는것이 이득
//커서도 동일하게 길이의 절반이상이면 왼쪽으로 이동하는 것이 이득, 아니라면 오른쪽으로 이동
int solution(string name) {
    int n = name.length();
    int answer = 0;
    
    // 각 알파벳을 바꾸는 데 필요한 조작 횟수를 합산
    for (int i = 0; i < n; ++i) {
        answer += min(name[i] - 'A', 'Z' - name[i] + 1);
    }
    
    // 커서 이동의 최소 조작 횟수를 구함
    int move = n - 1;
    for (int i = 0; i < n; ++i) {
        int next = i + 1;
        while (next < n && name[next] == 'A') {         //A건너뛰기 
            ++next;
        }
        move = min(move, i + n - next + min(i, n - next));      //왼쪽으로 갈때, 오른쪽으로 갈때 비교
    }
    
    return answer + move;
}

이 문제에서 중요한 점은

⭐ 블록에 적힌 번호가 n일때 가장 첫 블록은 n*2번째 위치에 설치하고 그 다음은 n*3, n*4에 설치한다.

⭐ 기존에 설치된 블록을 빼고 새로운 블록을 집어 넣을 수 있다

⭐ 만약 1부터 시작이라면 입출력 예시와 같이 제일 앞에 0이 있어야한다. 

이때 12번 블록에 들어갈 블록을 생각해보면 

12번 블록의 약수는 1,2,3,4,6,12이다 이때 최종적으로 들어가게 되는 블록은 제일 큰 약수인 6이다. 

만약 6번째 블록은 12번째 블록에 설치되는 것이다. 

이 약수는 제일 작은 약수에서 원래 값을 나누어주면 된다.

그리고 이 약수가 10,000,000보다 낮은 경우에만 블록으로 사용 가능하기 때문에 만약 가장 큰 약수가 이 보다 크다면 앞에서부터 숫자를 늘려가면서 원래값에 나눠주면 그보다 작은 값을 얻을 수 있다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;
const int MAX_VALUE=10000000;

long long FindMaxDiv(int num)
{
    long long result=1;
    
    for(int i=2;i<=sqrt(num);i++){
        if(num%i==0){
            result=i;
            
            if(num/i<=MAX_VALUE){
                result=num/i;
                break;
            }
        }
    }
    
    return result;
}

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    for(int i=begin;i<=end;i++){
        if(i==1){
           answer.push_back(0);
           continue;
        }
        answer.push_back(FindMaxDiv(i));
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/181188

그리디하게 접근하는 것이 중요하다. 

핵심은 end포인트를 기준으로 오름차순 정렬하고 설정된 end포인트보다 Start 포인트가 작은 미사일은 요격해주고 아닌 경우에는 요격포인트를 새로 설정해주는 것이다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//그리디하게 접근
bool cmp(vector<int> &a,vector<int> &b){
    if(a[1]==b[1]) return a[0]<b[0];
    else return a[1]<b[1];
}
int solution(vector<vector<int>> targets) {
    int answer = 0;
    sort(targets.begin(),targets.end(),cmp);
    int end=targets[0][1];
    answer++;
    for(int i=1;i<targets.size();i++){
        //만약 시작값이 설정해둔 끝점보다 작다면 요격가능
        if(targets[i][0]<end) continue;
        //아니라면 새로운 요격포인트 지정
        else{
            answer++;
            end=targets[i][1];
        }
    }
    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/160585

틱텍토 판이 주어질 때 이게 규칙을 지켜서 진행한 틱택토에서 나올 수 있는 상황인지 검사하면 되는 것이다

O가 선공 X가 후공이다. 

안되는 조건을 모두 검사하는 것이 중요하다. 

O의 개수가 X보다 많거나 같아야하고 많을 때는 2개이상 많아질 수 없다. 

둘 다 이길 수는 없다.

만약 O가 이겼을 때는 X의 개수보다 1개 많아야한다.

만약 X가 이겼을 때는 X가 후공이여서 O의 개수와 같은 수여야한다.

#include <string>
#include <vector>

using namespace std;
//O와 X의 개수를 세고 안되는 조건인지 검사
bool isWin(const vector<string>& board,char mark)
{
    //가로
    for(int i=0;i<3;i++)
    {
        if(board[i][0]==mark && board[i][1]==mark && board[i][2]==mark) return true;
    }
    //세로
    for(int i=0;i<3;i++)
    {
        if(board[0][i]==mark && board[1][i]==mark && board[2][i]==mark) return true;
    }
    if(board[0][0]==mark && board[1][1]==mark && board[2][2]==mark) return true;
    if(board[0][2]==mark && board[1][1]==mark && board[2][0]==mark) return true;
    
    return false;
}

int solution(vector<string> board) {
    int ocnt=0,xcnt=0;

    
     // O와 X의 개수를 센다.
    for (const string& row : board) {
        for (char cell : row) {
            if (cell == 'O') ocnt++;
            else if (cell == 'X') xcnt++;
        }
    }
    
    if(xcnt>ocnt) return 0;
    
    if(ocnt>xcnt+1) return 0;
    
    bool winO =isWin(board,'O');
    bool winX =isWin(board,'X');
    
    //둘 다 이길수는 없다
    if(winO && winX) return 0;
    //만약 O가 이겼을 때 O의 개수는 X보다 1개많아야 한다.
    if(winO && ocnt!=xcnt+1) return 0;
    //만약 x가 이겼을 때 x의 개수는 O와 같아야한다. 
    if(winX && xcnt!=ocnt) return 0;
    
    return 1;
}