1. 문제 기둥이 4개가 있다. 네 개의 기둥에 원반들이 자유롭게 배치되어있을 때 (작은것이 위로 와야함) 모든 원반을 맨 오른쪽 기둥으로 옮겨 놓기 위해 필요한 최소한의 움직임 수를 계산하는 프로그램을 작성하여라 2. 최소거리 탐색 기둥이 4개, 원반이 최대 12개 이므로 기둥은 2비트로 표현가능하므로 각 원반마다 해당하는 기둥을 나타내는 상태공간은 최대 24비트만 있으면 표현가능하다. 상태공간에서 최단거리를 구하기위해 너비우선 탐색을 사용하면 시간이 초과 될 수 있다. 분기점은 최대 6개에 최소 3개이니 대략 5라고하자 그러면 최단거리가 d일때 O(5^d) 의 시간이 걸린다. 하지만 목표상태에서 역방향으로 움직이기 쉬우므로 양방향 탐색을 통해 시간을 줄일 수 있다. 그러면 O(5^(d/2))로 어느정..

1. 최단 경로 전략 너비 우선 탐색은 최단 경로 문제를 푸는 가장 직관적이고 유명한 방법이지만, 모든 최단 경로 문제를 너비 우선 탐색만으로 풀 수 있는 것은 아니다. 문제에 따라서는 너비 우선 탐색보다 다른 탐색 알고리즘이 더 강력한 경우가 있다. 2. 15- 퍼즐 7 8 4 1 2 3 5 6 9 10 11 12 13 14 15 => 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 X 4 격자에 끼워진 열다섯 개의 숫자 타일을 순서에 맞게 맞추는 퍼즐이다. 빈 칸에 상하좌우로 인접한 타일 하나를 빈 칸으로 밀어넣는 것을 한번의 움직임이라 할 때, 이 퍼즐을 해결하기 위해 필요한 최소 움직임을 구하는게 오늘의 목적이다. 이 문제를 풀기 위한 첫번째 단계는 게임판의 상태를 정점으로 표..

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억이 넘어가므로 이건 아닌거 같다. 인접리스트로 각 시간을 담는것도 조금 무리인것 같지만 행렬보다는 아니다. 시간을 겹치는 것끼리 같은 그룹으로 묶어서 압축을 시키면 어..