그래프 정점(Node, Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 이때 간선은 정점간의 관계를 나타낸다. G = (V, E)로 나타낸다. 자세한 내용은 생략한다. 그래프의 표현 인접 행렬(Adjacency-matrix) 정점의 개수를 V라고 했을 때 VxV크기의 이차원 배열을 이용한다. a[i][j]는 i에서 j로 가는 간선의 존재 유무를 나타낸다.(0: 有, 1:無) 가중치를 표현하고 싶다면 0일때 간선이 없음, 1이상의 수일때 가중치로 표현할 수 있다. 인접 리스트(Adjacency-list) 리스트를 이용해서 구현한다. A[i]=i와 연결된 정점을 리스트로 표현한다. 리스트는 크기를 동적으로 변경할 수 있어야 하기 때문에, 일반적인 배열은 사용할 수 없다. 가중치를 표현할때는 리스트..

비트마스크 비트마스크를 이용해서 부분집합을 구할 수 있다는 점을 기억하고 가자. not 연산의 경우 자료형에 따라 결과가 달라진다. 또한, unsigned, signed에 따라서 보여지는 값이 달라진다. signed의 경우 가장 앞 자리 비트를 이용하여 음수/양수를 구별하기 때문이다. 정수의 집합을 나타낼 때 사용할 수 있다. 집합에는 같은수가 없기 때문이다. 570을 이진수로 나타내면 1000111010이 되는데, 이는 2^9+2^5+2^4+2^3+2^1로 나타낼 수 있다. 이를 통해서 주어진 수 570를 집합 {1, 3, 4, 5, 9}로 표현할 수 있다. 비트마스크를 사용하게되면 정수를 사용하는 것보다, 공간복잡도가 줄어들게 된다. 비트마스크의 연산 &를 사용하여 비트가 있는지 알 수 있다. |를 ..

재귀 함수 함수 내에서 자기 자신을 다시 호출하는 함수이다. 이 함수를 잘 사용하면 N번의 반복문을 보다 보기 쉽게 작성할 수 있다. 단, 다중 루프문을 사용한 것보다 복잡도가 줄어들지는 않을 수 있다. 재귀 함수는 잘 짜는게 중요한데, 항상 다음의 경우를 고려해야 한다. 조건에 맞지 않는 경우(불가능한 경우) 정답을 찾은 경우 재귀 호출을 하는 경우(다음의 경우를 실행하는 경우) 9095 1, 2, 3 더하기, 백준 온라인 저지 정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제. 주어진 N이 3일 경우, 1, 2, 3의 합으로 나타내는 방법은 아래의 표와 같다. N=4 1+1+1+1 1+1+2 1+2+1 1+1+2 2+1+1 2+2 1+3 3+1 이 때, Ngoal, 즉 합산 결과가 ..

순열 1~N까지 이루어진 순열로, 크기는 항상 N이며 겹치는 숫자가 존재하지 않는다. 크기가 N인 순열은 총 N!개가 존재한다. 순열을 사전순으로 나열했을 때, 다음에 오는 순열과 이전에 오는 순열을 찾을 수 있다. N이 3인 경우 사전순으로 나열한 수열은 다음과 같다. 아래의 표에서 1번째 순열은 오름차순으로 정렬된 순열이 되며, 마지막 순열(6번째 순열)은 내림차순으로 정렬된 순열임을 알 수 있다. 순서 수열 1번째 순열 123 2번째 순열 132 3번째 순열 213 4번째 순열 231 5번째 순열 312 6번째 순열 321 다음 순열 10972 다음 순열, 백준 온라인 저지 위에서 정리한 내용을 토대로 다음에 오는 순열을 찾을 수 있다. A\[i-1\] < A\[i\]를 만족하는 가장 큰 i를 찾는..

오즈모 모바일2의 어플에 탑재된 오브젝트 트래킹 기능을 테스트해봤는데, 아무래도 스마트폰과의 거리가 짧다보니 트래킹 기능이 잘 동작하는지는 쉽게 체감하기 어려웠다. 그러다 문득 360사진을 찍을때나 찍던 연장봉이 생각나서 테스트해봤다. 생각보다 트래킹 결과는 만족스러웠는데, 아쉽게도 연장봉이 오즈모 모바일2의 무게를 버티지 못했다. 그러다 문득 모노포드가 생각나서 연결해봤다. 길이가 긴 만큼 무겁긴하지만, 생각보다 만족스럽게 찍을수 있었다. 운동을 좀 더 해서 근력을 기른다면, 모노포드의 각도를 조절해서 오즈모 모바일2나 모노포드가 영상에 나오지 않게끔 촬영할수도 있을 듯 했다. 설마 이런식으로 운동을 해야겠단 생각을 할 줄은 몰랐는데...

Brute Force 브루트 포스는 모든 경우의 수를 계산해보는 방법이다. 단, 경우의 수를 계산하는 데 걸리는 시간이 주어진 문제의 시간 제한을 넘지 않아야 한다. Brute Force 방식으로 문제를 풀 때 가능한 경우의 수를 모두 계산해본다. 직접 계산을 통해서 구하며, 대부분 손으로 계산해볼 수 있다. 모든 방법을 찾는다. 대표적으로는 직접 계산하는 방법, 반복문 사용, 순열 사용, 재귀 호출, 비트마스크를 사용하여 직접 계산하는 방법이 있다. 각각의 방법을 이용해 답을 구해본다. 그리고 시간 제한을 초과하지 않는 방법을 찾는다. Brute Force 문제의 시간복잡도는 보통 O(경우의 수*방법 1개를 시도해보는데 걸리는 시간 복잡도)가 된다. 일곱 난쟁이 일곱 난쟁이, 백준 온라인 저지 아홉명의..