이것 저것 &

HLS(Http Live Streaming) 는 Apple(아이폰, 아이패드) 에서 사용하는 표준 HTTP 기반 스트리밍 프로토콜입니다. 프로토콜에서 스트리밍 데이터를 m3u8의 확장자를  가진 재생목록 파일과 잘게 쪼개놓은 다수의 ts 파일(동영상)을 HTTP를 통해 전송하는 방식을 사용합니다. 

• – m3u8 : m3u 파일인데, UTF-8 로 인코딩 되어 있다는 것
• – m3u : 멀티미디어 파일의 재생목록을 관리하는 파일
• – ts : MPEG-2 의 Transport Stream 포맷

apple의 수요가 증가하면서 자연스럽게 HLS의 수요도 증가하였고, 현재는 ios가 아니더라도 HLS를 많이 사용하고 있습니다. 

 이 프로토콜은 여러 미디어 플레이어, 웹 브라우저, 모바일 기기, 스트리밍 미디어 서버에서 지원되고 있습니다. 연간 비디오 산업 조사에 따르면 가장 대중적인 스트리밍 포맷으로 간주됩니다.

표준 HTTP 트랜잭션에 기반한 HTTP 라이브 스트리밍은 RTP 등 UDP 기반 프로토콜과 달리 표준 HTTP 트래픽을 통해 방화벽이나 프록시 서버를 경유할 수 있습니다. 또, 널리 이용되는 HTTP 기반 콘텐츠 전송 네트워크를 통해 콘텐츠를 전통적인 HTTP 서버로부터 제공받을 수 있습니다. 이 표준은 또한 표준 암호화 매커니즘과 HTTPS를 이용한 보안 키 배포를 사용하며 이 둘은 단순한 DRM 시스템을 제공하게 됩니다. 이 프로토콜의 후반 버전은 트릭 모드 빨리감기와 되감기, 자막 연동을 제공합니다.

출처:

ko.wikipedia.org/wiki/HTTP_%EB%9D%BC%EC%9D%B4%EB%B8%8C_%EC%8A%A4%ED%8A%B8%EB%A6%AC%EB%B0%8D

문제링크:www.acmicpc.net/problem/13549

대부분

• 순간 이동(0초 소요)은 걷는 이동(1초 소요)보다 더 빠르기때문에, 우선 순위가 높다. 

라는 조건을 생각해서 deque나 우선순위 큐를 사용해서 구현하셨더군요!

저는 일반 큐를 사용해서 구현했습니다. (수가 100,000까지 이기때문에 모든 방문노드를 들러도 된다고 인지했습니다. )

아래는 정답코드입니다.

천천히 확인해보세요.

#include <iostream>
#include <queue>
using namespace std;
int n = 0, k = 0;
int visited[100001] = { 0, };


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	queue <int> que;


	cin >> n >> k;
	que.push(n);
	visited[n] = 1;

	while (!que.empty()) {
		
		int v = que.front();
		que.pop();
		//cout << v << endl;
		for (int j = v; j <= 100000; j *= 2) { // 0초 후에 2*X의 위치로 이동
			if (j == 0) break;
			if (visited[j] == 0) {
				visited[j] = visited[v];
				que.push(j);
			}
		}
		if (visited[v + 1] == 0 && (v+1) <= 100000) {
			visited[v + 1] = visited[v] + 1;
			que.push(v + 1);
		}
		if (visited[v - 1] == 0 && (v-1) >= 0) {
			visited[v - 1] = visited[v] + 1;
			que.push(v - 1);
		}



	}

	cout << visited[k] - 1 << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/1967

문제풀이를 위해선 

1.가장 깊은 노드 중 가중치가 가장 큰 노드를 찾는다.

2. 찾은 노드를 기준 정점으로 잡고, 다시 한번 가장 가중치가 큰 노드를 찾는다.

2가지를 수행하면 된다.

왜 이렇게 되는지에 대한 증명은 구사과님 글을 참고하자.

koosaga.com/14

구현난이도는 쉽지만 아이디어 캐치가 어려운 문제였다.

이래서 개발자는 수학베이스가 있어야 하는것인가..

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

int n = 0;
bool visited[10001] = { 0, };
vector <pair<int, int>> arr[10001];

int result = 0;
int destination = 0;

void dfs(int cur, int len) {

	if (result < len) {
		result = len;
		destination = cur;
	}

	for (int i = 0; i < arr[cur].size(); i++) {
		if (visited[arr[cur][i].first] == 0) {
			visited[arr[cur][i].first] = 1;
			dfs(arr[cur][i].first, len + arr[cur][i].second);
		}
	}


}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int s, e, v;
		cin >> s >> e >> v;
		arr[s].push_back(make_pair(e, v));
		arr[e].push_back(make_pair(s, v));
	}

	visited[1] = 1;
	dfs(1, 0); //목적지 구하고
	cout << result << endl;
	
	memset(visited, 0, sizeof(visited));
	result = 0;
	
	visited[destination] = 1;
	dfs(destination, 0);

	cout << result << endl;
	

}

