25.11.21일자 - TIL

코딩 테스트 4-4

그리디 알고리즘

기본 개념과 작동 원리를 이해할 수 있다.
최적해를 구하는 과정에서의 선택 기준을 학습한다.

그리디(Greedy) - 탐욕스럽다
각 단계에서 지역적으로 최적의 선택을 하여 전체적으로 최적해를 찾는 것을 목표로 한다.

최적 부분 구조(앞 시간과 같은 내용)

그리디 선택 속성
각 단계에서 지역적인 최적 선택이 전체 문제의 최적 해로 이어질 수 있어야 한다는 성질

다양한 시간표 중 가장 많은 강의를 듣는 선택지를 고르는 예시.


거스름돈 예시 - 그리디가 적용 되지 못하는 예시.
거스름돈이 배수로 제한되는 경우에만 적용이 가능하다.



최소 신장 트리
 간선의 수가 정점의 수-1개 이고
 모든 정점은 최소 하나 이상의 간선으로 연결되어 있는 트리.


프림 알고리즘

임의의 정점을 하나 선택해 최소 신장 트리에 추가한다.
현재 트리에서 연결 가능한 간선 중, 가중치가 가장 작은 간선을 선택하여 해당 간선의 반대편 정점을 트리에 추가한다.
이 과정을 모든 정점이 트리에 포함될 때까지 반복한다.


==========
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 100;
const int INF = 1000000000;

int cost[MAX][MAX];  // 인접 행렬: 간선의 비용 저장
bool visited[MAX];   // 방문 여부
int minEdge[MAX];    // 각 정점에 연결된 최소 비용 간선의 가중치
int parent[MAX];     // MST에서 각 정점의 부모 정점 인덱스

int main() {
    int V = 5;  // 정점의 개수

    // 간선 비용 초기화 (없는 간선은 INF)
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cost[i][j] = INF;
        }
    }

    // 예시 간선들 (무방향 그래프)
    cost[0][1] = cost[1][0] = 2;
    cost[0][3] = cost[3][0] = 6;
    cost[1][2] = cost[2][1] = 3;
    cost[1][3] = cost[3][1] = 8;
    cost[1][4] = cost[4][1] = 5;
    cost[2][4] = cost[4][2] = 7;
    cost[3][4] = cost[4][3] = 9; // 다른 간선 예시

    // 방문 배열, 최소 간선 배열, 부모 배열 초기화
    for (int i = 0; i < V; i++) {
        visited[i] = false;
        minEdge[i] = INF;
        parent[i] = -1; // 부모 없음으로 초기화
    }

    minEdge[0] = 0;  // 시작 정점(0번) 설정

    // V개의 정점을 MST에 포함시킬 때까지 반복
    for (int count = 0; count < V; count++) {
        int minVal = INF;
        int u = -1;

        // 방문하지 않은 정점 중 MST에 가장 가까운 정점 u 찾기
        for (int j = 0; j < V; j++) {
            if (!visited[j] && minEdge[j] < minVal) {
                minVal = minEdge[j];
                u = j;
            }
        }

        if (u == -1) break; // 연결 그래프가 아닌 경우 대비

        visited[u] = true; // 정점 u 방문 처리

        // 새로 추가된 정점 u와 인접한, 아직 방문하지 않은 정점 v들의 정보 갱신
        for (int v = 0; v < V; v++) {
            if (!visited[v] && cost[u][v] != INF && cost[u][v] < minEdge[v]) {
                minEdge[v] = cost[u][v]; // 최소 비용 갱신
                parent[v] = u;           // v의 부모를 u로 설정
            }
        }
    }

    // 최소 신장 트리를 구성하는 간선 목록만 출력
    cout << "최소 신장 트리를 구성하는 간선 목록:" << endl;
    for (int i = 1; i < V; ++i) { // 루트(0번) 제외하고 확인
        if (parent[i] != -1) { // MST에 포함된 간선만 출력
             cout << "간선: (" << parent[i] << ", " << i << ") 비용: " << cost[parent[i]][i] << endl;
        }
    }

    return 0;
}
==========

크루스칼 알고리즘
 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.
 가중치가 가장 작은 간선부터 하나씩 선택하여, 사이클이 발생하지 않으면 최소 신장 트리에 추가한다.
 이 과정을 모든 정점이 하나의 트리로 연결될 때까지 반복한다.


