최장 증가 부분 수열이란?최장 증가 부분 수열(LIS, Longest Increasing Subsequence)은 어떤 수열이 주어졌을 때, 그 안에서 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 알고리즘이다. 여기서 말하는 "부분 수열"은 연속일 필요는 없지만 순서는 유지되어야 한다. 예를 들어, 수열이 [10 20 10 30 20 50] 이라면 최장 증가 부분 수열은 [10 20 30 50]이다. 최장 증가 부분 수열은 여러 개가 존재할 수 있다. 최장 증가 부분 수열은 다음과 같이 두 개의 방법으로 구현할 수 있다.1. 동적 계획법(DP)각 위치에서 끝나는 LIS 길이를 계산해 나가는 방식이다. 즉, DP[i]는 다음과 같이 정의된다.dp[i] : arr[i]를 마지막 값으로 가지는 LIS..
분류 전체보기
1. N진법 -> 10진법C++에서는 stoi() 라이브러리를 사용하면 N진법을 쉽게 10진법으로 바꿀 수 있다. stoi()의 기본 형태는 다음과 같다.int stoi(const string& str, size_t* idx = 0, int base = 10);str: 변환할 문자열idx: (선택) 변환이 끝난 위치를 저장할 포인터base: (선택) 진법. 기본값은 10진수여기서 base 값에 따라 진법 변환이 가능하다. 이때 base는 36까지만 가능하다!/* 2진수 변환 */string s = "1011";int n = stoi(s, nullptr, 2); // → 11/* 8진수 변환 */string s = "17";int n = stoi(s, nullptr, 8); // → 15/* 16진수 변환..
C++에서 짝수/홀수를 판단하는 방법은 크게 2가지가 있다.1. modulo 연산자 % 사용가장 흔히 쓰이는 방법이다. 2로 나누었을 때의 나머지 값을 가지고 판단한다.if (num % 2 == 0) { // 짝수} else { // 홀수}2. 비트 연산자 & 사용이진수에서 가장 끝자리(LSB)가 1이면 홀수, 0이면 짝수이다. 비트연산자 &를 사용해서 이진수의 가장 끝 자리를 검사한다.if (num & 1) { // 홀수} else { // 짝수}짝수만 판단하고자 할 때 아래와 같이 사용하면 될 것으로 착각할 수 있으나 아니다. 부정 연산자를 사용하는 것이 맞다. AND 연산에 대해 조금만 더 생각해보면 왜 이렇게 해야하는지 알 수 있다.// Xif (num & 0) { // 짝수}// Oif (!(n..
문제https://school.programmers.co.kr/learn/courses/30/lessons/12925 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 접근법각 언어마다 라이브러리 사용하면 된다. 코드C#include #include #include // 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요.int solution(const char* s) { return atoi(s);} 헤더에 선언되어 있는 atoi() 함수는 문자열을 정수로 변환해 반환한다.ASCII to INT 라는 뜻이다. C++에서도 사용할 수 있다.(하지만 굳이?)C..
문제https://www.acmicpc.net/problem/1931 접근법문제에서 출력하고자 하는 것이 애매하게 써있다.. 한 개의 회의실에서 진행할 수 있는 회의의 갯수를 출력하는 문제이다. 단순하게 생각하면 가장 빨리 끝나는 회의 순으로 진행하면 된다. 현재 회의가 회의실을 사용할 수 없는 경우만 체크해주면 된다. 풀이javaimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int N; static Meeting[] meetings; public static void main(String[] ..
문제https://www.acmicpc.net/problem/2839 접근법우리가 거스름돈을 줄 때 최소 개수로 주기 위해서는 큰 단위 순으로 계산을 하면 된다. 예를 들어 12,530원을 거슬러줘야 하는 상황일 때 큰 단위 순으로 10,000원 2개, 1,000원 2개, 100원 5개, 10원 3개 이런 식으로 계산한다는 뜻이다.이 문제도 비슷한 맥락으로 생각해보면 5kg으로 최대한 가져간 후, 남은 무게를 3kg으로 가져가면 된다. 이때 주의할 점은 5kg로 최대한 가져간 후 남은 무게가 3의 배수가 아닐 경우 3kg으로 남은 무게를 전부 배달할 수 없다는 것이다. 따라서 남은 무게가 최소한의 3의 배수가 될 때까지 5kg으로 배달하고 나머지는 3kg으로 배달해야 한다. 풀이javaimport jav..
cin과 >> 연산자C++에서는 표준 입력 스트림인 cin과 >> 연산자를 이용하여 사용자로부터 키를 입력받는다. cin과 >> 연산자는 헤더 파일에 선언되어 있으므로 프로그램 서두에는 다음 문이 필요하다.#include using namespace std; bool, char, short, int, long, float, double과 같이 기본 타입에 대해 입력이 가능하다. 아래와 같이 사용한다.int width;cin >> width;char c;cin >> c; 여러 개의 >> 연산자를 이용하여 여러 값을 입력 받을 수 있다. >> 연산자들은 왼쪽부터 오른쪽으로 순서대로 키보드로부터 입력받는다.cout >";cin >> width >> height;cout 너비와 높이를 입력하세요>> 23 36..
문제https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근법출전 순서는 사실 필요하지 않다. 그냥 B팀에서 A팀을 최대한 많이 이기면 된다.따라서 A와 B 배열을 오름차 순으로 정렬했다. A와 B 배열의 인덱스를 각각 만든 뒤 각각의 숫자를 비교한다.비교해서 나올 수 있는 경우는 2가지가 있다.1. A팀의 점수가 높거나 같은 경우2. B팀의 점수가 높은 경우 1번의 경우 현재 A팀의 점수는 A팀이 가지고 있는 숫자 중 가장 작은 숫자이다.따라서 해당..
