컴퓨터로 이것저것

그래프의 탐색을 하기 위해서는 그래프 정보를 저장해야만 한다. 그래프의 저장 방법 2가지를 살펴보고, 실제 예제를 통해 어떻게 적용되는지 살펴보도록 하겠다. 위와 같은 그래프는 방향성과 가중치를 가지고 있다. 이 그래프를 2가지 방법으로 자료를 정리해 보자. 인접행렬 인접행렬의 경우 2차 배열을 생각하면 쉽다. 이 때 기본 규칙은 간단하다. 각 점을 기준으로 갈 수 있는 방향에 데이터를 저장하며, 갈 수 없다면, 특정한 값을 입력해 놓도록 한다.(기본적으로 0 혹은 -1을 사용한다.) 가중치가 없는 경우라면 0과 1로 표현이 가능하다. 또한, 고민해 보아야 할 것은 방향성을 갖지 않는 경우이다. 예를 들어 위의 예제 그래프의 경우 정점 1에서 2로 이동하는 경로는 1가지 이다. 하지만 방향성이 없는 경우..

벡터 왠 뜬금없는 벡터에 대한 설명인지 하는 사람도 있을 것이다. 우리가 배열을 사용하면서 가장 많이 경험하는 것이 배열의 크기의 문제이다. 기존의 C 혹은 Cpp 에서 배열을 사용할 때 항상 크기의 문제가 우리의 발목을 잡게 된다. 또한 기존의 배열을 사용하게 되면 정보올림피아드 대회에서 문제에 따라서 배열의 크기를 매우 크게 잡기도 한다. 벡터를 사용하면 초기부터 메모리의 낭비를 줄일 수 있기 때문에 사용을 하기도 한다. 한 가지 중요한 점은. 그렇다고 해서 무분별하게 사용하면 오히려 독이 될 수 있음으로 신중하게 사용하도록 하자! (일반적인 경우 독이 되는 경우는 거의 없다.) (수정중입니다.)