코딩못하는사람

https://www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1.접근 간단한 문제인거같아 DFS로 목적지에 도달했을때 stack을 정렬해서 값을 찾아냈는데 시간초과를 받았다.(정렬을 너무 많이 사용하게 되서) 'x원으로 해결이 안되는데 x-1원으로 가능할까?' 라는 질문글에 있던 힌트를 보고 문제를 해결할 수 있었다. 2.풀이 이분탐색을 해가면서 다익스트라를 돌릴때마다 가능한 값이면 정답에 저장하도록 했다. 문제에서..

https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 1.접근 인접한 격자로 가려면 경사의 절댓값을 지날 수 있어야 한다. 두가지 풀이가 생각났다. 1.이진탐색 경사의 범위가 1 ≤ Ar,c ≤ 1,000,000,000 이므로 가능한 경사의 값을 이진탐색으로 찾아서 값을 찾아가며 (1,1)->(n,n)으로 DFS를 돌려서 찾는 방법. 2.우선순위 큐 가장 경사가 적은값들만 찾아가면서 n,n이 나올때까지 탐색으로 찾아들어가는 방법 2.풀이 1.이진탐색 DFS로 그래프를 순회하며 (1,1)->(n,n)을 찾아간다. 지정한 경사보다 낮은 경사값들만 찾아 들어가다가 n,n에..

https://www.acmicpc.net/problem/19584 19584번: 난개발 이 사실은 대회에 참가하고 있는 여러분들만 알고 있는 사실이다. 방금 외계인들이 지구를 정복했고 서울시청과 서울시의회를 장악했다. 이들은 인간들이 통근과 통학으로 고통받게 하려고 대 www.acmicpc.net 1.접근 문제의 예시 그림을 보고 고민을 해보면 X축의 값은 필요없고 Y축으로 압축해서 누적합이 가장 큰 곳을 구하면 된다는 생각을 할 수 있다. 통행량을 계속 증가시켜주기 위해서 구간에 대해서 세그먼트 트리도 생각해보고 여러가지 생각해보았지만 y축으로 정렬하여 존재하는 모든 y축을 돌면서 시작지점에는 +,종료지점에는 -를 해주는 방식을 생각했다. 2.풀이 누적합을 어떻게 구할지 생각하는게 중요한 문제이다. ..

16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 1.접근 N은 십만 M도 십만이다. N^2으로 해결 불가능하고 NlogN으로 해결한다고 생각했다. 구간 합을 구하는 문제가 아닌 구간에 k를 더하는 문제이다. 생각을 조금 바꿔보자. 세그먼트 트리와 관련되서 생각해보니 1번 쿼리가 들어왔을 때 각 리프노드에 k를 더하지 않고 구간에 해당되는 노드에 k를 넣어놓고 출력할때 꺼내가면 된다고 생각했다. 2.풀이 우선 하던대로 완전 이진 트리를 리프노드만 전처리한다. 리프위에 노드들은 구간합같은 문제가..

세그먼트 트리란? 세그먼트 트리(Segment Tree) 또는 인덱스 트리(Index Tree)는 다음 두 연산을 어떻게 더 효율적으로 할까에 대한 고민에서 출발한다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i] = v 두번째 연산은 O(1)에 해결할 수 있겠지만 첫 번째 연산은 l-r의 길이만큼의 시간 O(NM)이 쿼리가 요청될 때 마다 소요될 것이다. (쿼리 m번 구간크기 n) 따라서 우리는 M과 N이 클때를 위한 자료구조인 세그먼트 트리를 알아야한다. 가장 기본적인 2,3,7,4,5,9,6,1의 구간합을 구하는 세그먼트 트리를 보자. 트리는 완전 이진 트리로 구성된다. 또한 트리의 ..

페르마 소정리 보안 수업에서 자주 봤던 정리이다. 여기서 한번더 나아가면 다음과 같은 식을 유도할 수 있다. 이말은 모듈러 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를 통해 들어갔을때 꼬리를 물어서 사이클이 생기지 않는다면 방문했던 곳들은 어디서 들어가도 사이클이 생기지 않을 것이다. 하지만 어느 부분에서라도 사이클이 생기는 곳이라면 들어갔을 때 자기..

KMP 알고리즘이란? 우리가 문서에서 컨트롤+F눌러서 문자를 검색하던 항상 쓰였던 알고리즘이다. 알고리즘을 어떻게 구현하였을지 단순히 생각해보면 당연히 모든 인덱스에서 한번씩 패턴을돌려보는 N이 텍스트의 길이,M이 패턴의 길이라고 할 때 O(N*M)을 생각할 것이다. 하지만 KMP알고리즘은 O(N+M)정도로 줄여준다 KMP알고리즘에는 두가지 함수가 필요하다 전처리 테이블 KMP알고리즘은 접두사와 접미사를 기반으로 만드는 전처리 테이블이 필요하다 접두사와 접미사 같을때의 최대길이를 저장해주는 것이다 코드로 구현하면 다음과 같다. KMP 함수구현 이렇게 전처리 테이블을 만들면 이제 테이블을 활용하여 겹치는 부분들을 활용하여 j는 순서대로 돌지만 i를 테이블값에 따라 빙빙 돌리면 된다 그림으로 보면 3번 인덱..