분류 전체보기
-
알고리즘: 그래프 색칠하기(m-coloring)(Backtracking 문제)알고리즘 2020. 11. 12. 17:55
m-coloring 문제는 비방향그래프에서 서로 인접한 정점이 같은 색을 같지 않도록 m개의 다른 색으로 칠하는 방법을 찾는 문제다. 예를 들어, 이 그래프에서는 두 가지 색으로 문제를 푸는 것은 불가능하다. 세가지 색을 이용하면 6가지의 해답을 얻을 수 있다 그래프 색칠하기의 주요 응용분야는 지도 색칠하기이다. (이외에도 GSM에서 주파수 할당문제, Aircraft scheduling, final exam timetable등에 사용된다) 여기서 우리는 지도를 평면그래프(planar graph)로 나타낼 수 있는데 평면그래프란 두 개의 이음선이 서로 교차하지 않도록 그린 그래프를 말한다. 다음은 왼쪽의 지도를 평면그래프로 나타낸 것이다. (만약 v1과 v5를 연결하거나 v2와 v4를 연결한다면 평면 그래..
-
알고리즘: 부분집합의 합(sum of subset) 공부하기!(Backtracking 문제)알고리즘 2020. 11. 9. 23:46
부분집합의 합 구하기 문제에서는 양의 정수(무게) wi가 n개와 양의 정수 W가 있다. 합이 W가 되는 정수의 부분집합을 모두 찾는 것이 목표다. 전에 다루었던 knapsack문제와 유사하지만 부분집합의 합 구하기 문제에서는 조건을 만족하는 모든 집합을 찾는다는 점에서 다르다. 알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem) 탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 seungjuitmemo.tistory.com 예를 들어보자 n = 3, W =6 w1 = 2, w2 = 4, w3 = 5 이라 할때 각 노드들의..
-
알고리즘: 몬테칼로 알고리즘을 이용한 효율성 추적!알고리즘 2020. 11. 9. 23:17
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자) 되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 seungjuitmemo.tistory.com 이 전의 포스팅에서 되추적 알고리즘의 효율성에 대해서 문제 삼았고 이를 해결하지 못했다. 되추적 알고리즘이 어떤 특정 사례를 얼마나 효율적으로 처리하는지에 대한 추정치가 있다면 그 사례에 대해서 그 알고리즘을 사용하는게 타당한 지 결정할 수 있다. 몬테칼로 알고리즘은 확률 알고리즘이기 때문에 표본공간의 무작위 표본의 평균치를 가지고 표본공간에서 정의된 무작위..
-
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자)알고리즘 2020. 11. 9. 20:11
되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것이다. 즉, 어떤 여왕말끼리도 같은 행이나 열, 대각선상에 위치할 수 없다. 이 문제에서 순서는 여왕말을 둘 n개의 각각 다른 위치이고, 집합은 서양 장기판에서 말을 둘 수 있는 n제곱개의 위치들이 되고, 기준은 어떤 여왕말도 서로 잡아 먹히지 말아야 한다는 것이다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. DFS에 대해 간단히 설명하면 부모의 노드에서 내려갈 수 있는 자식노드까지 내려가고 그 이후의 자식 노드가 없다면 다시 부모노드로 돌아가면서..
-
머신러닝: 파이썬 Pytorch 사용하기!머신러닝 2020. 11. 9. 19:05
1. torch.rand(a, b) : 0 ~ 1사이의 값을 갖는 a x b 텐서생성 import torch x = torch.rand(5, 3) x tensor([[0.2107, 0.1415, 0.2014], [0.3747, 0.4420, 0.9662], [0.8733, 0.0158, 0.6805], [0.8282, 0.7829, 0.2063], [0.9674, 0.3998, 0.0489]]) tensor형태로 출력 2. tensor 값 지정해주기 x = torch.tensor([[0,1,1,2], [2,2,3,1]]) x tensor([[0, 1, 1, 2], [2, 2, 3, 1]]) 3. torch.zeros(a, b) : 0 값을 가진 a x b의 tensor 생성 torch.ones(a, b)..
-
알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)알고리즘 2020. 11. 6. 14:42
탐욕 알고리즘과 동적계획법은 최적화 문제를 푸는 두가지 방법이다. 둘 중 어떤 방법을 사용해도 문제를 풀 수 있다. 단일 출발점 최단경로 문제에서는 동적계획법은 모든 마디를 출발점으로 설정해서 구하기 때문에 과잉이라 볼 수 있다. 반면 탐욕 알고리즘은 항상 최적인 해를 만들어 주지 않는다. 그래서 보통 반례를 통해 최적의 해를 갖지 않는다는 것을 증명한다. 이 두 방법의 차이점을 확실하게 이해하기 위해서 0-1배낭 채우기와 배낭 빈틈없이 채우기라고 하는 두가지 문제를 살펴본다. 우선 결론적으로 말하면 배낭 빈틈없이 채우기 문제는 탐욕 알고리즘을 이용해서 풀 수 있지만 0-1배낭채우기를 풀 수 없으며 대신 동적계획법을 이용해서 완벽하게 풀 수 있다. < 0-1배낭채우기 문제(0-1 knapsack prob..
-
알고리즘: 스케줄짜기(Scheduling)공부하기! (시스템 내부시간 최소화, 마감시간이 있는 스케줄짜기)알고리즘 2020. 11. 6. 13:08
어떤 미용사에게 여러가지를 서비스를 받으려고 기다리는 손님이 있다고 하자. 서비스에 걸리는 시간은 모두 다르고 미용사는 얼마나 걸릴지 알고 있다. 손님들이 기다리는 시간을 최소가 되도록 손님을 서비스하는 것을 스케줄 짜기(sheduling)이라 하며 기다리고 머리하는데 걸리는 시간을 시스템 내부시간(time in the system)이라 한다. 그리고 마감시간이 정해진 경우(scheduling with deadlines)가 있는데 각 작업을 끝내는데 같은 시간이 걸리지만 각 작업과 관련된 보상을 최대로 얻기 위해서 마감시간을 고려해야하는 경우다. 이렇게 스케줄짜기는 시스템 내부시간(time in the system)과 마감시간이 있는 스케줄짜기(scheduling with deadlines)로 나뉘며 이..
-
네트워크: Network Layer 정리4 (AS routing, OSPF, SDN, ICMP)네트워크 2020. 11. 1. 18:40
네트워크: Network layer Routing 알고리즘 공부하기! 이번 포스팅은 Network layer control plane에서 routing이 어떻게 이루어지는 알아본다. 우선 이에 대해 알아보기전에 간단하게 네트워크 레이어의 구조에 대해 알아보자 네트워크 레이어는 data plane과 co seungjuitmemo.tistory.com 이전까지 다루었던 라우팅은 ideal한 모델이였으며 실제로 사용되는 routing은 scaling이 가능해야한다. 방대한 라우터들의 정보를 모두 가져와 라우팅 테이블을 계산하는 것은 불가능하기 때문에 이를 관리하는 자치적인 시스템이 필요하다. 그래서 전체 네트워크를 일련의 영역들로 나눠 각각 영역내 네트워크에서 라우팅을 컨트롤한다. 이렇게 일련의 영역들을 AS..