발자취

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소스코드 using System; using System.Collections.Generic; public class Solution { bool[,] found; public int[] solution(string[] maps) { found = new bool[maps.Length, maps[0].Length]; List answer = new List(); for (int i = 0; i ..

https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소스코드 시간을 다루는 예약 같은 경우 orderby를 통해 시간순으로 정렬하여 끝시간과 첫 시간만 비교한다. using System; using System.Collections.Generic; using System.Linq; public class Solution { public int solution(string[,] book_time) { var roomList = new List();..

이진트리는 한 노드에 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..

https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소스코드 using System; using System.Collections.Generic; public class Solution { static Pos _end; public int solution(string[] maps) { int answerL = 0; int answerE = 0; Pos startPos = null; for (int i = 0; i < maps.Length; i++..

다익스트라(Dijikstra) 다익스트라 알고리즘은 정점에서 모든 정점의 최단경로를 구하는 알고리즘이다.BFS는 가중치가 존재한다면 사용하기에 부적절하지만 다익스트라는 가중치가 있는 그래프에 적절하다. 다익스트라 알고리즘은 예약한 가장 가까운 정점으로 이동을 하며 이동한 정점에서도 다시 인접한 정점을 조사하여 상황에 따라 발견한 정점의 최단거리를 갱신한다. 다익스트라(Dijikstra) 2차 배열 사용 class Graph { int[,] adj = new int[6, 6] { { -1, 15, -1, 35, -1, -1}, { 15, -1, 05, 10, -1, -1}, { -1, 05, -1, -..

동적배열 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..