TIL day 64

이번주 월화수목 예비군을 다녀왔습니다.

 

1. 코딩테스트

---

오전에 챌린지반 과제 및 밀린 문제들을 해결했습니다.

 

1 - 1. N-Queen 다시 풀기

• N-Queen 문제에 있어서 갯수만 출력하는 것이 아니라 해당 위치를 출력하는 것이 과제이다.
• Choose함수에서 cur 변수가 x값(row) i 변수가 y값(col) 인 것을 생각하면 쉽게 해결할 수 있다.
• 주의할 점은 board 벡터를 초기화 해주고 사용해야 하므로, resize(n, vector<int> (n,0)); 코드가 필요하다.

//n queen
#include <iostream>
#include <vector>
using namespace std;

int n;
int isused1[20];
int isused2[40];
int isused3[40];
vector<vector<int>> board;

void printBoard() 
{
    cout << "====" << endl;
    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++) 
        {
            if (board[i][j] == 1) 
            {
                cout << "Q ";
            }
            else 
            {
                cout << ". ";
            }
        }
        cout << endl;
    }
    cout << "====" << endl;
}

void Choose(int cur)
{
    if (cur == n)
    {
        printBoard();
        return;
    }

    for (int i = 0; i < n; ++i)
    {
        if (isused1[i] || isused2[i + cur] || isused3[cur - i + n - 1])
            continue;
        isused1[i] = 1;
        isused2[i + cur] = 1;
        isused3[cur - i + n - 1] = 1;        
        board[cur][i] = 1;
        Choose(cur + 1);        
        isused1[i] = 0;
        isused2[i + cur] = 0;
        isused3[cur - i + n - 1] = 0;
        board[cur][i] = 0;
    }
}
int main()
{
    cin >> n;

    board.resize(n, vector<int>(n, 0));
        
    Choose(0);
}

 

1 - 2. boj 14888 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

• 기본적인 백트래킹 문제와 유사하다.
• 부호갯수를 통해 사용할 수 있는 부호인지 체크하는 과정만 있으면 된다.

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

int n;
int board[12];
int sign[4];
vector<int> ans;
int answerMax = INT_MIN;
int answerMin = INT_MAX;

void Choose(int cur)
{
	if (cur == n - 1)
	{
		int temp = 0;
		for (int i = 0; i < n; ++i)
		{
			if (i == 0)
				temp = board[i];
			else
			{
				if (ans[i-1] == 0)
				{
					temp = temp + board[i];
				}
				else if (ans[i-1] == 1)
				{
					temp = temp - board[i];
				}
				else if (ans[i-1] == 2)
				{
					temp = temp * board[i];
				}
				else if (ans[i-1] == 3)
				{
					temp = temp / board[i];
				}
			}
		}
		answerMax = max(answerMax, temp);		
		answerMin = min(answerMin, temp);
		return;
	}
	for (int i = 0; i < 4; ++i)
	{
		if (sign[i] > 0)
		{
			sign[i]--;
			ans.push_back(i);
			Choose(cur + 1);
			sign[i]++;
			ans.pop_back();
		}
	}
}

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

	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> board[i];
	}

	for (int i = 0; i < 4; ++i)
	{
		cin >> sign[i];
	}

	Choose(0);

	cout << answerMax << "\n" << answerMin;
}

 

1 - 3. boj 14889 스타트와 링크

https://www.acmicpc.net/problem/14889

• 처음 풀었을 때 시간초과가 발생했다.
• 시간 초과 발생 원인은 같은 경우의 수를 또 검색해서 생기는 결과이다.
  • 예를들어, {0 1 2} {3 4 5} 의 경우와 {3 4 5} {0 1 2} 는 같은 경우인데, 이런 경우를 모두 체크했기 때문이다.
  • 이 문제를 해결하기 위해 isused 체크 후 ans라는 벡터가 비어있는 경우나 비어있지 않은 경우 원래 가진 값보다 큰 값이 들어올 때만 ans 벡터에 값을 넣을 수 있도록 if문을 추가해주어서 문제를 해결하였다.

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

int n;
int board[20][20];
int isused[20];
vector<int> ans;
vector<int> ans2;
int answer = INT_MAX;

int Check(const vector<int>& ans)
{
	int temp = 0;
	for (int i = 0; i < ans.size(); ++i)
	{
		for (int j = i + 1; j < ans.size(); ++j)
		{
			temp += (board[ans[i]][ans[j]] + board[ans[j]][ans[i]]);
		}
	}
	return temp;
}

void Choose(int cur)
{
	if (cur == n / 2)
	{
		int scoreA = 0;
		int scoreB = 0;

		for (int i = 0; i < n; ++i)
		{
			if (!isused[i])
				ans2.push_back(i);
		}

		scoreA = Check(ans);
		scoreB = Check(ans2);
		
		answer = min(answer, abs(scoreA - scoreB));
		ans2.clear();

		return;
	}
	for (int i = 0; i < n; ++i)
	{
		if (!isused[i])
		{
			if (ans.empty() || (!ans.empty() && ans.back() < i))
			{
				isused[i] = 1;
				ans.push_back(i);
				Choose(cur + 1);
				isused[i] = 0;
				ans.pop_back();
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> board[i][j];
		}
	}
	
	Choose(0);

	cout << answer;
}

• 추가) 
  • Choose 함수에 매개변수 하나를 더 추가하여, start하는 지점을 지정할수도 있다.
  • 위 방식보다 깔끔하지만, 아직 익숙하지는 않다.

void Choose(int cur, int start)
{
	if (cur == n / 2)
	{
		vector<int> a;
		vector<int> b;

		for (int i = 0; i < n; ++i)
		{
			if (isused[i])
				a.push_back(i);
			else
				b.push_back(i);
		}

		int scoreA = Check(a);
		int scoreB = Check(b);
		
		answer = min(answer, abs(scoreA - scoreB));

		return;
	}
	for (int i = start; i < n; ++i)
	{
		if (!isused[i])
		{
			isused[i] = 1;
			Choose(cur + 1, i + 1);
			isused[i] = 0;
		}
	}
}

 

 

2. 알고리즘

---

정렬 및 탐색 알고리즘에 대해서 다시 한번 정리해 보면 좋을 것 같아서 이전에 공부했던 내용에

병합정렬과 이분탐색을 추가하여 글을 정리해 보았습니다.

https://gbleem.tistory.com/128

정렬 및 탐색 알고리즘 정리

 

 

3. CS

---

OS 및 CS관련 내용을 공부하다가 중요한 부분에 대해 추가적으로 정리해 보았습니다.

https://gbleem.tistory.com/129

OS & CS 몇 가지