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) : 스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선을 말한다. 위 ..

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