TIL day 15

1. 과제 풀이

• 언리얼 로그를 통해 좌표를 이동하는 프로그램을 작성하는 과제를 진행하였습니다.
• 추가적으로 언리얼 로그 시스템에 카테고리가 있는데, 커스텀 카테고리를 만드는 법을 추가적으로 공부해 보았습니다.

https://gbleem.tistory.com/27

UE_LOG 보충 (+ 과제)

 

2. 코딩 테스트

오늘 오전에도 프로그래머스 level 2 숫자 카드 나누기 문제를 풀었습니다.

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

프로그래머스

• 이 문제를 보고, 아래처럼 진행해야겠다는 생각이 들었습니다.
  • A배열에서 두개의 값을 뽑아서 최대공약수를 구한 후
  • 해당 값을 통해 B 배열을 순환하면서, 나눠지는 숫자가 없다면 answer에 기록한 후
  • B 배열을 기준으로 앞서 진행한 방식을 반복해서 최대공약수를 구하고, A배열을 순환하여 answer을 업데이트 하기
• 그런데, 앞에서부터 두개씩 비교해서 하나의 결과를 내는 과정이다보니 허프만 코딩 알고리즘을 사용했던 문제가 생각나서 해당 방식으로 해결해 보았습니다. (문제에서 원하는 방식은 아닐수도?)
• 코드
  • 주요한 내용은 허프만 코딩 방식과 최대공약수를 유클리드 호제법을 사용한 부분입니다.
  • 해당 알고리즘을 까먹지 말고자 정리도 해 보았습니다.

https://gbleem.tistory.com/28

허프만 코딩 & 유클리드 호제법

 

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

priority_queue<int, vector<int>, greater<int>> pqA;
priority_queue<int, vector<int>, greater<int>> pqB;

int gcd(int a, int b)
{
    if(a == 0)
        return b;
    else
        return gcd(b%a, a);
}

int solution(vector<int> arrayA, vector<int> arrayB) 
{
    int answer = 0;
    //a1 a2의 최대공약수로 
    //b1 b2 안나눠떨어지면 ok
    
    for(int i = 0; i < arrayA.size(); ++i)
    {
        pqA.push(arrayA[i]);
        pqB.push(arrayB[i]);
    }
    while(pqA.size() > 1)
    {
        int a = pqA.top();
        pqA.pop();
        int b = pqA.top();
        pqA.pop();
        int g = gcd(a, b);
        pqA.push(g);
    }
        
    bool flag = true;
    for(auto b : arrayB)
    {
        //나눠지지 않는 것 찾기
        if(b % pqA.top() == 0)
            flag = false;            
    }
    if(flag)
        answer = pqA.top();
    
    //반대도 해서 큰 수 정답
    while(pqB.size() > 1)
    {
        int a = pqB.top();
        pqB.pop();
        int b = pqB.top();
        pqB.pop();
        int g = gcd(a, b);
        pqB.push(g);
    }

    bool flag2 = true;
    for(auto a : arrayA)
    {
        if(a % pqB.top() == 0)
            flag2 = false;            
    }
    if(flag2)
        answer = max(answer, pqB.top());
    
    
    return answer;
}

 

오후에 코딩 테스트 문제를 몇 개 더 풀었습니다. 

• 간단한 bfs 문제 (프로그래머스 level2 무인도 여행) 
  • 이중 for문을 통해 maps를 순환하면서,
  • 시작이 가능한 좌표('X'가 아니고, 방문한 적이 없는 좌표)를 queue에 넣고 bfs를 실행하면 됩니다. 
    
    • 이때 bfs를 돌면서 날짜 값(days)을 업데이트 해주면 쉽게 풀 수 있습니다.
      • 주의) maps는 string 배열이므로, - 48을 해서 값을 더해주면 int로 바꿔서 값을 저장할 수 있습니다.
      • char 에서 48을 빼면 int 타입으로 바꿔집니다. days += (maps[nx][ny] - 48);
    • 한번 bfs를 순환하면 vis 배열이 업데이트 되기 때문에, 이중 for문을 통해 다음으로 가능한 좌표를 찾으면서, 중복되는 부분이 없게 끝날 수 있습니다.
    • 마지막으로 answer 배열을 sort하고, 빈 벡터라면 -1을 추가하면 됩니다.

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

프로그래머스

 

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

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char board[102][102];
int vis[102][102];
queue<pair<int, int>> q;

vector<int> solution(vector<string> maps) 
{
    vector<int> answer;
    int row = maps.size();
    int col = maps[0].size();
    
    for(int i = 0; i < maps.size(); ++i)
    {
        for(int j = 0; j < maps[0].size(); ++j)
        {
            if(vis[i][j] == 0 && maps[i][j] != 'X') // 방문하지 않았고, 바다 아닐때
            {
                //cout << "(" << i <<", " << j <<")\n";
                q.push({i, j});
                vis[i][j] = 1;
                int days = maps[i][j] - 48;
                
                while(!q.empty())
                {
                    auto cur = q.front();
                    q.pop();
                    
                    for(int dir = 0; dir < 4; ++dir)
                    {
                        int nx = cur.first + dx[dir];
                        int ny = cur.second + dy[dir];
                        
                        if(nx < 0 || nx >= row || ny < 0 || ny >= col)
                            continue;
                        if(vis[nx][ny] != 0 || maps[nx][ny] == 'X') //이미 방문했거나 바다일 때
                            continue;
                        q.push({nx, ny});
                        vis[nx][ny] = 1;
                        days += (maps[nx][ny] - 48);
                    }
                }
                answer.push_back(days);
            }
        }
    }
    
    sort(answer.begin(), answer.end());
    
    if(answer.empty())
        answer.push_back(-1);
    
    return answer;
}

• 프로그래머스 level2 점 찍기
  • 단순히 수학적으로 생각하면, 시간 초과가 발생합니다. (이중 for문은 불가능)
    • 시행 착오
      • 거리 값을 구하는 것이기 때문에 우리는 1/4 원 안에서의 좌표값을 찾는다고 생각했고,
      • 이걸 반으로 줄여서 1/8 원 안에서의 좌표값을 찾는 방식을 시도했으나 실패했습니다.
    • 해결 방식
      • x 좌표만 움직이면서, 내가 구하고자 하는 y값의 최대를 찾아서 답을 내는 방식으로 해결하였습니다.
  • 예전에 "두 수의 합" 관련 문제를 풀면서도 이런 테크닉을 썻는데, 이 문제를 못찾아서 찾게 되면 추가적으로 정리를 해 보겠습니다.
  • 해결한 방식을 설명해 보면
    • for문을 통해 x좌표를 증가시키면서,
    • distance 계산을 통해 (d*d = x*x + y*y) 최대로 가능한 y의 값을 구한 후,
    • 구한 y값을 k로 나누면, 각 x값 마다 범위에 맞는 y값을 찾아낼 수 있습니다.
    • 이때 answer이 long long 타입이므로, 나머지 계산하는 값들도 long long으로 잘 맞춰주면 됩니다.

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

프로그래머스

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

long long solution(int k, int d) 
{
    long long answer = 0;

    for (int x = 0; x <= d; x += k) 
    {        
        long long maxY = (long long)d*d - (long long)x*x;
        maxY = sqrt(maxY);
        
        answer += (maxY / k) + 1;
    }

    return answer;
}