1. 11050 11050번: 이항 계수 1 (acmicpc.net) 파스칼 삼각형을 사용해 문제를 해결 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std; int cache[11][12]; void initial() { for(int i = 0; i N>>K; initial(); coutK; initial(); cout 임의의 원소a와 임의의 연산?에 대해 a?x = a 이 되게하는 x ) (역원 => 임의의 원소 a와 임의의 연산 ?에 대해 a?x = 0 이 되게하는 x ) 어떤 수를 a로 나눈다 == 어떤 수를 a의 곱셈에 대한 역원과 곱한다 => 만약 a의 곱셈에 대한 역원이 존재하지 않으면..

1. 매칭 문제 N명을 둘씩 짝으로 묶으려고한다. 단 사이가 좋은 사람끼리만 짝을 지어준다고 할때 모든 학생에게 짝을 지어 줄 수 있는지, 불가능하다면 최대 몇 쌍이나 만들 수 있는지 계산하는 문제가 매칭 문제의 예시이다. 이런 문제들은 그래프로 간단하게 표현할 수 있다. 각 사람을 표현하는 정점을 만든 뒤, 사이 좋은 학생들을 간선으로 연결한다. 이 때 서로 짝을 이룬 학생들을 연결하는 간선들을 모아 보면, 이들은 끝점을 공유하지 않는 간선의 집합이 된다. 이런 간선의 집합을 이 그래프의 매칭(matching)이라고 한다. 이때 가장 큰 매칭을 찾아내는 문제를 최대 매칭 문제(maximum matching), 매칭 문제라고 부른다. 매칭 문제는 직관적인 정의를 가진 중요한 문제이다. 하지만 모든 그래프..

1. 네트워크 모델링 네트워크 유량 문제를 풀 때는 특히나 주어진 문제를 어떻게 그래프로 표현할 것인가가 중요하다. 예제를 통해 그래프를 어떻게 표현할 것인지를 알아보자 2. MILEAGE 마일리지로 여행하기: 자원 분배 신용카드 포인트와 항공사 마일리지 포인트, 이동 통신사 멤버십 포인트 등을 모아서 여행중 쓰려고 한다. 한 종류의 마일리지를 여러 개의 결제 항목에 나눠서 쓸 수 있으며, 한 가지 항목을 여러 개의 마일리지와 현금을 합쳐 결제 하는 것도 가능하다. 단 각 마일리지마다 사용할 수 있는 항목에 제한이 있기 때문에, 어느 마일리지로 무엇을 결제할지 신중해야한다. 결제해야하는 항목들의 가격과 각 마일리지에 쌓인 금액, 각 결제 항목마다 사용할 수 있는 마일리지의 목록이 주어질 때, 사용해야하는..

1. 그래프의 용량(Network Flow) 네트워크를 이용해 아주 큰 파일을 다운로드하는 중이라고 하자. 이렇게 존송받을 자료의 양이 많을 때 관심을 갖는 부분은 서버가 보낸 패킷이 내 컴퓨터에 몇 밀리초 만에 도착하느냐가 아니라 1초에 몇 MB의 자료를 전송받을 수 있느냐이다. 네트워크를 구성하는 케이블들에는 일정한 대역폭이 있기 때문에, 단위 시간당 일정량 이상의 자료를 전송할 수 없다. 따라서 패킷을 여러 경로로 나누어 보내 그 중 일부가 좀더 먼 길을 돌아오더라도 초당 10MB를 전송받는 것이 훨씬 이득이다. 이렇게 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 '흐름' 혹은 '유량'을 보낼 수 있는지를 계산하는 문제를 네트워크 유량 문제(Network Flow)라고한다. 네트워..

1. 최소 스패닝 트리(Minimum Spanning Tree) 외판원 문제 휴리스틱에서나 각종 그래프의 탐색 알고리즘, 최단 경로 알고리즘에서 경로를 찾는데에 사용했었다. 어떤 무향 그래프의 스패닝 트리(Spanning Tree)는 원래 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프이다. 이때 스패닝 트리에 포함된 간선들은 정점들을 트리 형태로 전부 연결해야한다. 트리 형태라는 것은 선택된 간선들이 사이클을 이루지 않는다는 것을 의미하며, 정점들이 꼭 부모-자식 관계로 연결될 필요는 없다는 것을 의미한다. 또한 그래프안에 여러 개의 스패닝 트리가 있다. 이런 스패닝 트리 중에서 가중치의 그래프의 스패닝 트리 중 가중치 합이 가장 작은 트리를 찾는 문제를 최소 스패닝 트리 문제(Minim..

1.플로이드의 모든 쌍 최단 거리 알고리즘 모든 정점 쌍에 대해 둘 사이의 최단 거리를 구해야 할 때도 있다. 이런 문제를 해결하는 가장 간단한 방법은 각 정점을 시작으로 다익스트라 알고리즘을 반복해서 실행하는 것이다. (음수가 있다면 벨만-포드 알고리즘 사용) 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 배열 dist[][]를 계산한다. (동적 계획법) 이 배열의 원소 dist[u][v]는 정점 u에서 v로 가는 최단 거리를 나타낸다. 2. 정점의 경유점들 두 정점 u, v를 잇는 어떤 경로가 있다고 하자 이 경로는 u, v를 지나가고 다른 정점 또한 지나갈 수 있다. u와 v를 직접 연결하는 간선이 없거나, 다른 정점을 경유해서 가는 편이 전체 경로가 더 짧아질 수 있기 때문이다..