반응형 코딩테스트 준비/자료구조 & 알고리즘42 C# - 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree)모든 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값들만 가진다. 최소값은 트리의 가장 왼쪽, 최대값은 가장 오른쪽에 존재한다.중위 순회(inorder traversal)노드의 값을 오름차순으로 방문한다.방문 순서재귀적으로 왼쪽 서브 트리 순회, 현재 노드를 방문(e.g. 값 출), 재귀적으로 오른쪽 서브트리 순회3 - 5 - 10 - 15 - 17 - 20 - 30 - 40 - 50전위 순회(preorder traversal)루트 노드를 먼저 방문방문 순서현재 노드 방문(e.g. 값 출력), 재귀적으로 왼쪽 서브트리 순회, 재귀적으로 오른쪽 서브 트리 순회20 - 5 - 3 - 15.. 2024. 6. 11. C# - 배열을 문자열로 바꾸는 방법 문자열 배열을 문자열로 바꾸기 위해 아래와 같이 작성했다. char[] array = answer.ToArray(); string s = array.ToString(); 그러면 아래와 같이 결과가 나온다. System.Char[] 왜 이런 결과가 나올까? ToString메서드를 사용하게 되면 배열 객체 자체를 문자열로 반환한다. 그러므로 배열의 형식 정보를 나타내는 문자열이 반환되는 것이다. 실제로 배열을 문자열로 바꾸기 위한 방법을 살펴보자 01 새로운 문자열 생성 char[] array = answer.ToArray(); string s = new string(array); 02 string.Join 사용 char[] array = answer.ToArray(); string str = string... 2024. 4. 8. 알고리즘 - 그리디(Greedy) 알고리즘 그리디 알고리즘 미래를 고려히지 않고 오직 현재 시점에 가장 좋은 선택 ex) 백준 - 동전0(11047) 핵심은 최소 동전 수이다. N개의 동전 중 금액이 제일 큰 것부터 가능한 많이 사용하고 그 다음 큰 동전 사용하기를 반복하면 된다. 그러므로 가장 큰 금액부터 최대한 많이 소진하고 뒤에있는 동전은 신경쓰지 않는다. 특징 미래를 신경쓰지 않고 현실에만 충실한 게 최적의 해가 될 수 있을까? 항상 보장하지 못한다. 그러므로 근사 알고리즘이라고 한다. 01 탐욕스런 선택 조건(Greedy Choice Property) 현재의 선택이 미래의 선택에 영향을 주지 않는다. 예를 들어 서울-대전-부산에 가는 방법 02 최적 부분 구조 조건(Optimal Substructure) 부분의 최적 해가 모이면 전체의 .. 2024. 3. 26. C# - 백준 코드 처리 속도(실행 시간) 측정 방법 +) Stopwatch 프로퍼티 및 메서드 설명 Stopwatch Stopwatch 클래스를 사용하기 위해서는 using System.Diagnostics; 네임스페이스를 추가해야한다. using System.Diagnostics; 01 인스턴스 생성 및 코드 실행 시간 측정 시작 Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); 02 코드 실행 시간 측정 종료 stopwatch.Stop(); 03 코드 실행 시간 출력 // 측정된 시간 출력 Console.WriteLine($"코드 실행 시간: {stopwatch.Elapsed}"); // 측정된 시간 출력 (밀리초 단위) Console.WriteLine($"코드 실행 시간 (밀리초): {stopwatch.ElapsedMilliseconds}");.. 2024. 3. 17. C# - 우선순위 큐(Priority Queue)와 힙(Heap) Queue 큐는 FIFO구조로 먼저 들어온 데이터가 먼저 나가는 구조이다. Priority Queue 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다. 예를 들어 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건보다 꺼내서 확인해야 하는 경우이다. 우선순위큐를 구현하는 방법 01 리스트를 이용 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도 삽입시간 O(1), 삭제 시간 O(N) 02 힙(Heap)을 이용 데이터의 개수가 N개 일 때, 구현 방식에 따라서 시간 복잡도 삽입시간 O(logN) (힙의 조건을 유지하기 위해 부모 노드와 비교하면서 올라간다) ,삭제 시간 O(logN)(루트 노드를 삭제한 후 힙을 재조정해야 한다) Heap 완전 이진 트리 자료 구조의 일종이다. 항상.. 2024. 3. 16. C# - 메서드안에서 재귀호출시 실행과정을 알아보자 알고리즘 문제를 풀면서 재귀 호출 실행 과정을 한 번 자세히 다뤄보는게 좋을 것 같다는 생각이 들었다. 과정 01 메서드 안에 다시 메서드를 호출할 경우 재귀 호출이기 때문에 메서드가 호출되면서 현재 실행 중인 함수의 상태를 스택에 저장하고 새로운 함수 호출이 시작된다. 02 새로운 함수의 실행이 끝나면 return을 통해 스택에서 이전 함수의 상태를 꺼내어 계속 진행하게 된다. 예시 static void RecursiveExample(int i) { if (i == 3) { Console.WriteLine($"i == 3 : {i}"); return; // 이전 호출로 되돌아 가기 } Console.WriteLine($"Before recursive call: {i}"); RecursiveExample.. 2023. 12. 22. 이전 1 2 3 4 ··· 7 다음 반응형