배낭 문제
부분( 짐을 쪼갤 수 있는 경우) / 0/1(넣거나 빼거나 택 1인 경우) 차이


거스름 돈 문제 (100, 50, 10, 1)
거스름 돈이 배수이므로 그리디를 활용할 수 있다.

예산 문제

기지국 설치 문제

==========
#include <vector>

using namespace std;

int solution(int N, vector<int> stations, int W) {
  int answer = 0;
  int location = 1; // 현재 탐색하는 아파트의 위치
  int idx = 0; // 설치된 기지국의 인덱스

  while (location <= N) {
    // 기지국이 설치된 위치에 도달한 경우
    if (idx < stations.size() && location >= stations[idx] - W) {
      location = stations[idx] + W + 1;
      idx++;
    }
    // 기지국이 설치되지 않은 위치인 경우
    else {
      // 기지국을 설치하고 해당 범위를 넘어감
      location += 2 * W + 1;
      answer++;
    }
  }

  return answer;
}

// 아래 코드는 테스트 코드 입니다.
#include <iostream>

int main()
{
    cout << solution(11, {4, 11}, 1) << endl; // 3
    cout << solution(16, {9}, 1) << endl;   // 3
    return 0;
}
===========
코딩을 설계하는 것에 비해 완성된 코드 자체는 그다지 길지 않다.

===============================================================
코딩 테스트 5-1
ctrl + alt + t
대기업의 출제 경향

삼전의 커트라인이 1.5솔인 이유
공개된 조건 외에 완전한 히든 조건까지 만족해야 1솔이기 때문.

================================================================
코딩 테스트 5-2

정렬이 필요 없으므로 unorderd_map / unorderd_set을 사용
string   key(피 신고자/map)-value(신고자/set)

7분 부터 설계하는 시범

==========
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <sstream>

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
  unordered_map<string, unordered_set<string>> reported_user; // 신고당한 유저 - 신고 유저 집합
  unordered_map<string, int> count; // 처리 결과 메일을 받은 유저 - 받은 횟수

  // 신고 기록 순회
  for (string& r : report) {
    // 각 report에서 user_id와 report_id를 분리하고 reported_user에 추가
    stringstream ss(r);
    string user_id, reported_id;
    ss >> user_id >> reported_id;
    reported_user[reported_id].insert(user_id);
  }

  for (auto& [reported_id, user_id_lst] : reported_user) {
    // k명 이상에게 신고당했는지 확인
    if (user_id_lst.size() >= k) {
      // 각 uid가 신고 결과를 받은 횟수를 기록
      for (const string& uid : user_id_lst) {
        count[uid]++;
      }
    }
  }

  vector<int> answer;
  // 각 아이디별 메일을 받은 횟수를 id_list 순서대로 answer에 추가
  for (string& id : id_list) {
    answer.push_back(count[id]);
  }

  return answer;
}

// 아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
void print(vector<int> vec)
{
    copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, " "));
    cout << endl;
}

int main()
{
    print(solution({"muzi", "frodo","apeach", "neo"}, {"muzi frodo", "apeach frodo", "frodo neo", "muzi neo", "apeach muzi"}, 2)); // 출력값 : 2 1 1 0
    print(solution({"con", "ryan"}, {"ryan con", "ryan con", "ryan con", "ryan con"}, 3)); // 출력값 : 0 0

    return 0;
}
==========

===
using namespace std;
std(standard) 에 있는 단어들로 명명하겠다. 라는 명령(?)

string - 문자열
sstream  - s(tring)stream 문자를 공백을 기준으로 분리할 때 활용하면 좋다.

===

메뉴 리뉴얼 문제

조합을 구할 때 유의할 점

조합을 구하기 전, 오름차순 정렬을 해서 AB =/= BA로 출력 되는 문제를 막으면 된다.

20분 부터 시범

==========
#include <algorithm>
#include <string>
#include <vector>
#include <map>

using namespace std;

map<string,int> combi; // 주문의 조합 - 조합의 빈도

// 실제 주문의 조합을 구하는 함수
void combination(string src, string dst, int depth) {
  if (dst.size() == depth) combi[dst]++;

  else for (int i = 0; i < src.size(); i++)
    combination(src.substr(i+1), dst+src[i], depth);
}

