기록보관소

가장 최근에 삽입된 원소부터 삭제되는 동적 집합 자료 구조(후입선출, LIFO, Last in First out) 원소를 삽입하는 연산은 push, 원소를 추출하는 연산을 pop이라고 한다. 스택의 top은 가장 최근에 삽입된 원소를 가리킨다. top = 0 이면 스택을 비어있다는 것이며 이때 pop을 실행하면 스택 부족(underflow) 오류가 발생한다. 반대로 스택이 가득찬 상태에서 원소를 삽입하면 스택 포화(overflow) 오류가 발생한다. push, pop의 수행시간 모두 O(1)의 수행시간이 걸린다.

그래프를 깊이 검색하는 알고리즘이다. 최근에 발견되었으나 아직 조사되지 않은 간선을 가진 정점에서 나오는 간선을 조사하고, 그 간선들의 조사가 끝나면 그 정점이 유래한 정점으로 되돌아가 해당 정점에서 나오는 간선을 조사한다. 출발점으로부터 도달가능한 모든 정점을 발견할 때까지 검색이 계속되며, 발견되지 않은 정점이 있다면 다른 출발점을 선택하고 검색을 반복한다. 너비 우선 검색과 달리 출발점이 여러 개가 있는 것으로 생각하지만 이는 알고리즘의 응용할 때 필요가 반영된 결과이다. 검색을 하면서 새로운 원소를 발견하면 그 원소에는 직전원소를 기록하며, 이를 통해 직전원소 부분 그래프를 형성할 수 있다. 너비 우선 검색과 달리 출발점이 여러 개가 될 수 있기 때문에 깊이 우선 트리의 개수 또한 여러 개가 될 ..

BFS는 간단한 검색 알고리즘으로 많은 그래프 알고리즘의 원형이 되는 알고리즘이다. 발견된 정점과 발견되지 않은 정점 사이의 경계선을 균일하게 확장시켜나간다는 사실에서 너비 우선 검색이라는 이름이 유래하게 되었다. 즉, 거리가 k인 정점을 모두 탐색한 후에 k+1의 거리를 갖는 정점을 탐색한다는 뜻이기도 한다. 특징적인 부분으로 이 알고리즘은 그래프 내의 하나의 출발점에서 도달이 가능한 모든 정점을 체계적으로 검색하는 알고리즘이다. (검색이란 그래프 내의 정점을 방문하기 위해 간선을 규칙에 맞춰 따라가는 행위이다.) 또한, 출발점에서 도달이 가능한 모든 정점을 포함하는 너비 우선 트리를 만들며, 이때 각 정점까지의 단순 경로는 출발점에서 특정 정점까지의 거리를 의미한다. (거리란 정점과 정점 사이의 최소..

인접 리스트, 인접 행렬로 그래프를 표현할 수 있습니다. 이 두 방식은 방향, 무방향 그래프 모두에 적용할 수 있습니다. 대개 간선의 개수가 적으면 인접 리스트로 표현하며, 간선의 개수가 많은 경우 인접 행렬로 표현합니다. 보통 두 정점을 연결하는 간선이 있는지 빠르게 확인할 때는 인접 행렬을 사용합니다. 인접 리스트 표현법(adjacency-list representation)에서는 V개의 리스트로 그래프의 간선을 표현합니다. 각각의 리스트는 그래프 내의 하나의 정점에 대해 연결된 다른 정점들을 포함합니다. 무방향 그래프의 경우, (u,v)에 대해 u의 리스트와 v의 리스트 각각에 서로의 정점을 저장하고, 방향 그래프의 경우, u의 리스트에 대해 v 정점을 저장합니다. 따라서 무방향 그래프의 경우 리스..

IF(A, B, C) -> A가 참이면 B를 출력, 아니면 C를 출력 IFERROR(A, B) -> A가 오류이면 B를 출력, 아니면 A 출력 ISERR(A) -> A가 #N/A 제외한 오류라면 TRUE, 아니면 FALSE ISERROR(A) -> A가 오류면 TRUE, 아니면 FALSE ISLOGICAL(A) -> A가 논리값이면 TRUE, 아니면 FALSE ISNUMBER(A) -> A가 숫자면 TRUE, 아니면 FALSE

단순 명제의 진리 값과 관계없이 복합 명제가 항상 참이다. -> 논리적 참 단순 명제의 진리 값과 관계없이 복합 명제가 항상 거짓이다. -> 논리적 모순 그 외(거짓일수도 참일수도) -> 우연적 명제

스타트와 링크 문제는 N명의 사람들을 두 집합으로 나누고 각 집합별로 능력치 합을 구하여 가장 적은 집합 간의 능력치 합의 차를 출력하는 문제입니다. 집합을 나누는 데 모든 가능한 경우의 수를 탐색하기 위해 백트래킹 기법을 사용하였습니다. 이때 주의해야 할 점은 자칫 똑같은 집합을 두 번 중복하여 계산할 수 있다는 점입니다. A집합에 있는 원소들이 그대로 B집합에 있는 상황입니다. 이러한 불필요한 연산을 방지하기 위해서는 어느 특정한 원소를 특정한 집합에만 존재한다고 미리 가정하여야 합니다. 예로 들어서 1을 기준으로 둘 때 모든 경우는 1을 포함한 집합과 포함하지 않는 집합으로 이루어져 있다는 것을 확인할 수 있습니다. 이때 1이 A집합에만 존재한다고 가정하면 똑같은 원소의 종류로 분할된 상황에서 B집..

레벨 210의 미하일 캐릭터로 페리온의 심부름꾼 업적을 달성하려고 했으나 페리온의 평화와 자칭 페리온 최고의 요리사 퀘스트를 받을 수가 없었다.... 인터넷에서 열심히 검색을 해본 결과 레벨 20이상의 모험가 직업으로만 받을 수 있는 퀘스트였다. 이 글을 읽는 독자가 만약 페리온의 심부름꾼 업적을 깨고자 한다면 레벨 20 이상의 모험가 캐릭터를 보유하기를 추천한다....