발자취

다익스트라(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..

https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소스코드 처음에 문제를 풀 때 다음 문제설명에 있는 "진행 중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다." 부분이 잠시 멈춘 과제가 그다음 진행 중인 시간 안에 온전히 포함될 때 한번에 끝내야 하는 줄 알았다 만약 멈춰둔 과제가 10분이 남았고 진행 중이던 과제가 종료되고 다음 과제까지 5분이 남았다면 멈춰둔 과제는 -5분을 해줘야 하는 것 을 나중에 깨..

보호되어 있는 글입니다.

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 =..

https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 소스코드 마지막 answer ++ 하는 이유는 마지막 미사일은 요격을 안항 상태로 반복문을 빠져나오기 때문이다. using System; using System.Collections.Generic; using System.Linq; public class Solution { public int solution(int[,] targets) { int answer = 0; List list = ne..

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