1. 문제 30022번: 행사 준비 (acmicpc.net) 30022번: 행사 준비 첫째 줄에 정수 $N(2\le N\le 100,000)$과 정수 $A,B(1\le A,B\leq N;A+B=N)$가 공백으로 구분되어 주어진다. 둘째 줄부터 $N$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 10^9)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 www.acmicpc.net 2. 풀이 첫번째 상점 가격을 오름차순 정렬하고, A개만큼 산 다음, 두번째 상점 가격을 오름차순 정렬해서, 이미 산 아이템일때, 첫번째 상점 가격보다 저렴한지 비교해서 저렴하면 두번째 상점 것으로 사보고.. 아니면 첫번째, 두번째 합쳐서 정렬해서 처음부터 순회할때, A개를 맞추면 나머지는 두번째 상점에서 다 ..
1. 문제 1725번: 히스토그램 (acmicpc.net) 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 2. 풀이 히스토그램이 주어질때, 찾을 수 있는 직사각형중 넓이가 가장 큰 직사각형을 찾는 문제 위와 같은 경우 다음과 같은 직사각형을 찾을 수 있을 것이다. 히스토그램이 높이 배열 A로 주어질 때, 어떤 구간 [i,j]까지 잡았을 경우, 만들 수 있는 직사각형은 높이가 가장 낮은 min(A)에 구간의 길이 j-i+1을 곱한 값이다. 따라서 가능한 모든 경우에 대해 min..
1. reduced row echelon form 한번 쯤 다시 읽어보자 elementary row operation과 reduced row echelon form을 설명하고 있다. elementary row operation은 1) 주어진 행렬의 i번째 행과 j번째 행을 뒤바꾸는 것 2) i번째 행에 0이 아닌 scalar를 곱하는 것 3) i번째 행에 scalar를 곱하고 j번째 행에 더해주는 것 이러한 연산을 하더라도 주어진 행렬의 rank는 변하지 않는다. https://deepdata.tistory.com/34 선형대수학 기본 용어 -상급자편 3- 1. gaussian elimination 1) 주어진 행렬의 $i$번째 행과 $j$번째 행을 뒤바꾼다. 2) 주어진 행렬의 $i$번째 행에 0이 아..
1. 부분문자열 검색 z-function의 대표적인 활용으로 특정한 문자열 t에 패턴 p가 몇번이나 존재하는지 찾아낼 수 있다. 이를 위해 새로운 문자열 s = p + # + t라는 문자열을 만들자. 여기서 #은 p와 t를 구분하기 위한 문자로, p,t 어디에도 등장하지 않는 문자여야한다. 이제 s에 대한 z-function을 계산하자. [0,len(t)-1]의 임의의 i에 대하여... z[i+len(p)+1]이 len(p)와 같다면, t의 i번째 위치에 p가 1번 등장한 것이다. 문자열 t 위에 있는 위치인 i+len(p)+1에 대하여.. z[i+len(p)+1]은 s와 일치하는 가장 큰 공통 접두사의 길이로, 이게 len(p)라는 것은 s의 접두사인 p의 길이와 일치하기 때문이다. 2. 연습문제 17..
1. z - function 길이 n인 문자열 s에 대하여 z[i]는 s의 i번째 접미사 s[i,i+1,...]과 s와의 최대 공통 접두사의 길이를 말한다 정의에 의하면 z[0]는 s와 s의 최대 공통 접두사의 길이로 s 그 자체의 길이 n이 될텐데 일반적으로 잘 정의하지 않는다. z[0] = 0으로 정의하기도 하고 문제에 따라 필요하다면 z[0] = n으로 정의하기도 한다. 예를 들어 'abacaba'에 대하여... z[1]은 'abacaba'와 'bacaba'의 최대 공통 접두사의 길이로... 공통 접두사가 존재하지 않으니 0 z[2]는 'abacaba'와 'acaba'의 최대 공통 접두사의 길이로 'a'가 있으니 z[2] = 1 z[3]은 'abacaba'와 'caba'의 최대 공통 접두사의 길이로..
1. 문제1 3216번: 다운로드 (acmicpc.net) 3216번: 다운로드 첫째 줄에, 다운로드 시작하고 몇 초 후에 노래를 듣기 시작하면, 끊김 없이 들을 수 있는지 출력한다. 그러한 시간이 여러개라면, 가장 빠른 것을 출력한다. www.acmicpc.net 2. 풀이 생각보다 어렵더라..? 다운로드 하면서 음악 재생시간을 누적해오고.. 어느 순간에 음악을 재생시키면.. 모든 다운로드 시간을 커버하면서 음악이 연속으로 흐를수 있게 할려면.. 다운로드가 언제 끝나는지 알아야하는데.. 이게 가능한가?? 리스트를 구성하면서 미리 더해서 남은 시간을 구해놓기도 하고.. 그리디의 기본인 정렬을 해서 짧은 시간부터 다운로드 해나가야하나? 생각은 했는데 정해진 순서대로 다운받아야하기 때문에.. 정렬은 할 수 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
