분류 전체보기 (20) 썸네일형 리스트형 다익스트라 알고리즘 다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 알고리즘이다. BFS의 경우 간선의 가중치가 존재할 경우 사용할 수 없기 때문에 이 경우 다익스트라를 사용할 수 있다. 출발점으로 지정된 노드에서 직접적으로 연결되어 있지 않더라도, 다른 노드를 경유하여 갈 수 있는 경로가 존재한다면 경유하는 다른 노드를 거쳐 목표 노드로 가는 비용을 계산하여 출발 노드에서 해당 노드까지의 경로가 존재하는 식으로 취급한다. 가령 해당 그래프를 예시로 들 경우 1번 노드와 4번 노드는 직접적으로 연결되어 있지 않지만 2번 노드를 경유하여 4번 노드로 가는 경로가 존재하기 때문에 1 -> 4 번노드로의 최단 거리는 1->2 , 2->4의 경로의 비용의 합인 5 + 6인 11로 .. 정렬 알고리즘 정렬 알고리즘은 말 그대로 데이터를 특정한 기준에 따라 순서대로 나열하는 알고리즘으로 정렬마다 시간 복잡도와 공간 복잡도에서 차이를 보이기 때문에 상황에 맞게 정렬 알고리즘을 선택하여 사용한다. 정렬은 크게 시간복잡도에서 O(N²)을 가지는 정렬과 O(NlogN)을 가지는 정렬로 나눌 수 있는데 시간 복잡도가 높으면 공간복잡도를 낮게 가져가고 반대로 시간 복잡도가 낮으면 그만큼 공간복잡도를 높게 가져가는 양상을 보인다. 시간복잡도가 O(N²)인 정렬은 선택정렬, 삽입정렬, 버블정렬이 있고 O(NlogN)인 정렬은 병합정렬, 퀵정렬, 힙정렬로 구분할 수 있다. [선택 정렬] - O(N²) 주어진 리스트에서 최소/최대값을 찾아 맨 앞부터 순서대로 정렬하는 방식이다. 아래의 코드에선 list의 요소를 순회하여.. DFS , BFS [그래프] 그래프는 노드 혹은 정점이라 불리는 객체들의 모음과 이 객체들을 잇는 간선의 모음의 결합을 뜻한다. 이들 사이의 연결을 뜻하는 간선은 노드들을 연결하며 간선의 방향성에 따라 단방향 그래프, 양방향 그래프로 나눌 수 있고 또 간선의 가중치를 기준으로 할경우 연결 그래프와 가중치 그래프로 나눌 수 있다. 그래프 내에서 각 정점의 인접 관계를 나타내는 행렬을 인접행렬 그래프라고 하는데 2차원 배열을 출발정점과 도착정점으로 표현할 수 있다. 이 인접행렬 그래프를 사용함으로써 얻는 장점은 두 노드간의 연결 여부를 상수 시간 O(1)에 확인할 수 있다는 점이다. 연결을 확인하고자 하는 좌표값이 true인지 false인지, 즉 연결 되었는지 여부를 인덱스로 확인할 수 있기 때문에 연결 여부를 즉각적으로 알.. 알고리즘 설계기법 알고리즘 설계기법 (Algorithm Design Technique) 알고리즘 설계 기법은 문제를 해결하기 위한 알고리즘, 해당 문제의 답을 효과적으로 찾아가기 위한 전략과 접근 방식이다. 문제를 풀 때 어떤 알고리즘 설계 기법을 쓰는지에 따라 효율성에서 막대한 차이를 보이기 때문에 특정 문제 유형에 가장 효과적인 해결책을 찾기 위한 접근 방식을 구할 필요가 있다. [이전까지는 C#에서 구현되어 있는 자료구조나 기본 문법들의 사용 방식을 배우고 그것들을 응용하는 것을 배웠다면 이번에 배운 설계 기법은 접근 방식이기 때문에 즉각적으로 적용과 응용이 힘들었고 적용 과정이 매우 난해하게 느껴졌었다. 그렇지만 이것은 알고리즘 설계 기법이 수학적인 원리를 기반으로 하고 있고 수학적 사고와 추론을 필요로 하여 문제.. [C#] 해시테이블 c#에서 해시테이블은 키-값 쌍을 저장하는 데이터 구조로 키를 사용하여 값을 검색하고 저장할 수 있는 컬렉션이다. 해시테이블은 특정 키에 대한 값을 빠르게 찾을 수 있는 해시 함수를 사용하여 내부적으로 데이터를 저장하는 방식을 사용하는데 이는 키 값을 해시 함수로 해싱하여 해시테이블의 특정 위치로 직접 액세스하도록 만든 방식이다. 여기서 해시는 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑하는 것을 말한다. 예를 들어 임의의 숫자에 % 10의 연산을 통해 나오는 숫자는 한 자리만을 나타내게 되므로 일종의 해시라고 볼 수 있다. 이 해시테이블은 몇가지 특징을 갖고 있는데 앞서 말했듯, 키와 값 쌍을 저장하고 키는 고유해야하기 때문에 중복된 키를 허용하지 않으며, 탐색, 삽입, 삭제에 있어서.. [C#]우선순위 큐와 힙 아래는 우선순위 큐의 기초적인 작성 방식이다. 이렇게 선언시에 클래스명에 붙이는 제네릭 형식에 우선순위가 추가된다는 점과 넣은 순서대로가 아니라 우선순위에 따라 요소가 나온다는 점만 빼면 Enqueue,Dequeue,Peek를 사용한다는 점에서 별반 다를게 없어보인다. 하지만 앞서 정리했던 Queue(큐) 는 PriorityQueue(우선순위 큐)와 이름은 같지만 내부적으로는 전혀 다른 구성을 갖고 있다. 우선 큐는 배열을 기반으로 연속적으로 데이터들을 연속적으로 일렬로 저장하며 새로운 요소가 추가될 경우 Tail에 해당하는 제일 뒤쪽에 추가하고 자료를 꺼낼 때는 Head에 해당하는 제일 앞에서 꺼내는 형식인데 우선순위 큐는 힙 트리(Heap Tree)의 구조를 갖고 있어 새로운 요소를 추가할 때는 힙 .. [c#] 스택과 큐 [스택(Stack)] 스택은 후입선출(LIFO - Last In First Out)의 구조를 가진 자료구조로 가장 최신에 입력된 순서대로 처리해야 하는 상황에 이용한다. 자료구조에서의 스택과 메모리 구조에서의 스택은 각각의 특징에서 차이를 보이고 있다. 먼저 자료구조에서의 스택은 추상적인 데이터 구조이자 프로그래밍에서 데이터를 저장하고 관리하는 데에 사용되지만 메모리 구조에서의 스택은 컴퓨터 메모리의 일부로서 물리적인 형태이며 함수 호출 및 관련 데이터를 메모리에 저장하는 데에 사용한다. 그런데 두 스택은 후입선출의 작동방식을 가지고 있다는 점에서 가장 큰 공통점을 보인다. 이러한 후입선출의 특징은 각 종류의 스택이 있는 부분에서 이점들을 갖고 있다. 먼저 자료구조에서의 스택을 사용했을 때의 이점들을 알.. [C#] 연결 리스트 [연결 리스트(LinkedList)] 연결 리스트는 데이터를 포함하는 노드들을 양방향 혹은 한방향으로 연결하여 만든 자료구조이다. 노드는 데이터와 이전,다음 노드 객체를 참조하는 형식으로 구성되어 있는데 노드는 메모리에 연속적으로 배치되지 않는다. 배열은 인덱스를 통해 요소들에 접근할 수 있지만 메모리상 독립적으로 위치해 있는 노드들에 접근하려면 노드들은 각자가 데이터를 가지고 다음 노드나 이전 노드에 대한 위치 정보에 대해 가지고 있어야 한다. 따라서 C#에서는 LinkedList 클래스와 별개로 LinkedList 클래스로부터 생성된 객체를 이루는 것은 단일 정보들의 나열이 아닌 각 노드들이다. 마찬가지로 링크드 리스트는 인덱스를 사용할 수 없기 때문에 0부터 시작해서 길이보다 작은 수가 될 때까지 .. 이전 1 2 3 다음
