TIL 2018-10-25

오늘 배운 것 & 한 것

---

• algorithm
  • bj 11724 - 연결 요소의 개수.cpp
  • jmbook 종만북 스터디 (정리)
• dep
• ref

algorithm

bj 11724 - 연결 요소의 개수.cpp

질문 중에 인접배열 대신 인접리스트를 쓰라는 답변이 있던데 차이가 있나?

아직 제출 안함.

int vv[1001];
int edge[1001][1001];

int search(int start, int fillval);

void solve() {
	int n, m;
	cin >> n >> m;

	int ans = 0;

	for (int mm = 0; mm < m; mm++)
	{
		int start, end;
		cin >> start >> end;
		edge[start][end] = 1;
		edge[end][start] = 1;
	}

	for (int i = 1; i <= n; i++)
	{
		if (search(i, ans + 1) == 1) {
			ans++;
		}
	}

	cout << ans << endl;
}

int search(int start, int fillval) {
	if (vv[start] != 0) return 0;

	vv[start] = fillval;
	for (int i = 1; i <= 1000; i++)
	{
		if (edge[start][i] == 1) {
			search(i, fillval);
		}
	}

	return 1;
}

jmbook 종만북 스터디 (정리)

• O 표기법의 O는 오더 라고 읽는다.

-> $O(N^2)$은 오더 엔 제곱 이라고 읽는다

• O 표기법 정의 : $N$에 대한 함수 $f(N)$이 주어질 때, $f(N) = O(g(N))$이라고 쓰는 것은 다음을 의미한다:

충분히 큰 $N_0$와 $C(N_0, C>0)$를 적절히 선택하면 $N_0<=N$ 인 모든 $N$에 대해 $

f(N)

<= C*

g(N)

$이 참이 되도록 할 수 있다.

dep

ref

---