1. 문제 C개의 선물들을 n명의 아이들에게 나누어주는데 m명의 아이들에게는 1+ g 개 n-m 명의 아이들에게는 g개 씩 나누어준다고한다. 이때 C는 D 목록에 있는 수로만 이루어져있는 자연수여야한다. 2. C의 성질 이 문제는 D목록을 정점으로하는 무향 그래프를 생성하여 0에서부터(impossible) bfs로 차근차근 하나씩 자리수를 늘려가며 맞아 떨어지는지 검사하는 문제인것같다 문제에서 주어지는 변수들로 수학식을 정리해보면 다음과 같다 C = m(1+g) + (n-m)g C = ng + m C%n = m%n (C>=n) C%n = m ,,, m>n 즉 목록 D로 구성되어있는 C를 n으로 나눈 나머지는 m을 n으로 나눈 나머지와 같아야한다 이때 m과 n은 고정점이므로 이점을 이용하면 목록이 주어졌을..

1. 문제 중복이 없는 정수 수열에서 이 수열의 임의의 구간을 선택 해당 구간을 뒤집을 수 있다. => 뒤집기 연산으로 전체 수열을 정렬하고 싶다. 정렬을 위해 뒤집기 연산을 최소 몇번해야 하는지를 계산하여라 2. 그래프 수열의 길이는 1~8 이다. 따라서 이는 최대 8!의 상태가 있는것이다. 각각의 상태를 그래프로 표현하고, 각각 뒤집기 한번한 연산 결과와 이어주는 간선으로 표현하면 그래프가 만들어질 것이다 이 그래프를 bfs로 정렬된 상태까지의 거리를 구하면 답이 될것이다 하지만 내가 생각한 그래프를 만드는 방법은 수열하나에 번호 하나를 매기고 하나하나 뒤집으며 간선을 이어주는 것 이었다. 전체 수열 40320 개 중 하나를 뒤집으면 28개의 뒤집어진 수열이 생기고 28개를 뒤집는데 2중 반복문에 거..

1. 그래프의 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색은 깊이 우선 탐색과 함께 그래프 탐색 방식의 두 축을 이룬다. 다익스트라의 최단 거리 알고리즘이나 프림의 최소 스패닝 트리 알고리즘에서 BFS가 쓰인다. 너비 우선 탐색은 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다. 너비 우선 탐색은 각 정점을 방문할 때마다 모든 인접 정점들을 검사한다. 이 중 처음 보는 정점을 방문할 때마다 모든 인접 정점들을 검사한다. 이중 처음 보는 정점을 발견하면 이 정점을 방문 예정이라고 기록해둔다. 인접한 정점을 모두 검사하고 나면, 지금까지 기록한 목록에서 다음 정점을 꺼내서 방문하게 된다. 따라서 BFS의 방문 순서는 정점의 목록에서 어떤 정점을 먼저 꺼내는지..

1. 회의실 배정 문제 이 문제는 n개의 팀이 회의를 할 수 있는 두 시간 범위가 주어지고 두 시간중 한 타임을 선택하여 모든 팀이 회의를 할 수 있게하는 문제이다. 2. 그래프 만들기? 그래프의 정점들은 각 시간의 첫부분과 끝부분이어야 할 것 같다. 그러면 간선은 회의를 하는 시간을 표현해야할 꺼 같다. 각 회의 구간은 겹칠수 있다. A -> B A->a->b->B C -> D 위와 같은 다양한 경우가 존재할 수 있다. 어떻게 그래프를 표현해야할까 인접행렬로 표현할 시 시간의 범위가 43200이므로 메모리가 432000*432000로 1억이 넘어가므로 이건 아닌거 같다. 인접리스트로 각 시간을 담는것도 조금 무리인것 같지만 행렬보다는 아니다. 시간을 겹치는 것끼리 같은 그룹으로 묶어서 압축을 시키면 어..

1. 문제 모든 방을 감시할 수 있게 감시 카메라를 최소한으로 설치해야한다. 이때 방은 모두 트리 간선을 이루고 있다고 한다. (연결되지 않은 방 또한 있다.) 어떤 방에 카메라를 설치했다고 하자. 그러면 그 방 주위의 방들을 감시할 수 있다. 1칸밖에 감시를 못하므로 이것은 '리프' 에서부터 차근 차근 카메라를 설치해야한다. '리프' 에서부터 탐색하는하는 것은 dfs를 이용하면 쉽게 구현할 수 있다. 2. dfs 일단 루트에서부터 dfs를 실행하게 되면 제일먼저 종료되는 dfs는 '리프'이다. '리프' 이전의 방에서는 무조건 카메라가 설치되어야 '리프'를 감시 할 수 있다. 그러므로 '리프' 이전의 방에 카메라를 설치한다. 이 문제에서 '리프'는 연결점이 타고내려온 것을 제외하고는 아무것도 없는 정점을..

1. 간선의 분류: 유향 dfs를 수행하면 그래프의 간선을 한 번씩은 조사하게 된다. 간선의 종류는 두가지가 있다. - 처음 발견된 정점으로 연결된 간선 - 무시되는 간선 이들에 대한 정보를 수집하면 그래프 구조에 대해 많은 것을 알 수 있다. 일단 연결된 간선들만을 모아보면 트리 형태를 띠게 된다. (위 그림은 0번 정점을 루트로 하는 트리 형태) 이 트리의 이름을 그래프의 깊이 우선 탐색의 스패닝 트리 혹은 DFS 스패닝 트리 라고 부른다. DFS스패닝 트리를 생성하고 나면 모든 간선을 4가지로 분류할 수 있다. - 트리 간선(tree edge) : 스패닝 트리에 포함된 간선 - 순방향 간선(forward edge) : 스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선을 말한다. 위 ..