16139번: 인간-컴퓨터 상호작용

2559번: 수열사용 언어: C++문제 요약문자열 S와 질의 Q개가 주어진다. 각 질의는 알파벳 α와 정수 l, r로 구성되어 있으며,문자열 S[l]부터 S[r]까지 구간 내에서 α가 몇 번 등장했는지 구해야 한다.문자열 길이 ≤ 200,000질의 개수 ≤ 200,000⇒ 단순 순회는 시간 초과 발생.풀이구간 빈도 문제에서는 누적합을 사용하면 효율적으로 문제를 풀 수 있다.알파벳은 총 26개이므로 각 알파벳마다 문자열의 접두 구간에서 누적 등장 횟수를 저장.prefix[c][i] = 문자열 S의 0번째부터 i-1번째까지의 알파벳 c가 등장한 횟수그리고 전처리 방식for (int i = 0; i 정답 코드#include #include #include using namespace std;int main()..

11659번 : 구간 합 구하기 4

11659번: 구간 합 구하기 4사용 언어: C++문제 요약수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.풀이전형적인 누적합 (prefix sum)문제다. 매번 값을 구하면 너무 느리니까 미리 관련된 값을 다 구하고 필요할 때 꺼내쓰는 방식이다. 위 방식은 구간과 구간 사이에 합을 구하는 것이므로 모든 자리까지의 누적합을 구하고 해당 자리가 필요할때 구간이 a, b이면 (a#i..

C++ STL (뇌를 자극하는) - 4장. 함수 템플릿 (Section 2 ~ 3)

※ 제가 개인적으로 공부하는 것이라 요약하거나 책에서 빠진 내용이 있을 수 있습니다 ※Section 2. 함수 템플릿클래스 템플릿은 클래스를 만들어내는 틀(메타 코드)다. 함수 템플릿과 별반 다를게 없다. 단지 함수에서 클래스 바뀐 것 뿐. 클래스 템플릿을 설명하기 위한 정수형 배열을 추상화한 클래스 Array를 최소의 기능만을 갖게 만들어봅니다.정수형 Array 클래스#include using namespace std;class Array{ int* buf; int size; //원소의 개수 int capacity; //저장 가능한 메모리 크기 public: explicit Array(int cap = 100) : buf(0), size(0), capacity(cap)..

2565번: 전깃줄

2565번: 전깃줄사용 언어: C++문제 요약두 개의 전봇대 A, B 사이에 여러 개의 전깃줄이 연결되어 있음.전깃줄은 A의 위치 번호와 B의 위치 번호 쌍으로 주어짐.어떤 두 전깃줄이 교차한다면 위험하므로, 전깃줄 일부를 제거하여 서로 교차하지 않도록 만들고자 함.남길 수 있는 최대 전깃줄 개수를 찾고,제거해야 할 전깃줄의 최소 개수를 출력하라.입력첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.출력첫째 줄에 남아있는 모든 전깃줄이 서로 ..

C++ STL (뇌를 자극하는) - 4장. 함수 템플릿 (Section 1)

※ 제가 개인적으로 공부하는 것이라 요약하거나 책에서 빠진 내용이 있을 수 있습니다 ※Section 1. 함수 템플릿템플릿은 두 종류가 있다1. 함수 템플릿 : 여러 함수를 만들어내는 함수의 틀2. 클래스 템플릿 : 여러 클래스를 만들어내는 클래스의 틀예제templatevoid Print(T a, T b){ cout (0.123, 1.123); // 명시적 호출}템플릿 함수를 사용하면 컴파일러는 클라이언트(호출 측)의 함수 호출 인자 타입을 보고 템플릿 함수의 매개변수 타입을 결정하여 실제 함수인 템플릿 인스턴스 함수를 만들어낸다. (참고로 컴파일 타임에 이루어진다)또한, 컴파일이 완료되면 함수 템플릿 (원본 함수 템플릿 자체)는 존재하지 않고 인스턴스화된 실제 함수들만 존재하게 된다. 템플릿도 함..

11053번: 가장 긴 증가하는 부분 수열

11053번: 가장 긴 증가하는 부분 수열사용 언어: C++ 문제 요약수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이dp[i]는 해당 위치에서 가장 긴 증가하는 부분 수열의 길이.dp[i]의 값은 이전 위치 j들 (0그래서 점화식은dp[i] = max(dp[j] +..

2156번: 포도주 시식

2156번: 포도주 시식사용 언어: C++ 문제 요약효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 ..

10844번: 쉬운 계단 수

10844번: 쉬운 계단 수사용 언어: C++문제 요약45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.풀이이전 자리 숫자와 현재 자리 숫자의 관계를 고려하면 되므로 마지막 숫자만 알면 다음 숫자 선택이 가능. 그래서 점화식 기반 Bottom-Up DP로 채워나가는 식으로 풀어야하고, dp[i][j]는 길이 i, 마지막 숫자 j일 때 계단 수의 개수.점화식- dp[i][j] = dp[i - 1][..