vector<string> solution(vector<string> orders, vector<int> course) {
  vector<string> answer;
  // 각 주문들을 오름차순으로 정렬
  for (string &order : orders)
    sort(order.begin(), order.end());

  for (int len : course) {
    for (string order : orders)
      // course의 길이에 해당되는 조합 생성
      combination(order, "", len);

    // 각 주문의 빈도수를 순회하면서 가장 많은 빈도수를 maxOrder에 저장
    int maxOrder = 0;
    for (auto it : combi)
      maxOrder = max(maxOrder, it.second);

    // 주문 횟수가 2회 이상이면서, 가장 많이 주문된 주문의 구성은 answer에 추가
    for (auto it : combi)
      if (maxOrder >= 2 && it.second == maxOrder)
        answer.push_back(it.first);

    combi.clear();
  }
  // 반환 전, 문제의 조건에 따라 주문의 구성들을 오름차순 정렬해서 반환
  sort(answer.begin(), answer.end());
  return answer;
}


// 아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>
void print(vector<string> vec)
{
    copy(vec.begin(), vec.end(), std::ostream_iterator<string>(cout, " "));
    cout << endl;
}

int main()
{
    print(solution({"ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"}, {2, 3, 4})); // 출력값 :  AC ACDE BCFG CDE
    print(solution({"ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"}, {2, 3, 5})); // 출력값 : ACD AD ADE CD XYZ
    print(solution({"XYZ", "XWY", "WXA"}, {2, 3, 4})); // 출력값 : WX XY

    return 0;
}
===========

양궁 대회 문제.
개 악질이네 문제가

문제 해독
표적의 점수를 그대로 반환하는 게 아니라 다 쏜 후 둘 중 더 많이 맞춘 사람이 해당 점수를 가져가고 동점이면 도전자인 어피치가 점수를 가져가는 규칙.

36분 부터 시범
==========
#include <vector>

using namespace std;

vector<int> answer;
vector<int> ryan(11, 0);
int maxScore = -1;

// 어피치와 라이언의 점수차이를 계산
int calcScoreDiff(const vector<int> &apeach) {
  int scoreApeach = 0;
  int scoreLion = 0;

  for(int i = 0; i < 11; ++i) {
    if(apeach[i] == 0 && ryan[i] == 0) continue;
    if(apeach[i] >= ryan[i]) scoreApeach += 10 - i;
    else scoreLion += 10 - i;
  }

  return scoreLion - scoreApeach;
}

void dfs(const vector<int> &apeach, int score, int arrow) {
  if(score == -1 || arrow == 0) {
    ryan[10] = arrow;
    int scoreDiff = calcScoreDiff(apeach);
    // 현재 구한 점수차가 기존 최대 점수차보다 더 크고, 라이언의 점수가 더 높은 경우 갱신
    if(scoreDiff > 0 && maxScore < scoreDiff) {
      maxScore = scoreDiff;
      answer = ryan;
    }
    ryan[10] = 0;
    return;
  }

   // 아직 어피치가 쏠 화살이 남은 경우
  if(arrow > apeach[score]) {
    ryan[score] = apeach[score] + 1;
    dfs(apeach, score - 1, arrow - apeach[score] - 1);
    ryan[score] = 0;
  }

  // 어피치가 화살을 사용하지 않는 경우
  dfs(apeach, score - 1, arrow);
}

vector<int> solution(int n, vector<int> info) {
  // 10점 과녁부터 모든 조합을 확인
  dfs(info, 10, n);

  // 라이언이 이길 수 있는 경우가 없는 경우
  if(maxScore == -1) answer.push_back(-1);

  return answer;
}


// 아래 코드는 테스트 코드 입니다.
#include <iostream>
#include <iterator>

void init(){
  answer.clear();
  maxScore = -1;

  for(int i = 0 ; i < ryan.size(); i++)
    ryan[i] = 0;
}

void print(vector<int> vec)
{
  copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, " "));
  cout << endl;
}

int main()
{
  print(solution(5, {2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0})); // 출력값 : 0 2 2 0 1 0 0 0 0 0 0
  init();
  print(solution(1, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0})); // 출력값 : -1
  init();
  print(solution(9, {0, 0, 1, 2, 0, 1, 1, 1, 1, 1, 1})); // 출력값 : 1 1 2 0 1 2 2 0 0 0 0
  return 0;
}
==========

숫자 문자열과 영단어 문제

stoi(s)

49분 부터 시범

==========
#include <string>
#include <iostream>

using namespace std;

