발자취

달팽이 알고리즘(Snail Sort 또는 Spiral Order Traversal)은 행렬(matrix)을 처음부터 끝까지 달팽이의 움직임과 유사하게 순회하는 알고리즘입니다. 이 알고리즘은 행렬의 각 원소를 한 번씩만 방문하면서 순회합니다. 알고리즘의 움직임은 아래와 같습니다: 첫 번째 행을 왼쪽에서 오른쪽으로 순회합니다. 마지막 열을 위에서 아래로 순회합니다. 마지막 행을 오른쪽에서 왼쪽으로 순회합니다. 첫 번째 열을 아래에서 위로 순회합니다. 이 과정을 반복하면서 행렬의 중앙까지 진행하게 됩니다. 만약 행과 열의 크기가 홀수인 경우에는 마지막 단계에서 중앙에 위치한 원소가 중복해서 방문되게 됩니다. 다음은 3x3 행렬에 대한 달팽이 알고리즘의 동작 예시입니다: 1 2 3 8 9 4 7 6 5 이 알고..

순열(Permutation) 순열이란 순서가 부여된 서로 다른 원소배열을 중복없이 순서에 맞게 나열하는 것이다. 예를들어 1,2,3 이란 배열을 순열한다면 아래처럼 된다. 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1 순열을 구하는 기본적인 방법은 재귀를 통해 DEPTH의 위치와 각위치의 숫자를 스왑하여 재귀로 호출하고 다시 원복하는 것 이다. 재귀를 호출 할 때 DEPTH와 i가 같을 때는 원래위치도 순열 중 하나이기 때문에 그대로 진행한다. 종료시에는 DEPTH와 구하려는 길이가 같은 시점에서 재귀를 종료하면 된다. 소스코드 static void Main(string[] args) { int[] datas = new int[] { 1, 2, 3 }; Permutation(datas,..

이진트리는 한 노드에 2개의 노드를 가지고 있는 트리로 외쪽으로 갈수록 값이 현재 값보다 작아지며 오른쪽으로 갈수록 현재 값보다 커진다. 이진검색트리 이진트리는 점점 직전보다 큰 값을 추가한다면 오른쪽으로 추가만 되기 때문에 오른쪽 왼쪽의 균형이 깨질 수 있다. 그래서 이진 검색 트리는 주기적으로 재배치를 통해 균형을 유지해야한다.(AVL, Red-Black) 힙트리 힙트리는 부모노드가 가진 값은 항상 자식 노드가 가진 값보다 크다. 마지막 레벨을 제외한 모든 레벨에 노드가 모두 차있어야 한다. 마지막 레벨에 노드가 있을 떄는 항상 왼쪽부터 순서대로 채워야 한다. 노드 개수를 알면 트리구조는 무조건 확정할 수 있다. 자식 노드 구하는 공식 i번 노드 왼쪽 자식 [(2*i) + 1] i번 노드 오른쪽 자식..

트리는 그래프와다르게 데이터가 동적으로 무수하게 바뀔 때 적합하다. 그렇기 때문에 실제 노드를 만들어 연결해주는 방식으로 사용된다. 트리는 재귀함수와 매우 밀접하다. 트리구현 class TreeNode { public T Data { get; set; } public List Children { get; set; } = new List(); } class Program { static TreeNode MakeTree() { TreeNode root = new TreeNode() { Data = "R1개발실" }; { { TreeNode node = new TreeNode() { Data = "디자인팀" }; node.Children.Add(new TreeNode() { Data = "전투" }); nod..

동적배열 List Add - O(1) RemoveAt - O(N) class MyList { const int DEFAULT_SIZE = 1; T[] _data = new T[DEFAULT_SIZE]; public int Count;// 실제 사용데이터 public int Capacity { get { return _data.Length; } }// 예약한 데이터 개수 //O(1) public void Add(T item) { //1. 공간이 충분히 남아 있는지 확인한다. if(Count>=Capacity) { //공간다시 늘려서 확보 T[] newArray = new T[Count * 2]; for (int i = 0; i < Count; i++) newArray[i] = _data[i]; _data ..

BFS(Breadth First Search 너비 우선 탐색) BFS는 다음에 접근할 정점을 예약하며 예약이 가장 오래된 녀석 부터 순회를 하는 방법으로 Queue를 사용하여 사용한다. BFS는 대표적으로 최단거리 길찾기에서 사용한다. (가중치가 있다면 사용에 부적절하다.) BFS는 가중치가 동일하다는 가정하에 진행하게 된다. BFS(Breadth First Search 2차 배열 사용 class Program { static void Main(string[] args) { int[,] adj = new int[6, 6] { { 0, 1, 0, 1, 0, 0}, { 1, 0, 1, 1, 0, 0}, { 0, 1, 0, 0, 0, 0}, { 1, 1, 0, 0, 1, 0}, { 0, 0, 0, 1, 0, ..

DFS(Depth First Search 깊이 우선 탐색) DFS는 재귀함수를 호출하여 전체적인 순환을 해야한다. DFS(Depth First Search) 2차 배열 사용 class Graph { int[,] adj = new int[6, 6] { { 0, 1, 0, 1, 0, 0}, { 1, 0, 1, 1, 0, 0}, { 0, 1, 0, 0, 0, 0}, { 1, 1, 0, 0, 1, 0}, { 0, 0, 0, 1, 0, 1}, { 0, 0, 0, 0, 1, 0}, }; bool[] visited = new bool[6]; //1) now부터 방문 //2) now와 연결된 정점들을 하나씩 확인해서 [아직 미방문 상태라면]방문 public void DFS(int now) { Console.WriteL..

그래프란 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현한 것 이다. 정점(vertex) 데이터를 표현 간선(Edge) 정점들을 연결관계 표현 1. 가중치 그래프(Weighted Graph) 간선에 수치를 담을 수 있다. ex) 지하철 노선도에서 노선간 걸리는 시간. 2. 방향 그래프(Directed Graph) 간선에 방향이 있는 그래프 ex) 일방 통행이 포함된 도로망, 두 사람 사이의 호감도 구현 1. 연결리스트 사용 객체를 계속 생성해야하기 때문에 비효율 적일 수 있다. class Vertex { public List edges = new List(); void CreateGraph() { List list = new List(6) { new Vertex(), new Vertex(), n..

보호되어 있는 글입니다.

BIG-O 표기법은 수행되는 연산(산술, 비교 등)의 개수를 대략적으로 판단하는 지표로 사용된다. BIG-O 표기법은 단순이 연산을 계산하는 것 이아니라 데이터가 늘어남에 따라서 얼마나 연산이 늘어나냐가 중요하기 때문에 단순한 상수등은 생략을 하게된다. BIG-O를 나타낼 때는 O라고 표시하며 Order of라고 읽는다. 대략적인 계산 //Add = O(1) int Add(int n) { return n + n; } //Add2 = O(N +1) int Add2(int n) { int sum = 0; for (int i = 0; i < n; i++) sum += i; return sum; } //Add3 = O(N^2 + 1) int Add3(int n) { int sum = 0; for (int i =..