최장 증가 부분 수열이란?최장 증가 부분 수열(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[] ..
