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 6588 골드바흐의 추측

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

https://github.com/simjaemun2/BaekJoon/blob/bbb6bed5763440f079afa91844f0632558e8c30e/BOJ6588/BOJ6588.cpp

분류 : 소수 구하기, 에라토스테네스의 체

난이도 : MH

소수 배열을 만든 후, 3부터 답에 맞는지 확인한다.

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)을 사용해도 답을 구할 수 있다.

BOJ 1874 스택 수열

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

https://github.com/simjaemun2/BaekJoon/blob/ddca9cb6c5182a2621cd2c01829daedd8bab1c56/BOJ1874/BOJ18874.cpp

분류 : 스택

난이도 : MH

cnt = 스택에 push 한 값

cnt < input

-> 계속 push

스택.탑 != a

-> 답 없음

else

-> 팝, 다음 단계 계속