BOJ 2186 문자판

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

https://github.com/simjaemun2/BaekJoon/blob/7cc49b8b63da5b0eb628409949adcfe994425ac0/BOJ2186/BOJ2186.cpp

DP

난이도 : H

단순 DFS인줄 알았으나, DP를 이용하지 않으면 시간초과가 발생

BOJ 1517 버블 소트

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

https://github.com/simjaemun2/BaekJoon/blob/573ed75b9d62e5d0b6131fbb55f5fa6790eff75f/BOJ1517/BOJ1517.cpp

난이도 H

버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내느 문제

비슷한 문제로 삽입 정렬을 수행할 때 숫자들을 총 몇 번 옮기는지 계산하기

일반적인 버블소트는  O(N^2) 이기 때문에

문제 조건에서의 수행 시간을 만족하지 못함

이 문제를 풀기 위해선 O(N logN) 시간을 만족해야 함

O(N logN) sort + binary search, 팬윅 트리(바이너리 인덱스드 트리) 등을 이용하는 방법이 있지만

병합 정렬을 이용해서 문제 풀이가 가능

자세한 설명은 JM Book 762 페이지를 참고

BOJ 1080 행렬

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

https://github.com/simjaemun2/BaekJoon/blob/61c09ddf7b85d71c0afa0bcc4b8b580219db07d9/BOJ1080/BOJ1080.cpp

그리디 알고리즘

난이도 MH ~ H

배열의 첫 인덱스부터 따라가면서

A배열과 B배열의 값이 다르면

그 칸을 기준으로 A배열을 뒤집는다.

마지막에 A배열과 B배열이 다른지만 확인한다.

비트 연산으로 구현하면 속도를 줄일 수 있지만

이 문제는 N이 작아서 그런 작업이 불필요하다.

BOJ 1707 이분 그래프

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

https://github.com/simjaemun2/BaekJoon/blob/e966b8ff93461ba2c36383c5ee9392b865eb7a6b/BOJ1707/BOJ1707.cpp

이분그래프

난이도 : MH

이분 그래프란?

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프

-> 인접하고 있는 노드가 서로 다른 2개의 색을 칠하는 것이 가능한 그래프

DFS나 BFS 로 노드를 따라가면서 1이나 -1로 색을 칠한다.

이 때, 인접한 노드의 색이 자신과 같은 색으로 이미 칠해져 있다면, 이분 그래프가 아닌 것을 확인할 수 있음

그런데 인풋 맵 안에 partial graph가 존재할 수 있으므로,

반복문을 통해 모든 노드를 확인해야 함

BOJ 1167 트리의 지름

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

트리, DFS

난이도 MH

트리의 지름이란?

트리의 한 정점(V1)에서 다른 정점(V2) 까지의 거리가 제일 큰 것을 트리의 정점이라 한다.

보통 트리의 지름을 구하는 방법은

아무 정점이나 하나 골라서 가장 거리가 먼 V1을 찾고

그 V1을 이용해 가장 거리가 먼 V2를 찾아 길이를 구하면 트리의 지름이 된다.

#define _CRT_SECURE_NO_WARNINGS 

#include 
#include 
#include 
#include 

using namespace std;

#define MAX_N 100000

int N, A, B, V;

typedef pair PAIR;
vector > input;
bool v1[MAX_N + 1];
bool v2[MAX_N + 1];

PAIR longest(int v, bool* visited)
{
	visited[v] = true;

	PAIR ret = make_pair(0, 0);

	for (int i = 0; i < input[v].size(); i++)
	{
		if (!visited[input[v][i].first])
		{
			PAIR p = longest(input[v][i].first, visited);

			if (ret.second < input[v][i].second + p.second)
			{
				ret.second = input[v][i].second + p.second;
				ret.first = p.first;
			}
		}
	}

	if (ret.first == 0)
		return make_pair(v, 0);
	return ret;
}

int main(int argc, char** argv)
{
#ifdef _WIN32
	freopen("Text.txt", "r", stdin);
#endif

	scanf("%d", &N);

	input = vector >(N + 1);

	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &V);

		while (true)
		{
			scanf("%d", &A);

			if (A == -1)
				break;

			scanf("%d", &B);

			input[V].push_back(make_pair(A, B));
		}

	}

	PAIR p1 = longest(1, v1);
	PAIR p2 = longest(p1.first, v2);
	printf("%d", p2.second);

	return 0;
}

BOJ 1890 점프

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

https://github.com/simjaemun2/BaekJoon/blob/81ca03af7ed86a85aac3b94c02d39adcd4d6b7e2/BOJ1890/BOJ1890.cpp

DP

난이도 : MH

결과 값의 범위에 유의

BOJ 11404 플로이드

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

https://github.com/simjaemun2/BaekJoon/blob/4bf0ae92959236c131b54630b87312a8833a0e0a/BOJ11404/BOJ11404.cpp

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

그래프, 플로이드-마샬, 최단 경로

난이도 : MH

BOJ 2096 내려가기

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

https://github.com/simjaemun2/BaekJoon/blob/7e1e8fa7ca3f040ecabc41ea9954532166dc81ca/BOJ2096/BOJ2096.cpp

분류 : DP

난이도 : MH

문제 조건에서 메모리가 4MB밖에 되지 않으므로,

슬라이딩 기법 등 메모리를 적게 사용하는 방법을 이용한다.

BOJ 10472 십자뒤집기

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

https://github.com/simjaemun2/BaekJoon/blob/25337654f7dcfeac11526bf2ab6d0190897b6c15/BOJ10472/BOJ10472.cpp

분류 : BFS, Bit operation

난이도 : H

N이 3이기 때문에 별 지장이 업지만,

N이 많이 커질 경우를 대비하여 Bit operation으로 구현하였다.

보드의 맨 윗 배열만 버튼을 누르거나 안누르는 모든 경우의 수를 따지면, 총 2 ^ N 의 경우의 수가 나온다.

그 후 0번째 행의 i번째 열이 흑색(1) 일 경우, 1번째 행의 i번째 열을 누른다.

1번 째 행을 0번째 행의 색에 따라 눌러보았을 때, 0번째 행에 검은색이 남아 있는 경우는 답을 구할 수 없는 상태로 함수를 종료한다.

이 후, 마찬가지로 1번째 행의 남은 흑색을 이용해 2번째 행을 눌러본다.

그리고 1번째 행과 2번째 행이 모두 흑색이 없을 때, 저장한 카운트를 이용하여 최소 값을 구한다.

BOJ 11004 K번째 수

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

https://github.com/simjaemun2/BaekJoon/blob/afba3a503bef21b3c6a5cd5af645c2375f4e43ad/BOJ11004/BOJ11004.cpp

분류 : 정렬

난이도 : MH

nth_element()

- 1부터 n 번째 순위  수 까지 정렬

- 모든 범위의 배열을 정렬할 필요가 없을 때 까지 사용

이 문제는, 일반 정렬(N logN)을 사용해도 답을 구할 수 있다.