문제링크:www.acmicpc.net/problem/3980

dfs문제입니다. 

전형적인 dfs문제입니다. 백트래킹에 속하는 이유는 문제조건중에서

 각 선수는 능력치가 0인 포지션에 배치될 수 없다.

라는 조건을 수행해야하기 때문입니다.

일반적인 dfs 방식을 사용해서 구현했습니다.

아래는 정답코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t = 0, result = 0;
int arr[11][11] = { 0, };
bool visited[11];

void dfs(int cnt, int sum) {
	if (cnt == 11) {
		result = max(result, sum);
		return;
	}

	for (int i = 0; i < 11; i++) {
		if (arr[cnt][i] == 0)
			continue;
		if (visited[i] == 0) {
			visited[i] = 1;
			dfs(cnt + 1, sum + arr[cnt][i]);
			visited[i] = 0;
		}


	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;

	while (t--) {
		for (int i = 0; i < 11; i++)
			for (int j = 0; j < 11; j++)
				cin >> arr[i][j];
		memset(visited, 0, sizeof(visited));
		result = 0;
		dfs(0, 0);
		cout << result << "\n";
	}

}

문제링크:www.acmicpc.net/problem/16197

문제 조건에 따르며 구현했습니다.

두 동전의 좌표는 각각 c1y(coin 1 y좌표), c2x( coin 2 x 좌표)와 같은 형태로 나타냈습니다.

신경써야할 조건은 아래와 같습니다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
• 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1

조건에 맞추어 구현해주면 되는 dfs 겸 시뮬레이션 문제였습니다. 

아래는 정답코드입니다. 

1. 코인 두개 모두 범위안에 존재

2. 코인 둘 다 범위밖에 존재

3. 두개의 코인 중 하나만 밖으로 나감(결과 도출)

#include <iostream>
#include <string>
using namespace std;
int n, m;
int result = 2e9;
string arr[21]; //0base
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void dfs(int cnt, int c1y, int c1x, int c2y, int c2x) {
	
	if (cnt == 10)
		return;

	for (int i = 0; i < 4; i++) {
		int n1y = c1y + y_ar[i];
		int n1x = c1x + x_ar[i];
		int n2y = c2y + y_ar[i];
		int n2x = c2x + x_ar[i];
		if (n1y >= 0 && n1y < n && n2y >= 0 && n2y < n && n1x >= 0 && n1x < m &&  n2x >= 0 && n2x < m) {
			if (arr[n1y][n1x] == '#' && arr[n2y][n2x] == '#')
				continue;
			if (arr[n1y][n1x] == '#')
				n1y = c1y, n1x = c1x;
			if (arr[n2y][n2x] == '#')
				n2y = c1y, n2x = c1x;
			dfs(cnt + 1, n1y, n1x, n2y, n2x);
		}
		else if ((n1y < 0 || n1y >= n || n1x < 0 || n1x >= m) && (n2y < 0 || n2y >= n || n2x < 0 || n2x >= m)) {
			continue;
		}
		else {
			if (result > cnt + 1)
				result = cnt + 1;
			return;
		}
	}

}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int c1y, c1x, c2y, c2x;
	bool chk = false;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < m; j++)
			if (arr[i][j] == 'o'&& chk == false) {
				c1y = i, c1x = j;
				chk = true;
			}
			else if (arr[i][j] == 'o'&& chk == true) {
				c2y = i, c2x = j;
			}
	}
	dfs(0, c1y, c1x, c2y, c2x);
	if (result == 2e9)
		cout << -1 << endl;
	else
		cout << result << endl;
	return 0;
}

문제링크:www.acmicpc.net/problem/2239

일반적인 스도쿠문제와 동일합니다.

 다만,  "제일 작은 경우를 출력한다." 라는 조건이 추가됐습니다.

아래 링크와 같은 방법으로 해결해도 됩니다. 

gusdnr69.tistory.com/142

저는 직관적인 방법으로 결과를 도출했습니다.

아래는 정답 코드 입니다.

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

int arr[9][9] = { 0, };
bool fin = false;
vector <pair <int, int>> zero_vec;

