반응형 코딩테스트 준비/자료구조 & 알고리즘45 최단 경로 알고리즘 총 정리(다익스트라,벨만-포드 알고리즘,A*알고리즘) 최단 경로 알고리즘이란?어떻게 하면 가정 적은 비용으로 목적지에 도착할 수 있을까?를 생각하는 알고리즘이다.1. 다익스트라 알고리즘(Dijkstra Algorithm)하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 단 모든 간선의 가중치는 0보다 크거나 같아야 한다.이 알고리즘의 핵심은 지금 까지 찾은 가장 짧은 길을 기억하고 그걸 이용해서 다음 길을 더 쉽게 계산하는 것이다. 즉 지금까지 찾은 가장 짧은 길을 계속 저장해두고 DP처럼 기존에 구한 결과를 재활용한다. 01 작동 과정distance[] ← ∞, distance[start] ← 0visited[] ← false반복: 현재 노드 ← 방문 안 한 노드 중 최소 distance 인접 노드의 거리 갱신 .. 2025. 4. 17. 탐색 알고리즘 총 정리(선형,이진탐색,해시탐색) 탐색 알고리즘이란탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법 01 선형 탐색(Linear Search)처음부터 끝까지 하나씩 비교하면서 찾는 방식int LinearSearch(int[] arr, int target){ for (int i = 0; i 시간복잡도최악 : O(N)최선 : O(1)02 이진 탐색(Bineary Search)정렬된 배열에서 중간값과 빅하며 절반씩 범위 줄이기조건 : 오름차순 or 내린차순으로 정렬된 데이터여야 한다.int BinarySearch(int[] arr, int target){ int left = 0, right = arr.Length - 1; while (left 시간복잡도 O(logn)03 해시 탐색(Hashing)키(key)를 해시.. 2025. 4. 16. 시간복잡도(빅오표기법)을 왜 알아야할까? 시간복잡도(빅오표기법)을 왜 알아야할까?개발을 할 때마다 매번 작성한 함수나 메서드의 시간 복잡도를 정확하게 계산하진 않는다. 실제 코드를 적을때는 함수 하나가 여러 파라미터를 받고 내부에서 또 다른 메서드를 호출하고 그 메서드가 또 다른 함수를 부르는 식으로 구조가 복잡해지는 경우가 많다. 이런 상황에서 일일이 모든 시간 복잡도를 구하는건 비효율적이고 현실적이지 않다. 그럼 시간복잡도는 신경 안 써도 될까?시간복잡도에 대한 개념을 잘 알고 있다면 코드를 짤때 동작하는 코드를 넘어서 더 나은 코드를 고민할 수 있는 능력이 생긴다.예를 들어 지금 작성하고 있는 코드에서 동작이 되긴하지만 더 최적화된 코드가 없을까?라는 질문을 스스로 할 수 있게 된다. 이는 꼭 O(n)과 O(n²)인지 계산하는게 중요한게 .. 2025. 4. 9. 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. 이전 1 2 3 4 ··· 8 다음 반응형
