동바리의 공부방

문제 :

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

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

int K;
constexpr int MAX = 9;
constexpr int NUM_LENGTH_MAX = 10;
array<char, MAX + 1> inequality{ 0 };
array<int, NUM_LENGTH_MAX + 1> is_visited{ 0 };
vector<string> ans;

bool is_correct(string& temp)
{
	bool ret = true;
	for (int i = 0; i < K; i++) {
		if (inequality[i] == '<') {
			if (temp[i] >= temp[i + 1]) {
				return ret = false;
			}
		}
		else if (inequality[i] == '>') {
			if (temp[i] <= temp[i + 1]) {
				return ret = false;
			}
		}
	}

	return ret;
}

void Run(const int start_idx, const int depth, string temp)
{
	if (is_visited[start_idx]) {
		return;
	}

	is_visited[start_idx] = true;
	temp += to_string(start_idx);
	if (K == depth) {
		if (is_correct(temp)) {
			ans.push_back(temp);
		}

		is_visited[start_idx] = false;
		return;
	}

	for (int i = 0; i <= 9; i++) {
		Run(i, depth + 1, temp);
	}

	is_visited[start_idx] = false;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> K;
	for (int i = 0; i < K; i++) {
		cin >> inequality[i];
	}

	for (int i = 0; i <= 9; i++) {
		Run(i, 0, "");
		memset(&is_visited, 0x00, sizeof(is_visited));
	}

	sort(ans.begin(), ans.end());

	cout << ans[ans.size() - 1] << '\n';
	cout << ans[0] << '\n';
	return 0;
}

• 브루트포스 방법을 이용해 풀 수 있는 문제였습니다.
• 재귀함수를 이용했습니다. 트리의 MAX 깊이가 10 이고, 모든 경우가 깊이 10까지 들어가지 않기 때문에 시간초과가 나지 않을 것이라고 생각했습니다.
• 하지만 생각보다 elapsed time이 컸습니다. 방법을 수정해도 좋을것 같습니다.

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

#include <iostream>
#include <queue>
#include <array>
#include <cstring>
using namespace std;

int col, row;
constexpr int MAX = 100 + 1;
int cheese_map[MAX][MAX];
bool is_visited[MAX][MAX];
const array<int, 4> dx = { -1, 1, 0, 0 };
const array<int, 4> dy = { 0, 0, -1, 1 };
int cnt = 0;
int final_cnt = 0;

namespace curr_state {
	const enum { CHEESE = 1, READY_MELTED, AIR };
}

void change_cheese_to_air()
{
	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			if (cheese_map[i][j] == curr_state::READY_MELTED) {
				cheese_map[i][j] = curr_state::AIR;
			}
		}
	}
}

void search_air()
{
	memset(is_visited, 0, sizeof(is_visited));

	queue<pair<int, int>> air_idx;
	air_idx.push({ 1,1 });
	while (!air_idx.empty()) {
		const int current_air_x_idx = air_idx.front().first;
		const int current_air_y_idx = air_idx.front().second;
		air_idx.pop();
		for (int i = 0; i < dx.size(); i++) {
			const int next_x = current_air_x_idx + dx[i];
			const int next_y = current_air_y_idx + dy[i];
			if (next_x < 1 || next_x > row || next_y < 1 || next_y > col) {
				continue;
			}

			if (is_visited[next_x][next_y]) {
				continue;
			}

			if (!cheese_map[next_x][next_y] || cheese_map[next_x][next_y] == curr_state::AIR) {
				air_idx.push({ next_x, next_y });
				cheese_map[next_x][next_y] = curr_state::AIR;
				is_visited[next_x][next_y] = true;
			}
		}
	}
}

void search_melted_cheese()
{
	memset(is_visited, 0, sizeof(is_visited));

	queue<pair<int, int>> to_be_melted_cheese;
	to_be_melted_cheese.push({ 1,1 });
	while (!to_be_melted_cheese.empty()) {
		const int current_air_x_idx = to_be_melted_cheese.front().first;
		const int current_air_y_idx = to_be_melted_cheese.front().second;
		to_be_melted_cheese.pop();
		for (int i = 0; i < dx.size(); i++) {
			const int next_x = current_air_x_idx + dx[i];
			const int next_y = current_air_y_idx + dy[i];
			if (next_x < 1 || next_x > row || next_y < 1 || next_y > col) {
				continue;
			}

			if (is_visited[next_x][next_y]) {
				continue;
			}

			if (curr_state::AIR == cheese_map[next_x][next_y]) {
				to_be_melted_cheese.push({ next_x, next_y });
				is_visited[next_x][next_y] = true;
			}

			if (cheese_map[current_air_x_idx][current_air_y_idx] == curr_state::AIR &&
				cheese_map[next_x][next_y] == curr_state::CHEESE) {
				cheese_map[next_x][next_y] = curr_state::READY_MELTED;
				to_be_melted_cheese.push({ next_x, next_y });
				is_visited[next_x][next_y] = true;
			}
		}
	}
}

