728x90 분류 전체보기58 [자료구조] 다익스트라 알고리즘 최단 경로를 구하는 방법은 다양하다. 그 중 다익스트라 알고리즘에 대해 알아보자다익스트라 알고리즘이란?각 경로의 가중치를 비교해서 최단거리 경로를 찾아내는 알고리즘이다.가중치가 양수인 그래프에서 활용이 가능하며, 음수인 경우는 벨만-포드 알고리즘을 사용하면 된다 어떻게 작동할까?다익스트라 알고리즘의 작동 과정은 다음과 같다.1. 출발 노드를 설정한다.2. 최단 거리 테이블을 초기화 한다. 이때 초기화 값은 inf 또는 아주 큰 수로 잡는다.3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 찾고 해당 노드를 방문 처리한다.4. 해당 노드를 거쳐 다른 노드로 넘어가는 가중치를 계산해 최단 거리 테이블을 업데이트 한다.5. 3~4 과정을 최.. 2025. 6. 9. [자료구조] 그래프와 순회(BFS, DFS) 자료구조는 크게 두 종류로 나뉜다.선형 구조와 비선형 구조가 바로 그것이다. 비선형 구조에 속하는 그래프를 소개해 보고자 한다. 그래프란?그래프는 비선형적 자료 구조로, 한정된 Node들 사이에 간선으로 연결된 형태들로 구성된 것들의 집합이다.일반적으로 그래프를 G, node를 V, 간선을 E라고 한다.그래프 사이의 연결은 e1(V1,V2) 이런식으로 나타낸다.해당 그래프가 Directed(방향성) 그래프라면 "V1에서 V2로 가는 e1으로 이어져 있다"정도로 이해하면 되겠다.만약 Undirected(무방향) 그래프 라면 "V1, V2가 e1으로 이어져 있다"로 이해하면 되겠다. 그래프 용어 추가 정리그래프를 다루기 전에 알아야 하는 몇 가지 용어가 있다.먼저 loop이다.루프라는 이름에서 볼 수 있 듯.. 2025. 6. 9. [자료구조] Hash 지난 글에서는 O(N)인 선형 탐색과 O(logN)인 이분 탐색까지 알아봤다. 그러나 더 빠른 방법이 있다.무려 O(1)이 가능한 Hash방법이다. 마치 마법처럼 '띡' 하고 바로 찾아내는 것이다.Hash란?Hash는 key-value로 데이터를 다루는 방법으로 함수와 테이블로 이루어져 있다.어떤 데이터가 입력으로 들어오면 미리 정해놓은 Hash 함수를 이용해서 특정한 값을 구해낸다.그 다음 그 값에 해당하는 위치에 값을 저장한다.그렇게 하면 나중에 그 값을 찾을 때 똑같이 Hash 함수에 넣어서 그 값이 저장된 곳을 반환하면 즉각적으로 값을 찾을 수 있다. 만약 그 값의 위치가 중복된다면???Hash 알고리즘의 차이는 충돌(collision)이 일어나는 경우에 어떻게 처리하느냐는 것이다.해시 함수를 이.. 2025. 6. 8. [자료구조] 탐색 알고리즘 (선형탐색 & 이분탐색) 옛날에 집에서 어떤 책이 다음날 꼭 필요해서 찾으려고 보면 보이지 않는 일이 종종 있었다.결국 집의 모든 책장을 하나하나 뒤져서 찾아내거나, 몇번씩이나 반복해서 찾아봤지만 찾을 수 없었던 기억이 있다.당시에는 인터넷 검색처럼 딱 책 제목을 찾으면 어딨는지 마법처럼 알아내면 좋을 것 같다는 생각을 한 적이 있다.컴퓨터과학을 전공하니 이제는 컴퓨터로 똑같은 짓을 종종한다. 물론 직접 찾지는 않고 컴퓨터가 대신 찾기는 한다. 기초적인 탐색 알고리즘가장 기초적인 탐색 알고리즘은 Linear Search(선형 탐색)이다.말 그대로 있는 데이터를 처음부터 끝까지 순회하면서 찾아내는 방법이다.컴퓨터는 1초에 몇십억번 정도의 연산을 할 수 있기 때문에 O(N)인 이 방법을 사용하면 아주 많은 정보라도 몇초 ~ 몇분 정.. 2025. 6. 8. [자료구조] Merge Sort, Heap Sort, Quick Sort 이번 정렬 알고리즘은 분할 정복 기법을 활용한 알고리즘들인 Merge Sort, Quick Sort 그리고 Heap 구조를 사용한 정렬기법인 Heap Sort를 정리해보려고 한다. 분할정복 기법이란?분할 정복이란, 큰 문제를 해결하기 쉬운 작은 문제들로 나눠서 해결해나가 결국 전체 문제를 해결하는 기법이다. 알고리즘 뿐 아니라 정치, 군사 등 다양한 분야에서 사용되는 기법이다.분할 정복 알고리즘의 일반적인 큰 흐름은 다음 세 단계로 요약할 수 있다.1. Divide (분할)정렬해야 할 원소들을 두 개의 크기가 비슷한 그룹으로 나눈다. 예를 들어, 길이가 n인 배열이면 인덱스 0 … (n/2 - 1)을 왼쪽 그룹, 인덱스 (n/2) … (n-1)을 오른쪽 그룹으로 분할한다.2. Conquer (정복, 재귀.. 2025. 6. 6. [자료구조] Selection Sort(선택정렬), Insersion Sort(삽입정렬) 이번에 소개할 알고리즘은 정렬 알고리즘인 Selection Sort와 Insersion Sort이다.두 알고리즘은 모두 최악의 경우 O(N2)의 시간복잡도를 갖는 알고리즘이다. Selection Sort란?Selection Sort는 말 그대로 선택하면서 정렬하는 알고리즘이다.과정은 아래와 같다.1. 앞에서부터 순회하면서 가장 큰 수를 발견하면 맨 뒤로 보내고 고정2. 다시 순회하면서 고정된 범위를 제외하고 가장 큰 수를 발견하면 고정 범위의 앞으로 보내고 고정3. 1과 2의 방법을 반복하면서 고정범위 == 배열의 크기가 될 때까지 진행아래는 정렬되는 예시이다.Selection Sort의 시간복잡도(n-1) 회 반복 * (각 반복마다 최소 요구되는 상수시간 + 적절한 인덱스를 찾는 시간)== O(N2)의.. 2025. 6. 5. 이전 1 2 3 4 5 6 ··· 10 다음 728x90 반응형
