1. 문제 타일이 주어지면 '.'에 함정을 설치한다고 한다. 이때 함정은 상하좌우 4칸에 다른 함정이 없어야된다. 이때 최대 함정을 설치할 수 있는 갯수와 함정의 위치를 포함한 타일을 출력해야한다. 2. 암시적 그래프 타일을 상하좌우를 간선으로 가지는 암시적인 그래프로 표현할 수 있다. 이를 이용해 이분 그래프의 매칭 문제의 dfs코드를 조금 변형하면 최대한 많은 타일에 함정을 매칭할 수 있다. 이분 그래프로 생각하면 다음과 같다. a그룹 = '#' 이 아닌 타일 전체 b그룹 = 상하좌우중간 으로 묶여진 타일들의 집합. 중간을 기준으로 구별할 수 있다. 3. 이분 그래프의 매칭 dfs 모든 타일을 조사하면서 '.' 인 타일에대해 dfs를 실행한다. (a그룹을 하나씩 조사) 주위에 함정이 없어 함정을 설치..

1. 문제 게임판과 장애물의 위치가 주어진다. 이 게임판 위에서 비숍을 서로 죽일수 없도록 최대한 몇개 배열할 수 있는지 계산하는 문제이다. 2. 이분 매칭 비숍은 대각선으로만 이동할 수 있다. 오른쪽으로 가는 대각선과 왼쪽으로 가는 대각선 두개로 비숍의 위치를 나타낼 수 있다. 그러므로 해당 대각선에 비숍이 두개 있을 경우 서로 죽일 수 있다. 이를 이용하여 오른쪽 대각선과 왼쪽대각선을 a그룹 b그룹으로 나누어 이분 할 수 있으며 최대한 많이 비숍을 배열해야하므로 이는 이분 최대 매칭 문제가 된다. 따라서 그래프만 적절히 표현하면 문제는 쉽게 해결된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ..

1. 문제 이 문제는 주어진 그래프에서 '사이클'을 찾는 문제이다. 특히 1번 정점을 지나는 '사이클' 만 찾으면된다는 것이다. 다른 곳에서 생기는 사이클은 전부 무시해도 된다는 것이다. 하지만 이 문제는 한번 꼬아서 최대와 최소 즉 양의 무한대와 음의 무한대일 경우도 찾아야하는 것이다. 2. 벨만-포드 알고리즘 벨만-포드 알고리즘은 relax를 |V|번하게되면 그래프에 음수사이클의 여부를 알 수 있다. 이 알고리즘을 조금 변형하여 V번째 완화에서 만약 성공하면 시작점부터 완화가 발생한 지점까지 갈 수 있는지 확인하고 완화가 발생한 지점에서 목적지까지 갈 수 있는지 또 확인해야한다. 이는 0번에서 1번까지 도달하는것을 제외한 모든 사이클을 무시하게 해준다. 코드는 다음과 같다 이 코드는 최대 최소를 한번..

1. 문제 이 문제는 여러 소방서에서 불난집까지 가는 최단 거리들을 찾는 것이다. 이것은 불난집을 여러번 다익스트라를 돌려서 가장짧은 소방서를 찾으면 해결되지만 이 문제의 의도는 아니다. (소방서를 기준으로 돌리거나 플로이드의 모든 쌍 최단 경로 알고리즘(O(V^3))을 이용하여 풀 수 도 있지만 느리다) 2. 모든 소방서를 하나로 이 문제는 모든 소방서를 한 소방서에 합치면 다익스트라 한번에 해결 할 수 있다. 다음은 모든 입력이 주어지고나서 첫번째 소방서에다가 하나로 합친 그래프를 만들고 문제를 해결하는 코드이다. 책에서는 인덱스 0 인 임의의 정점을 만들어서 이를 가중치가 0 으로 소방서를 전부 이었다. 이렇게하면 모든 소방서에서 동시에 다익스트라를 수행하는것과 같다. 1 2 3 4 5 6 7 8 ..

1. 다익스트라 문제 이 문제는 간단한 다익스트라 문제이다. 이 문제의 핵심은 정수의 거리가 아닌 실수인 노이즈의 증폭도라는 것이다. 따라서 간선을 지나가면서 가중치를 더하는게 아니라 곱을 하는 것이다. 2. 책의 풀이 책에서는 곱을 로그의 합으로 변환해서 문제를 해결하였다. 로그의 합의 최소를 구하고 exp()만 해주면 답을 구할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #inc..

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