코딩못하는사람

페르마 소정리 보안 수업에서 자주 봤던 정리이다. 여기서 한번더 나아가면 다음과 같은 식을 유도할 수 있다. 이말은 모듈러 p에 대해서 a의 역원이 a^p-2가 된다는 뜻이다. 이걸 알고 문제를 들어가야 풀 수 있다. www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 1.접근 n이 너무 크기때문에 이항계수 성질을 이용한 O(n^2)의 풀이는 불가능 할 것이라고 생각했다. 2.풀이 이 문제의 궁극적 목표인 이항계수의 식을 써보자면 N!/(N-K)!*(K)이다. 이것을 %P로 나눈값을 ..

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 1.접근 바이러스가 퍼진다는 것을 보면 DFS를 쓰면 되겠다는 생각이 든다. 조건으로 0인 부분에 벽을 3개 세워야 한다고 하니 itertools의 combination을 이용해서 0인 부분으로 3개의 모든 조합을 만들고 모든 상황을 DFS 해보고 제일 바이러스가 적게 퍼지는 상황을 구하면 되겠다. 2.풀이 우선 배열을 입력받고 행과열 양끝에 벽이 있는 것처럼 1로 입력을 감싸준다. 다음으로 배열을 돌면서 0인 부분과 2..

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 1.접근 문제에서 요구하는 것은 원래의 최단경로를 제외한 길에서의 최단경로이다 따라서 다익스트라를 활용하여 최단경로를 구한 후 그 경로들을 제거해준후 다익스트라를 다시 돌리면 될것이다. 2.풀이 문제풀이 방법을 생각보다 간단하고 구현에서 시간이 걸린다. 접근에서 말한 것 처럼 다익스트라로 최단경로를 구해준다. 근데 여기서 중요한 것은 최단경로가 여러개 있을 수 있다는 것이다. ..

www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1.접근 문제의 표를 보면 꼬리를 무는 사이클을 찾아야하는 것을 알 수 있다. 따라서 DFS나 while문을 통해 돌면서 사이클이 생기는 곳을 체크해주면 되겠다. 2.풀이 문제의 사이클에 대해서 생각해보자. 어느 부분에서라도 DFS를 통해 들어갔을때 꼬리를 물어서 사이클이 생기지 않는다면 방문했던 곳들은 어디서 들어가도 사이클이 생기지 않을 것이다. 하지만 어느 부분에서라도 사이클이 생기는 곳이라면 들어갔을 때 자기..

Chess Tournament www.acmicpc.net/problem/13344 1.접근 문제를 보고 동점인 경우에는 같은 차수의 집합이 생길거라고 생각해서 disjoint set을 바로 생각했다. 일관성이 있는지 없는지를 판단하려면 위상정렬을 시켜서 순서대로 진행했을때 위상정렬이 정상적으로 수행되면 일관성이 있는 것이고 차수가 0인게 존재하지않아서 큐에서 뽑을게없으면 사이클이 생겨 일관성이 없다고 판단했다. 2.풀이 중요한 것은 집합을 모두 만들고 > 연산을 수행하는 것이다. 처음에는 =,> 연산을 들어올때마다 했는데 바뀌는 것이 매번 많아서 코드가 복잡했다. 그래서 '='이 나왔을 때 유니온을 합치는 작업부터 모두 수행하고 그다음 '>' 작업을 했다. 모든 병합이 완료되면 경로 압축을 통해 부모노..

18809 Gaaaaaaaaaarden www.acmicpc.net/problem/18809 1.접근 초록색과 빨간색 조합을 써야하므로 itertools 모듈에 combination을 써주고 경우의 수가 너무 많으므로 백트래킹을 활용한 BFS로 최대 꽃개수를 구해보자 2.풀이 combination을 사용해서 해볼 경우의수를 모두 BFS함수에 넣는다. BFS를 초록색을 돌리는 큐와 빨강색을 돌리는 두개의 큐로 나눠서 풀었다. 우선 방문한곳을 체크하는 visited함수를 -1로 초기화하고 몇번째날에 들어가는지(cnt)로 갱신한다. 우선 초록색을 돌리면 큐에서 꺼낸좌표가 flower이면 continue 좌표가 n,m범위에 있고 바다가 아니며 visited가 -1이면 언제 방문했는지 visited에 cnt를 넣..