int solution(string s) {
    string num_words[10] = {
        "zero", "one", "two", "three", "four",
        "five", "six", "seven", "eight", "nine"
    };
    for (int i = 0; i < 10; ++i) {
        size_t pos;
        // 해당 숫자의 영어 단어가 문자열 s에 없을 때까지 반복하여 숫자로 치환
        while ((pos = s.find(num_words[i])) != string::npos) {
            s.replace(pos, num_words[i].length(), to_string(i));
        }
    }
    return stoi(s);
}

// 아래 코드는 테스트 코드 입니다.
int main() {
    cout << solution("one4seveneight") << endl;
    cout << solution("23four5six7") << endl;
    return 0;
}
==========
튜플 문제

59분 부터 시범

입력 값을 어떻게 처리할 것인가.
 ({1}, {2,1}, {2, 1, 3}) 같이 입력 값이 낯선 것을 처리할지 잘 생각해보자.


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

using namespace std;

int counts[100001] = {};

void updateCounts(const string& s) {
  string numStr;
  // 인자로 받은 문자열을 순회
  for (char ch : s) {
    // 현재 문자가 숫자인 경우
    if (isdigit(ch)) {
      numStr += ch;
    // 현재 문자가 숫자가 아닌 경우
    } else {
      if (!numStr.empty()) {
        //❹ 계수정렬을 하기 위해 각 숫자의 개수를 저장
        counts[stoi(numStr)]++;
        numStr.clear();
      }
    }
  }
}

vector<int> solution(string s) {
  vector<int> answer;
  // 집합이 담긴 문자열의 각 원소를 계수정렬
  updateCounts(s);

  vector<pair<int, int>> freqPairs;
  for (int i = 1; i <= 100000; i++) {
    // 집합에 있는 원소인 경우 (개수, 값) 형식으로 푸시
    if (counts[i] > 0) {
      freqPairs.push_back({counts[i], i});
    }
  }

  // 각 원소의 개수를 기준으로 내림차순 정렬
  sort(freqPairs.rbegin(), freqPairs.rend());

  // 원소의 개수로 내림차순 정렬된 벡터를 순회하며 원소를 푸시
  for (const auto& p : freqPairs) {
    answer.push_back(p.second);
  }

  return answer;
}


// 아래 코드는 테스트 코드 입니다.
#include <iterator>
#include <iostream>

void init()
{
  for(int i = 0 ; i <= 100000; i++)
    counts[i] = 0;
}

void print(vector<int> vec)
{
  copy(vec.begin(), vec.end(), std::ostream_iterator<int>(cout, " "));
  cout << endl;
}


int main()
{
  print(solution("{{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}")); // 출력값 : 2 1 3 4
  init();
  print(solution("{{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}")); // 출력값 : 2 1 3 4
  init();
  print(solution("{{20, 111}, {111}}")); // 출력값 : 111 20
  init();
  print(solution("{{123}}")); // 출력값 : 123
  init();
  print(solution("{{4, 2, 3}, {3}, {2, 3, 4, 1}, {2, 3}}")); // 출력값 : 3 2 4 1

  return 0;
}
==========


=================================================================
언리얼 실습 2-3
3-1 숙제
문을 회전으로 열어야 하므로 전체 수정

90도만 이동하게 하기 위한 설정, 자연스럽게 회전하도록 타임라인을 사용한 모습.


3-2 숙제는 전일 내용으로 대체

본 내용 콜리전
언리얼 엔진 내부에서 콜리전을 어떻게 관리하는지, 실습으로 콜리전 채널과 프리셋을 바꿔가며 이벤트를 발생시켜보는 방법, 스태틱 메시의 기본 콜리전 형태 편집, 그리고 캐릭터 콜리전의 주의 사항을 확인할 수 있다.

오브젝트 채널// 트레이스 채널 둘로 나눠져서 관리된다.

 

차의 채널을 바꿔 상호작용 되지 않게 만드는 과정

다른 조건 변화 없이 겹쳐지는 모습

 

 

히트 판정을 키기 전에는 충돌 만 하는 모습

 

상호 작용까지 활성화 한 후 원래 조건 대로 차가 파괴된 모습

 

===
콜리전

 

보이는 것과 다른 판정을 가진 모습과 오브젝트의 콜리전의 모습을 볼 수 있는 모드

콜리전을 제거한 후 통과되는 모습

 

새롭게 자동완성 콜리전을 만든 후 자연스럽게 올라가지는 모습

 

통과되지 않는 문

콜리전을 수정해 들어가지는 모습

변경된 두 오브젝트의 콜리전 모습