생각정리/자료구조&알고리즘 (4) 썸네일형 리스트형 [알고리즘] 비트마스크 비트마스크이란? 비트마스크는 이진수 표기법의 특징을 활용한 비트 연산을 이용해 부분집합을 표현하는 것이다.비트 마스크를 이용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있다.비트의 연산A101010B01106A & BAND 연산 : 둘다 1이면 1, 아니면 000102A | BOR 연산 : 둘다 0이면 0, 아니면 1111014A ^ BXOR 연산 : 둘이 다르면 1, 아니면 0110012~ANOT 연산 : 0이면 1, 1이면 001015B 왼쪽 시프트 : X비트 만큼 왼쪽으로 이동110012A >> 1오른쪽 시프트 : X비트 만큼 오른쪽으로 이동01015시프트 연산은 X비트만큼 2를 곱하고 나누는 것과 같다. (2의 X제곱을 곱하고 나누는 것과 동일)비트마스크.. [알고리즘] Kruskal 알고리즘이란 Kruskal 알고리즘이란?크루스칼 알고리즘은 그래프의 모든 정점을 최소 비용으로 연결하는 최적해를 구하는 것으로 부분 그래프 중에서 가중치의 합이 최소인 트리인 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는데 적합한 알고리즘이다.Spanning Tree란?신장 트리는 그래프 상의 모든 정점이 사이클 없이 연결된 최소 부분 그래프를 뜻한다.그래프에서 간선의 수가 가장 적다.가장 작은 간선의 수는 n개의 정점을 가지는 그래프에서 (n-1)개일 경우이다.이때, 그래프의 형태는 필연적으로 트리 형태가 된다.이중 간선의 가중치의 합이 최소인 경우를 최소 신장 트리(MST, Minimum Spanning Tree)라고 한다.MST의 활용도시들을 모두 연결하면서 도로의 길이가 최소가 되.. [알고리즘] DFS / BFS (깊이 탐색 / 너비 탐색) 그래프 탐색에서 각 정점을 지나가는 과정을 말하고 주로 사용되는 탐색 방법으로는 깊이 우선 탐색(Depth-First Search)과 너비 우선 탐색(Breadth-First Search) 2가지 알고리즘이 있다. 깊이 우선 탐색 (Depth-First Search) 일반적으로 스택과 재귀함수로 구현을 하고 재귀함수가 편하고 많이 사용되고 있다. 탐색 과정 하나의 점에서 한쪽 방향(연결 노드)으로 먼저 이동을 하고 갈 수 있는 끝 점까지 탐색을 한 뒤 다시 시작 지점으로 돌아와 다른 방향으로 끝 점까지 탐색을 시도한다. 진행 중 여러 방향으로 연결된 점이 있다면 시작 점과 같이 한쪽 방향씩 끝 점을 탐색하고 시작 점으로 돌아와 결과를 출력한다. 경로 탐색 깊이 탐색에서 경로 탐색에 경우에는 갈림길이 있을.. [알고리즘] Binary Search(이진 탐색 / 이분 탐색) Binary Search란? 이분 탐색 알고리즘은 정렬되어 있는 배열(혹은 특정 범위)에서 특정한 값을 찾아내는 알고리즘이다. 배열에 중간에 있는 값을 선택하여 찾는 값과 비교해서 값을 찾아낸다. 중간 값이 찾는 값보다 작으면 중간 값을 기준으로 오른쪽 범위에서 다시 탐색, 크다면 왼쪽 범위에서 다시 탐색을 한다. 탐색을 반복하면서 찾는 값이 일치할 때와 왼쪽 값이 오른쪽 값보다 커지면 종료가 된다. 이분 탐색 과정 해당 배열에서 찾는 값이 16일 경우, 인덱스 0과 5부터 시작을 하고 중간 값은 (0 + 5) / 2 = 인덱스 2가 된다. 중간 값 설정 일반적으로 mid = (left + right) / 2로 계산이 가능하지만, left + right가 자료형의 최댓값을 초과할 경우 오버플로가 발생해 .. 이전 1 다음
