반응형 코딩테스트 준비/자료구조 & 알고리즘42 C# - 그래프(자료 구조) 이론 (그래프 종류들, 다양하게 코드로 구현해보기) 그래프 정점과 간선을 조합으로 이루어져있다. 그래프의 종류는 무방향 그래프(간선에 방향이 없는 경우), 방향 그래프(간선에 방향이 있는 경우), 가중치 그래프(간선에 가중치 정보가 추가된 경우)등이 있다. 01 무방향 그래프 간선에 방향이 없는 경우 02 가중치 그래프(Weighted Graph) 간선에 가중치 정보가 추가된 경우 간선에 대한 가중치를 이용해서 최단 거리를 구할 수 있다. 03 방향 그래프 간선에 방향이 있는 경우 그래프를 어떻게 구현할까? 인스턴스 생성으로 구현 단점 : Vertex인스턴스 생성 부담이 크다. 01 정점클래스 만들기 List에는 해당 정점과 연결된 간선들을 저장한다. class Vertex { public List edges = new List(); } 02 정점들을 저.. 2023. 7. 13. C# - 큐(Queue) Queue FIFO(First-In-First-Ou)t - 먼저 들어간애가 제일 먼저 나온다. Queue queue = new Queue(); 관련 메서드 01 Enqueue 큐에 요소 추가 queue.Enqueue(1); 02 Dequeue 큐의 제일 앞 요소 제거 queue.Dequeue(); 03 Count 큐의 저장된 요소의 수 반환 int count = queue.Count; 04 Contains 큐에 특정 요소가 있는지 여부 확인 bool contains = queue.Contains(1); 05 ToArray 큐의 모든 요소를 배열로 반환 string[] elements = queue.ToArray(); 코드 예시 01 Enqueue를 5번한 결과 Queue queue = new Queue(.. 2023. 7. 13. C# - 스택(Stack) Stack LIFO(Last-In-First-Out) - 마지막에 들어간애가 제일 먼저 나온다. Stack stack = new Stack(); 관련 메서드 01 Push 스택에 요소 추가 stack.Push(1); 02 Pop 스택의 맨 위 요소 제거 stack.Pop(); 03 Peek 맨 위의 요소 반환 int data = stack.Peek(); 04 Count 스택 요소 갯수 반환 int count = stack.Count; 05 Clear 스택의 모든 요소 제거 stack.Clear(); 06 ToArray 스택의 요소들 배열로 변환 int[] elements = stack.ToArray(); 코드 예시 01 push를 5번 한 결과 Stack stack = new Stack(); stack... 2023. 7. 13. C# - Big-O 표기법 Big-O표기법 알고리즘의 효율성을 분석하고 측정하기 위해 사용된다. 알고리즘의 성능을 분석 할때, 입력 데이터의 크기가 증가함에 따라 알고리즘의 연산량이 어떻게 증가하는지가 중요하다. BIG-O표기법 1단계 : 대략적인 계산 수행되는 연산의 개수를 대략적으로 판단한다. 연산이 1개이면 1로 표기 반복문이 한개이고 연산이 1개이면 N + 1 표기 반복문이 두개이고 연산이 1개이면 N² + 1 표기 BIG-O표기법 2단계 : 대장만 남긴다 1)영향령이 가장 큰 대표 항목만 남기고 삭제한다. 예를 들어 2N² + 3N + 1이라면 2N²만 남기고 다 삭제한다. 2)상수 무시(2N² -> N²) 상수 값은 데이터의 크기가 무한히 커질 때 영향력이 작아지기 때문에 표기법에서 무시한다. 위에서 설명한거와 같이 B.. 2023. 7. 13. C# - Random 클래스( +) 반복문 안에서와 밖에서의 차이 ) Random 클래스 난수를 생성하는데 사용되는 클래스 Random 생성자 01 시드 값을 직접 지정하지 않는 경우 Random random = new Random(); 02 시드 값을 직접 지정 하는 경우 시드 값을 지정하는 경우 동일한 순서의 난수를 생성하면서 동일한 난수 시퀸스가 생성된다. Random random = new Random(33); 시드(Seed) 값 이란? 컴퓨터는 난수 생성 알고리즘을 사용하여 난수를 사용하는데 난수 생성 알고리즘을 실행하기 위해 사용(시작)되는 값이다. 만약 시드 값을 지정하지 않고 생성된 경우 시스템 시간을 기반으로 자동으로 시드값이 선택된다. 시드 값을 지정한 경우 동일한 난수 시퀀스가 생성되면서 Next()메서드를 호출하더라도 항상 동일한 순서의 난수가 반환된.. 2023. 7. 4. C# - List shuffle 시키는 법, 리스트 섞는 법 입력된 정수 리스트를 섞은 후 새로운 리스트 반환하는 메서드 만들기 public static List Shuffle(int count) { } 01 반환할 새로운 리스트 만들기 List listToReturn = new List(); 02 난수 사용을 위해 Random 객체 만들기 Random random = new Random(); 03 랜덤한 위치로 i값 insert하기 for (int i = 0; i < count; i++) { int index = random.Next(0, i + 1); listToReturn.Insert(index,i+1); } 실행 순서도 04 반환 return listToReturn; 실행 결과 List numbers = new List { 1, 2, 3, 4, 5 }; C.. 2023. 7. 4. 이전 1 2 3 4 5 6 7 다음 반응형