1.접근 N의 범위를 모르고 (1 ≤ N ≤ 100,000) 모든간선을 만드는 N^2으로 풀었다가 시간초과를 받았다. 그래서 NlogN으로 풀려고 정렬을 생각했다. 2.풀이 정점들이 주어진다고 해서 이전문제들 같이 모든 간선을 만들 수 없다. 근데 만들필요도 없다. 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이라고 했으므로 x,y,z축들의 값을 따로 따로 보면된다. 이 부분이 생각하기 힘들었는데 x,y,z축 좌표들을 각각 정렬해놓고 바로 앞,뒤 값들의 차이로 간선들을 만들고 힙에 넣으면 된다. 이렇게 되면 힙에서 빠져 나오는 값들은 비용의 최소값부터 나올 것이다. x,y,z축을 정렬해줄때 좌표의 값도 같이 넣어주어야 쉽다. 이후 유니온 파인드와 크루스칼 알고리즘을..

https://www.acmicpc.net/problem/13913 1.접근 bfs역추적을 방문했던곳인지 확인하는 check배열을 만들어 바로 전 값을 저장하도록 해서 추적하게 했다. 2.풀이 출발지점에서 도착지점까지 가는 +1,-1,*2의 3가지 뿌리로 bfs를 만들어준다. 여기서 방문했던 곳인지 확인하는 check 배열을 -1로 초기화 시킨다.bfs를 통하여 방문할때마다 cnt대신에 자신의 바로 전 위치를 집어 넣어주면 -1도 아니게 되고 어떤 경로로 현재 지점에 와있는지 알 수 있게된다. 따라서 큐에서 도착지점 값이 나올 때 cnt값을 반환하고 도착지점에서부터 시작지점까지 check배열을 순서대로 거꾸로 따라가보면 어느 경로로 왔는지 나온다.(마지막 while 문) 3.코드 4.배운점 처음에 che..

두개의 문제는 전위,중위,후위순회을 활용해서 문제를 풀어봐야한다. 2263 트리의 순회 https://www.acmicpc.net/problem/2263 1.접근 생각하기 어려웠지만 직접 트리를 그려서 중위탐색과 후위 탐색을 해보면 전위 탐색을 어떤식으로 해야할지 보였다. 2.풀이 중위순회과 후위순회을 그려보면 규칙을 찾을 수 있다. 후위 탐색된 리스트에서 맨 마지막 값은 중위 순회의 루트노드일 것이다.따라서 중위 탐색에서 그 루트노드의 인덱스를 구해서 왼쪽 오른쪽 나눠서 재귀적인 문제로 만들어 풀면 된다. 여기서 후위순회에서 구한 루트값의 인덱스를 구할 때 일일이 탐색하게 되면 시간초과가 날게 분명하므로 for i in range(n): num[in_order[i]-1]=i 루트값이 어디있는지 인덱스를..

1.접근 모든 정점을 기준으로 DFS를 들어가보는 생각밖에 나지 않아서 풀어봤지만 시간초과가 났다(2≤V≤100,000) 도저히 생각나지 않았는데 트리의 지름을 구하는 쉬운 방법이 있었다. 2.풀이 트리의 지름을 구하려면 임의의 점을 잡고 그 점으로부터 최대거리를 가진 곳의 인덱스에서 다시 최대 거리를 구하면 그것이 지름이 된다.(처음 임의의 점에서 최대거리를 구할 때 트리의 지름과 겹치는 부분이 생길 수 밖에 없기 때문에 이라고 한다.) 따라서 DFS를 두번 써주면 된다 (임의의 점,임의의 점에서의 최대 거리 인덱스) 트리의 지름을 구하는 공식은 이곳에 자세히 있다.https://blog.myungwoo.kr/112 3.코드 4.배운점 DFS나 재귀를 쓸때는 습관적으로 sys.setrecursion을 ..