본문 바로가기

알고리즘

 (7)
Topological Sorting Topological Sorting(위상정렬) 구조각 노드에 나타낸 숫자는 자신을 향하는 노드의 갯수를 표시 한 것 입니다. 이것은 indegree라고도 불리며 indegree의 값이 0인 노드부터 시작하여 자신과 연결된 노드들의 indegree의 값을 감소 시키면서 0이 되는 노드마다 queue에 넣고를 반복합니다.Topological Sorting 코드초기화cin >> n >> m;while (m--) { int x, y; cin >> x >> y; cur[x].push_back(y); cnt[y]++;}노드의 갯수와 간선의 갯수를 입력 받습니다. x -> y로 향하는 노드 이므로 x의 연결노드로 y를 추가하고 y의 indegree 값을 1 증가 시킵니다.시작 노드 추가queue..
BitMask bitMask 구조위 그림은 word 데이터 타입이라 가정했으며 16bit 이므로 16개의 0으로 표시 했습니다. bitMask 알고리즘은 이 0과 1로만 표시 할 수 있는 16개의 데이터를 다루는 것을 의미합니다.bitMask 연산자& = and 연산자| = or 연산자^ = xor 연산자~ = not 연산자bitMask 연산(bitMask & 0) 연산은 모든 비트를 0과 AND 연산해서 0으로 만드는 연산 입니다.~(bitMask) 연산은 0의 값을 1로 1의 값은 0으로 만드는 연산 입니다.(bitMask | (1 (bitMask & (1 (bitMask | ~(bitMask) 또는 (bitMask ^ ~(bitMask) 연산은 모든 비트의 값을 1로 만드는 연산 입니다.(bitMask >> 1)..
Binary Search Binary Search 구조Binary Search 이분탐색이라고 부르는 알고리즘의 초기 세팅은 위 그림과 같습니다. 반드시 배열의 값이 정렬이 된 상태여야 하며 Left는 시작점 Mid는 중간점 Right는 끝점을 가르킵니다. 예시로 위 배열에서 3이라는 값의 인덱스 값을 찾아보겠습니다. 1. arr[Mid] >= Data Mid의 오른쪽 인덱스 중에서는 원하는 값이 없다는 의미이므로 기존 Right를 Mid 위치로 옮기고 Mid를 (Left + Right) / 2로 설정합니다.2. arr[Mid] Mid의 왼쪽 인덱스 중에서는 원하는 값이 없다는 의미이므로 기존 Left를 Mid  + 1 위치로 옮기고 Mid를 (Left + Right) / 2로 설정합니다.Binary Search 코드int arr..
Dynamic Programming Dynamic Programming 구조 다이나믹 프로그램밍 이라고 부르는 dp 알고리즘은 배열을 이용하여 각 경우의 수마다 최적의 값을 구할때마다 저장하여 다시 계산하지 않고 값을 불러옴으로써 불필요한 연산을 줄이는 알고리즘 입니다. 피보나치 함수 문제로 예를 들면 f(0) = 0, f(1) = 1, f(2) = f(1) + f(0), f(3) = f(2) + f(1) 이며 식으로 표현하면 f(n) = f(n-1) + f(n-2) 입니다. f(4) = f(3) + f(2)을 풀어서 쓰면 결국 이미 계산했던 f 함수의 값을 또 계산하게 됩니다. 그래서 임의의 배열에 f(1 .... n)까지의 값을 한번 올때마다 값을 계산해서 저장합니다.DP 배열 반복문을 이용한 방법dp[0] = 0;dp[1] = 1;f..
BackTracking BackTracking 구조BackTracking(백트래킹) 알고리즘은 위 그림과 같이 모든 경우의 수를 탐색 할 수 있습니다. 기본적으로 나타낼 숫자의 범위 N과 수열의 길이 M을 입력 받으며 시간복잡도는 O(N*M) 입니다. void backTracking(int dep) { int i; if (dep >= m) { for (i = 0; i 1. 매개변수 dep는 수열의 현재 길이를 의미하며 입력받은 M보다 클 경우 현재까지 담은 숫자들을 출력하고 함수를 종료합니다.2. 반복문으로 i = 0부터 입력받은 N 값 만큼 순회합니다. 이미 방문했던 즉 배열에 담긴 숫자가 아닐때 visi 배열로 방문 체크하고 arrNum 배열에 i 값을 넣은 뒤 재귀함수로 backTracking 함수를 dep + 1 매개..
BFS, DFS BFS 구조BFS는 너비 우선 탐색 알고리즘으로 현재 위치에서 상하좌우로 이동합니다. 현재 그림에서는 맨 왼쪽, 맨 위의 위치에서 시작한다고 가정 하였으며 중복해서 방문하진 않으므로 화살표는 맨 오른쪽 맨 아래를 향하도록 표현하였습니다.BFS 코드방향 설정int xp[4] = { 0,1,0,-1 };int yp[4] = { 1,0,-1,0 };이동을 나타내는 배열입니다. 반복문을 통해서 상하좌우로 이동하며 값의 순서는 임의로 해도 됩니다. 위의 코드 같은 경우에는 우하좌상 으로 이동합니다.변수 초기화queue> q;q.push({ 0,0 });visi[0][0] = 1;q에는 현재 x, y의 위치를 담고 있습니다. 첫 시작은 0, 0이며 visi 배열은 방문 여부를 담으며 1이면 미방문 0이면 방문으로 ..
다익스트라 다익스트라 구조다익스트라의 구조를 그림으로 나타내면 위 사진과 같습니다. 각 원은 노드를 의미하며 각 노드에는 번호가 주어집니다. 노드끼리 이어진 화살표는 간선이라고 하는데 그림에선 단방향이며 양방향도 가능하고 노드에서 노드로 이동할때 지불하는 비용을 옆에 숫자로 표시했습니다. 이렇게 주어진 문제에서 예를들면 1번 노드에서 출발하여 6번노드로 갈때 간선을 지나면서 지불하는 비용을 최소로 했을때 나오는 값을 구하는 것이 다익스트라 알고리즘 입니다.초기화int matrix[SIZE][SIZE] = { {0, 2,5,1,inf,inf}, {inf,0,3,2,inf,inf}, {inf,3,0,inf,inf,5}, ..

티스토리툴바