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

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

1. 문제 끝말잇기 참가자 = 원으로 앉아있음 시계방향으로 단어를 말함 단어의 첫글자 = 이전사람이 말한 글자의 끝 단어의 종류가 정해짐 한단어 두번X 단어들을 전부 사용가능한지 판단하고 어떤 순서로 단어를 사용해야하는지를 계산하는 문제 2. 오일러 트레일 이 문제는 각 단어의 첫부분과 끝부분으로 만들어진 간선을 가지는 그래프를 만들고 오일러 트레일과 오일러 경로 구하는 문제인것 같다. 하지만 책에서 구현한 오일러 경로를 아직 이해하지 못하겠다. 간선이 아닌 정점을 벡터에 집어넣는것, 아직 생각을 더해야 겠다. 또한 그래프를 생성하고 홀수점이 2개일때 오일러 트레일을 찾을려면 홀수점 두개중에서 시작점과 끝점을 찾아야하는게 문제이다. (책의 풀이를 보고, 방향그래프인점을 생각하지 못한 것을 알게되었다.) ..

1. 문제 고대어 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있지만, 사전에 포함된 단어의 순서들이 영어와 서로 다르다. 사전선이 다른 순서인지 알파벳 순서가 영어와 서로 다른 것인지 알기 위해 사전에 포함된 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하여라 2. DFS, 위상정렬, DAG - 사이클이 없는 방향그래프일때 해당 순서를 계산할 수 있을 것이다. - DAG를 다루는 문제로 각 알파벳을 정점으로하고 다음문자와의 비교를 통해 알파벳끼리의 간선을 생성할 수 있을 것이다. 이 문제는 사이클만 찾는 코드를 구현하면 쉽게 풀 수 있다. 사이클이 생기는 경우는 한가지만 체크하면된다. 위상정렬을 구하기 위해 dfs를 실행하는 중 함수가 종료될..