TIL day 21

어제는(1/14) 면접을 보느라 TIL day 20이 없습니다.

1. 코딩 테스트

오늘 오전에는 오랜만에 코딩테스트 문제를 다시 풀었습니다.

level 2에 피로도 문제를 풀었습니다. 

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

프로그래머스

• 뭘로 풀지?
  • 처음에 이 문제를 보고 그리디 문제처럼 보였습니다. 
  • 그런데 예제로 주어진 값들을 보면 어떤 방법으로도 그리디에 해당하지 않았습니다.
    • 필요 피로도나, 소모 피로도 둘 중 무엇을 우선시 하더라도 최적의 결과가 나오지 않아서 다른 방법을 생각해 모았습니다.
    • 이 문제의 특징은 주어진 dungeons 배열의 최대 크기가 8인 것입니다. 
    • 그래서 백트레킹을 써서 문제를 풀어보기로 생각했습니다.
• 백트레킹
  • 백트레킹은 간단히 설명해서 모든 경우의 수를 다 해보는 방식입니다.
  • 백트레킹은 재귀를 통해서 구현하는데, 
  • BOJ 문제들 중에서 N과 M 시리즈와 관련된 문제들이 백트레킹에 관한 문제들입니다.
  • 그중 가장 간단한 N과M (1)을 풀어보겠습니다. (https://www.acmicpc.net/problem/15649)
• BOJ 15649 풀어보기
  • 위에서 말한대로 모든 경우의 수를 그냥 다 구하면 되는 문제입니다.
  • 문제는 아래와 같습니다.
  
  • 정답 코드
    • 아래의 코드가 가장 기본적인 백트레킹 코드의 모습이다. 이 코드에 추가적인 조건이나 더하거나 수정해서 어려운 문제를 풀면 된다.
    • 먼저 ans라고 하는 벡터는 우리가 구하고자 하는 모든 경우의 수를 다 담는 벡터이다.
    • Choose() 함수는 M개를 고르는 함수이다. 
      • if 문을 통해 cur == M+1 이면, 문제에서 하고자 하는 동작을 수행하면 된다.
        • 이 문제에서는 모든 경우의 수를 출력하라고 했으니, Print() 함수를 통해 출력하면 된다.
      • Choose함수의 for문의 인덱스를 통해 우리가 ans 벡터에 넣을 값을 지정하면 된다.
        • 이 문제의 경우 1부터 N까지의 수이기 때문에 i를 1에서 N까지로 넣어준 것이다.
        • 추가적으로 중복은 허용하지 않으니, isused라는 배열을 통해 중복체크를 해주면 된다.

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

int N, M;
vector<int> ans;
bool isused[10];

void Print()
{
	for (const auto& a : ans)
	{
		cout << a << " ";
	}
	cout << "\n";
}

void Choose(int cur)
{
	if (cur == M + 1)
	{
		Print();
		return;
	}
	for (int i = 1; i <= N; ++i)
	{
		if (!isused[i])
		{
			ans.push_back(i);
			isused[i] = true;
			Choose(cur + 1);
			ans.pop_back();
			isused[i] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;

	Choose(1);
	return 0;
}

• 다시 원래 문제로 돌아와서
  • 이 문제도 방금 푼 문제와 유사하게 풀 수 있다.
  • 모든 경우의 수를 구한 후, Print() 대신 Check() 를 통해 최대 던전 수를 측정해서 업데이트 해주면 된다.
• 정답 코드

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

int answer = -1;
vector<int> ans;
vector<vector<int>> Dungeons;
int totalSize;
int K;
int isused[10];

void Check()
{
    int tempK = K;
    int tempAnswer = 0;
    
    for(int i = 0; i < ans.size(); ++i)
    {
        if(tempK >= Dungeons[ans[i]][0])
        {
            tempK -= Dungeons[ans[i]][1];
            tempAnswer++;
        }
        else
        {
            break;
        }
    }
    answer = max(tempAnswer, answer);
}

void Choose(int cur)
{
    if(cur == totalSize + 1)
    {
        Check();
        return;
    }
    for(int i = 0; i < totalSize; ++i)
    {
        if(!isused[i])
        {
            ans.push_back(i);
            isused[i] = 1;
            Choose(cur + 1);
            ans.pop_back();
            isused[i] = 0;
        }        
    }
}

int solution(int k, vector<vector<int>> dungeons) 
{    
    totalSize = dungeons.size();
    K = k;
    Dungeons = dungeons;
    Choose(1);    
    
    return answer;
}

 

추가로 N-Queen 문제도 풀었습니다.

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

프로그래머스

 

• 이 문제를 처음 풀 때 2차원 배열로 시도했지만, 해결하지 못했습니다.
• 다른 해설들을 참고하여 이해한 결과물을 정리해 보겠습니다.
• 결론적으로,
  • 퀸을 배치할때 2차원 배열을 쓸 필요가 없이 배열 하나로 해결할 수 있는 문제였습니다.
  • col이라는 배열을 사용하여 col[cur]] = i; 라고 하면, cur 행 i열에 퀸을 배치하는 것으로 문제를 해결했습니다.
  • 코드의 흐름은
    • Choose()함수가 재귀함수로 cur이라는 변수는 행을 조절하게 됩니다.
    • 이후 Choose()함수 안에 있는 for문의 i를 통해 열을 조절하였습니다.
    • Choose함수에서는
      • for문을 돌면서 행과 열의 값을 col배열에 넣고 Check()함수를 통해 해당 위치가 적합한지를 체크합니다.
      • 만약 퀸을 둘 수 있는 적합한 곳이라면, cur을 증가시켜 Choose함수를 호출하는데(Choose(cur + 1)), 이는 행을 증가시키는 것을 의미합니다.
      • 만약 Choose함수가 for문을 다 돌았지만, Check함수를 통과하지 못하고 빠져나오게 되면 그전에 쌓여있던 재귀함수를 거꾸로 호출하면서 행이 하나 줄어있는 Choose() 함수(Choose(cur-1))를 수행하게 됩니다.
      • 예를 들어
        • (0,0)에 두고, (1, 2)에 두었다면 이후 2행에서는 둘 곳이없으므로,
        • Choose(1)로 돌아가게 되며, (1,2)에서 멈췄으므로 다시 (1,3)을 체크합니다.
        • 이 과정을 반복해서 N개를 고른 순간 answer++를 해주면서 답을 찾을 수 있습니다.

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

int answer = 0;
int N;
int col[14];

bool Check(int cur)
{
    for (int i = 0; i < cur; ++i)
    {
        //열 체크 || 대각선 체크
        if (col[cur] == col[i] || abs(cur - i) == abs(col[cur] - col[i]))
            return false;
    }
    return true;
}

void Choose(int cur)
{
    if (cur == N)
    {
        answer++;
        return;
    }

    //cur 은 행
    //i는 열
    for (int i = 0; i < N; ++i)
    {
        col[cur] = i; //cur행 i열에 퀸 두기

        if (Check(cur))
        {
            Choose(cur + 1);
        }
    }
}

int solution(int n)
{
    N = n;
    Choose(0);

    return answer;
}

 

2. 과제 발표 준비

• 과제 발표를 담당하게 되어서, 발표를 위한 ppt 제작을 하였습니다.
• 프로젝트 코드, 시연 영상, 발표 자료 모두가 업데이트된 팀 노션입니다.
• https://teamsparta.notion.site/1-3-6275cd21563d4ddeba5d7ce71f361581

1기 3조 | Notion

 

☆이것저것 나의 생각☆

• 면접 준비하면서 느낀 점인데, 이야기할 때 사람 눈을 잘 쳐다봐야 할 것 같다는 생각이 들었습니다. 면접을 연습하면서 스스로의 모습을 찍어봤는데, 눈이 엄청 왔다갔다 하는 문제점이 있었습니다. 이런 것들이 아마도, 사람이 편안해 보이는지 불안해 보이는지 등을 알 수 있을 것 같아서 고치고 바꿔야 할 것 같았습니다.
• 내가 아는 것을 잘 설명하는 것도 중요하다고 생각했습니다. 분명히 내가 자주 쓰고, 공부해 본 것인데 막상 설명해보려고 하는 생각보다 쉽지 않았습니다. 그래서 앞으로 동료들과 많이 이야기하면서, 서로 생각도 좀 공유하고 아는것도 공유하는 그런 시간을 가지면 좋겠다는 생각이 들었습니다.
• 글을 날려서 읽고, 읽고 싶은 것만 읽는 것 같다는 생각이 많이 들었습니다. 아무래도 최근에는 영상을 통해서 공부도 많이하고, 글보다는 영상을 많이 봐서인지 글보다 영상이 편해졌던 것 같습니다. 그래서 앞으로는 문제를 보거나 책을 보거나 등등 모든 글을 볼때 앞에서부터 천천히 잘 읽는 버릇을 가져야 할 것 같습니다.
• TIL 블로그 글을 보니 말투가 계속 달라지는 것을 볼 수 있었습니다. (~있다. ~있습니다. 둘 다 쓰고있음) 앞으로는 TIL을 쓸 때는 ~습니다.  이런 말투로 적고, 다른 공부 정리글을 쓸 때는 ~있다. 이런 식으로 적어서 통일성을 주어야 할 것 같습니다.
• 다음주 부터는 언리얼 엔진 공부를 본격적으로 시작하게 되는데 기대가 됩니다. 이번 기회에는 재미도 있고 멋진 게임을 꼭 한번 완성해보고 싶습니다.