void dfs(int cnt) {
	if (cnt == zero_vec.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << arr[i][j];
			cout << endl;
		}
		fin = true;
		return;
	}
	if (fin == true)
		return;

	for(int i=cnt;i<zero_vec.size();i++){}
	int y = zero_vec[cnt].first;
	int x = zero_vec[cnt].second;

	bool temp[10] = { 0, };
	for (int i = 0; i < 9; i++) {
		temp[arr[y][i]] = 1;
		temp[arr[i][x]] = 1;
	}
	for (int i = y / 3 * 3; i < y / 3 * 3 + 3; i++)
		for (int j = x / 3 * 3; j < x / 3 * 3 + 3; j++)
			temp[arr[i][j]] = 1;

	for (int i = 1; i <= 9; i++)
		if (temp[i] == 0) {
			arr[y][x] = i;
			dfs(cnt + 1);
			arr[y][x] = 0;
		}


}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	for (int i = 0; i < 9; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < 9; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 0)
				zero_vec.push_back(make_pair(i, j));
		}
	}
	dfs(0);

	return 0;
}

문제링크:www.acmicpc.net/problem/2529

algorithm 라이브러리에서 제공하는 순열 함수를 사용하여 해결했습니다.

k+1개의 수를 만든 다음 큰 수부터 작은 수순으로, 그리고 작은 수부터 큰 수순으로 차례대로 결과값이 될 수 있는지 확인해주면 결과를 도출했습니다.

처음에 재귀함수로 접근하려고 했는데 생각해보니 굳이 필요없을 것 같습니다. 

아래는 정답코드입니다.

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

int k;
vector <char> arr;
vector <int> val;
bool chk() {

	for (int i = 0; i < arr.size(); i++) {
		if (arr[i] == '<') {
			if (val[i] > val[i + 1])
				return false;
		}
		else {
			if (val[i] < val[i + 1])
				return false;
		}
	}
	return true;
}


int main() {

	cin >> k;
	for (int i = 0; i < k; i++) {
		char temp;
		cin >> temp;
		arr.push_back(temp);
	}
	for (int j = 0, i = 9; j < k + 1; j++,i--) 
		val.push_back(i);
	while (1) {
		if (chk() == true)
			break;
		prev_permutation(val.begin(), val.end());
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;

	val.clear();
	for (int i = 0; i < k + 1; i++)
		val.push_back(i);

	while (1) {
		if (chk() == true)
			break;

		next_permutation(val.begin(), val.end());
		
	}
	for (int i = 0; i < val.size(); i++)
		cout << val[i];
	cout << endl;
	return 0;

}

문제링크: www.acmicpc.net/problem/1799

백트래킹문제입니다. 체스판 크기가 최대 10x10입니다. 그렇기 때문에 가지치기를 통해서 반복 횟수를 줄여주어야 합니다.

• 1. 비숍특성상 검은칸에서 시작하면 검은칸으로만 흰칸에서 시작하면 흰칸으로만 이동가능합니다.
• 2. 그렇기 때문에 흰색과 검은색을 각각 구분합니다. (행 +열이 짝수면 흰색 아니면 홀수면 검은색)
• 2. 각각 비숍을 둘 수 있는지 확인합니다. (abs(arr[cur].y - bitshop[j].y) = abs(arr[cur].x - bitshop[j].x) 면 대각선에 비숍이 있는 것)

아래는 정답코드입니다. 천천히 확인해보세요.

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

typedef struct MyStruct
{
	int y;
	int x;
}chess;
int n = 0, result = 0;
int temp[11][11];
vector <chess> arr; //1인 곳
vector <chess> bitshop; // 비숍저장

void dfs(int cnt, int cur) {// 비숍개수, 현재 탐색 위치 순

	if (cnt > result) {
		result = cnt;
	}
	if (cur == arr.size())
		return;

	//1. 비숍가능한지 검사
	bool jud = true;
	for (int j = 0; j < bitshop.size(); j++) {
		if (abs(arr[cur].y - bitshop[j].y) == abs(arr[cur].x - bitshop[j].x)) {
			jud = false;
			break;
		}
	}
	if (jud == true) { //비숍이 가능하다면 
		bitshop.push_back({ arr[cur].y,arr[cur].x });
		dfs(cnt + 1, cur + 1);
		bitshop.pop_back();
	}
	dfs(cnt, cur + 1);

	return;

}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	int answer = 0;
	for(int i=1;i<=n;i++)
		for (int j = 1; j <= n; j++) {
			cin >> temp[i][j];
			if (temp[i][j] == 1 && (i+j)%2 == 0)
				arr.push_back({ i,j });
		}

	dfs(0, 0);
	answer += result;
	result = 0;
	arr.clear();


	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (temp[i][j] == 1 && (i + j) % 2 == 1)
				arr.push_back({ i,j });
		}
	dfs(0, 0);
	answer += result;
	cout << answer << endl;

	
	return 0;
}