코딩못하는사람

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.풀이 이분탐색을 해가면서 다익스트라를 돌릴때마다 가능한 값이면 정답에 저장하도록 했다. 문제에서..

파이썬에서의 문자열 문제해결방법 in을 사용해서 포함여부 판단하기 find()를 사용해서 index까지 구하기 KMP알고리즘을 사용해서 index 또는 포함여부 구하기 1,2번은 최악의 경우 O(N*M)이지만 KMP알고리즘은 O(N+M)에 해결 가능하다. 리스트 형태로 저장하였다면 ''.join(list_name)으로 공백없는 문자열을 만들 수 있다. 1. in을 사용하기 문자열에 in을 사용해서 찾는 문자열이 포함되는지 판단 가능하다. 만약 포함된다면 True를 아니면 False값을 반환해준다. ex) string='python' print('pyt' in string) =>True print('ppp' in string) ->False 2.find() 함수 사용하기 문자열간에 포함여부와 인덱스를 반환..

1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 1.접근 알파벳 소문자는 26개이다. 따라서 int(32bit) 크기의 2진수 배열에서 알파벳을 각각 하나씩 마스킹에 할당해서 문제를 풀 수 있다. 2.풀이 남극의 모든 단어는 a,n,t,i,c 으로 이루어져 있으므로 k가 5보다 작다면 어떠한 단어도 읽을 수 없다. 5개의 단어는 모두 배운다고 가정한고 한줄씩 입력받으면서 a,n,t,i,c을 지우고 가운데 알파벳들만 입력받는다. 만약 a,n,t,i,c로 지운 리스트의 길이가 0이라면 무조건 읽을 수 있는..

Inversion counting이란? 배열 A는 1,2,3,...n 의 수가 무작위 순서로 들어 있다고 했을 때 그 순서 대비 크기가 역전되어 있는 수들의 쌍을 구하는 문제이다 예를들어 4 2 7 1 5 6 3순서의 배열은(4–2), (4–1), (4–3), (2–1), (7–1), (7–5), (7–6), (7–3), (5–3), (6–3)인 10개의 역순쌍이 있는 것이다. Inversion counting 해결방법 직관적으로 해결하자면 O(n^2)을 이용해서 모든 수에서 모든수를 돌아보면 되지만 O(NlogN)으로 해결하는 merge sort를 이용한 방법과 segment tree를 이용한 방법이 있다. 1.merge sort 병합정렬을 이용한 방법은 병합정렬을 사용해서 반으로 나눈 뒤 합치는 과정..

http://acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 같은 점이 여러 번 주어질 수도 있 www.acmicpc.net 1.접근 n이 100000이므로 O(N^2)으로는 풀 수 없다. 내가 아는 방법이 없는 것 같아서 구글링으로 라인 스위핑 알고리즘과 분할정복을 통한 closest pair 방법이 있었는데 라인 스위핑이 아직 어려워서 분할정복으로 풀어보았다. 라인스위핑:www.acmicpc.net/blog/view/25 closet pair:casterian.net/archives/92 2..

www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 1.접근 N이 2,000,000이므로 NlogN을 생각하게된다. 세그먼트 트리를 이용할텐데 X의 크기도 2000000까지인 것을 보아 리프노드를 200만개로 만들고 1번 유형 쿼리로 숫자와 인덱스가 같은 트리를 만들어야겠다. 2.풀이 우선 트리를 만드는대 어느 숫자가 들어올지 모르기 때문에 리프노드 200만개 모두 만들어야 한다. 그 후 인덱스와 들어오는 숫자가 같은 트리이므로 ..

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의 구간합을 구하는 세그먼트 트리를 보자. 트리는 완전 이진 트리로 구성된다. 또한 트리의 ..

피보나치 수를 구하는 3가지 방법. 피보나치 수는 알다시피 다음과 같이 정의되는 수열이다. 이렇게 이전 2개의 합이 다음 오는 수가 되는 수열이다. 조금 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...이 된다. 가장 기본적인 문제를 풀어보자 10826 피보나치 수 4 www.acmicpc.net/problem/10826 1.접근 n은 10,000보다 작거나 같은 자연수 또는 0이다. 쉬운 피보나치 수이다. 2.풀이 우리는 DP느낌의 방법으로 쉽게 O(N)시간에 답을 구할 수 있다. 3.코드 4.배운점 사실 dp로 구현했었는데 메모제이션 할 필요없이 for 문을 돌리면 가장 간단했다. 2749 피보나치 수 3 www.acmicpc.net/problem/27..

페르마 소정리 보안 수업에서 자주 봤던 정리이다. 여기서 한번더 나아가면 다음과 같은 식을 유도할 수 있다. 이말은 모듈러 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로 나눈값을 ..