bool is_clear_all()
{
	int remain_cnt = 0;
	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			if (curr_state::CHEESE == cheese_map[i][j]) {
				remain_cnt++;
			}
		}
	}

	if (remain_cnt) {
		final_cnt = remain_cnt;
		return false;
	}

	return true;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> row >> col;
	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			cin >> cheese_map[i][j];
		}
	}

	int cnt = 0;
	while (!is_clear_all()) {
		cnt++;
		search_air();
		search_melted_cheese();
		change_cheese_to_air();
	}
	
	cout << cnt << '\n';
	cout << final_cnt << '\n';

	return 0;
}

** C++ 17 Clang으로 제출합니다. 그렇지 않으면 다음 구문에서 컴파일 에러가 발생합니다.

namespace curr_state {
	const enum { CHEESE = 1, READY_MELTED, AIR };
}

문제 : https://www.acmicpc.net/problem/2580

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 9;
int sudoku[MAX][MAX];
bool row[MAX][MAX + 1]; //열, 1~9
bool col[MAX][MAX + 1]; //행, 1~9
bool square[MAX][MAX + 1]; //3*3 박스 idx, 1~9

int change2SquareIdx(int y, int x) // small square
{
	return (y / 3) * 3 + x / 3;
}

void DFS(int cnt)
{
	if (cnt == 81) {//Sudoku는 총 81칸
		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++)
				cout << sudoku[i][j] << " ";
			cout << endl;
		}
		exit(0); //답을 하나만 출력
	}

	int y = cnt / 9;
	int x = cnt % 9;
	if (sudoku[y][x]) //칸이 채워져있으면
		DFS(cnt + 1);
	else { //채워져있지 않았고	
		for (int k = 1; k <= MAX; k++) {
			//sudoku 규칙에 적합하면 채우고 본다
			if (!col[x][k] && !row[y][k] && !square[change2SquareIdx(y, x)][k]) {
				sudoku[y][x] = k;
				col[x][k] = true;
				row[y][k] = true;
				square[change2SquareIdx(y, x)][k] = true;
				DFS(cnt + 1);
				sudoku[y][x] = 0;
				col[x][k] = false;
				row[y][k] = false;
				square[change2SquareIdx(y, x)][k] = false;
			}
		}
	}
}

int main(void)
{
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			cin >> sudoku[i][j];
			if (sudoku[i][j]) {
				col[j][sudoku[i][j]] = true;							// j열에 sudoku[i][j] 체크
				row[i][sudoku[i][j]] = true;							// i행에 sudoku[i][j] 체크 
				square[change2SquareIdx(i, j)][sudoku[i][j]] = true;	// 작은 사각형의 체크
			}
		}
	}

	DFS(0); //sudoku는 81칸
	return 0;
}

참고 : https://jaimemin.tistory.com/664

1. 삼각형 무게 중심

2. 벡터의 내적, 외적, 넓이

3. 삼각함수

4. 다항함수의 그래프

ebsi에서 모두 학습 가능

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

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

int N;
string num;

void permutation(const char c, const int cnt)
{
    //조건 만족(제일 먼저 나오는 숫자가 제일 작은 수)

    if (cnt - 1 == N) {
        cout << num << "\n";
        exit(0);
    }

    num += c;

    for (int i = 1; i <= cnt / 2; i++) {
        const string&& a = num.substr(cnt - i, i);
        const string&& b = num.substr(cnt - i * 2, i);
        //나쁜 수열

        if (a == b) {
            num.erase(cnt - 1);
            return;
        }
    }

    for (int i = 1; i <= 3; i++) {
        permutation(i + '0', cnt + 1);
    }

    num.erase(cnt - 1);  //cnt - 1 자리가 성립하지 않을 경우
}

int main(void)
{
    cin >> N;
    for (int i = 1; i <= 3; i++) {
        permutation(i + '0', 1);
    }

    return 0;
}

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

N = int(input())
arr = [0 for i in range(N)]

for i in range(0, N):
    num = int(input())
    arr[i] = num

arr.sort()
for i in range(N):

    print(arr[i])

1초라는 시간 제한을 고려했을때, 내장 sort를 이용하면 쉽게 풀 수 있을것이라 생각했고 , 실제로 무난하게 통과했습니다.

#include <iostream>
#include <GL/glut.h>

void display()
{
	glClearColor(1.0f, 0.25f, 1.0f, 1.0f); // 배경 color 지정
	glClear(GL_COLOR_BUFFER_BIT);		   // 지정한 color로 배경 초기화
	
	glColor3f(0.5f, 0.25f, 0.68f);		   // 도형색 지정
	glBegin(GL_TRIANGLES);				   // 도형 타입 선언
	glVertex2f(-0.5f, -0.2f);				// 도형 좌표 선언
	glVertex2f(0.4f, -0.4f);
	glVertex2f(-0.97f, 0.2f);
	glEnd();

	glFinish();
}

int main(int argc, char** argv)
{
	glutInit(&argc, argv);
	glutCreateWindow("OpenGL");
	glutDisplayFunc(display);
	glutMainLoop();
	return 0;
}

삼각형을 그려봤습니다 ㅎㅎ.