컴퓨터 언어/알고리즘 (4) 썸네일형 리스트형 다익스트라 알고리즘 다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 모든 정점까지의 최단 경로를 찾는 데 사용되는 알고리즘이다. 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#에서 구현되어 있는 자료구조나 기본 문법들의 사용 방식을 배우고 그것들을 응용하는 것을 배웠다면 이번에 배운 설계 기법은 접근 방식이기 때문에 즉각적으로 적용과 응용이 힘들었고 적용 과정이 매우 난해하게 느껴졌었다. 그렇지만 이것은 알고리즘 설계 기법이 수학적인 원리를 기반으로 하고 있고 수학적 사고와 추론을 필요로 하여 문제.. 이전 1 다음
