복습용 블로그

부분 합 : 배열의 각 위치에서 배열의 시작부터 현재 위치까지의 원소의 합을 구해 둔 배열 어떤 구간의 평균, 분산 등을 구하기 위해서는 간단히 생각하면 해당하는 위치에 있는 애들을 다 더 해서 처리해야한다. O(N)의 시간이 걸리지만, 이 방법을 여러 번 구현 한다면 전체 복잡도가 증가할 것이다. 이 때, 부분 합을 이용하면 해당 구간의 합을 구하는 데에 O(1)로 해결할 수 있으므로 전체 복잡도를 줄일 수 있다. arr[a]~arr[b] 까지 합 : psum[b] - psum[a-1] c++ : STL에 partial_sum( ) 활용해도 됨 partialSum : 전체 부분합 구하기, rangeSum : 배열의 a~b번째 합 구하기 vector partialSum( vector a){ vector ..

책 : 밑바닥부터 시작하는 딥러닝 2 chpater 2 text, 즉 글을 인식할 때 단어 자체로 분류를 할 수도 있지만, 앞 뒤 문맥 (context)을 파악하도록 말뭉치 (corpus)를 이용할 수 있다. 1. 말뭉치 전처리 (preprocessing) 전처리라는 것은 미리 어떤 것을 처리해 놓는 것이다. 여기서는 텍스트 데이터를 단어로 분할하는 과정을 의미한다. 그리고 단어에 id를 부여하여 해당 단어가 몇 번째 단어인지 구분한다. 예시 코드 def preprocess(text): text = text.lower() text = text.replace('.', ' .') words = text.split(' ') word_to_id = {} id_to_word = {} for word in word..

www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 주어진 배열 중 두 값을 골라 합이 0에 가장 가까운 두 수를 고르는 문제입니다. 답이 여러 개일 때는 아무거나 출력하면 됩니다. 음수 배열과 양수 배열을 따로 정렬한 뒤, binary search를 이용하면됩니다. 예를 들어, 양수 배열에서 a라는 수를 골라 음수 배열을 이분 탐색하며 -a 가 음수배열의 어느 위치에 놓이게 될지 탐색하면 됩니다. 그리하여 -a와 그 양 옆의 ..

백준 문제를 풀다보면 가끔 맞게 푼 거 같은데 시간초과가 날 때가 있다. cin, cout은 printf, scanf보다 입출력 속도가 느리다. 그럴 때는 main 함수 안에 다음을 추가하면 cin, cout의 입출력 속도를 증가시킬 수 있다. ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 백준 문제를 많이 풀다 보면 gcc 컴파일러를 이용하여 채점하기 때문에 컴파일 에러 날 때가 있다. 예를 들면, 비주얼 스튜디오의 경우 scanf를 scanf_s, gets를 gets_s 와 같이 받아야 컴파일 에러가 나지 않는다. 하지만 gcc 컴파일러의 경우 scanf와 같이 써야 컴파일 에러가 나지 않는다. 이럴 때 다음을 붙히면 된다. #define ..

www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 간단한 문제 하나만 풀고 집에 가려했는데 너무 간단한 문제였습니다. (사실 시간초과 한 번 나서 cin, cout 시간 줄이는 코드 사용) 그냥 우선순위 큐를 사용해 출력시키면 됩니다. 우선순위 큐는 큐에 값을 push할 때마다 오름차순, 혹은 내림차순으로 정렬합니다. (따로 기준 만들어서 하는 것도 가능) 기본형은 int를 기준으로 priority_queuepq = priority_queu..