Study

최장 증가 부분 수열이란?최장 증가 부분 수열(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..
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..
자세한 설명 및 사용법은 유튜브나 위키백과에서 확인하시면 됩니다 ♪멀티미터(Multi Meter)멀티미터는 디버깅을 하기 위해 가장 기본적이며 필수적인 측정 장비이다. 측정 정보가 LCD에 표시되는 디지털 멀티미터가 많이 사용되며 DMM이라고도 한다.멀티미터는 교류/직류 전압 측정, 교류/직류 전류 측정, 저항 측정, 쇼트 검사, 다이오드 방향 측정 등의 기능을 가진다. 오실로스코프(Oscilloscope)오실로스코프는 신호 전압을 측정하여 그래프의 형태로 볼 수 있는 장비로, 신호의 전압, 주파수, 노이즈 등을 확인할 수 있는 기본 장비 중 하나이다. 비쌀수록 대역폭이 넓어 빠른 신호까지 측정할 수 있다. 시스템의 최고 주파수 2배~2.5배 이상의 샘플링 속도를 가지는 오실로스코프를 선택해야 신호 간섭..
cout과 std::cout C++에서는 위와 같이 cout과 를 이용해 다양한 데이터를 화면에 출력한다. 문자열 뿐만아니라 bool, char, short, int, long, float, double 모두 출력할 수 있다. cout 객체cout은 스크린 장치와 연결된 C++ 표준 출력 스트림 객체(standard output stream object)이다. cout은 C++ 프로그램에서 출력한 데이터를 자신과 연결된 스크린에 대신 출력해준다. cout 앞에 붙여진 std::의 접두어는 cout의 name space가 std임을 표시한다. 본래 헤더 파일에 재정의(operator overloading)되어 cout과 함께 사용된다. 아래 예시와 같이 다양하게 화면에 출력할 수 있다.  std::cou..
typedef란? typedef를 사용하면 새로운 자료형을 정의할 수 있다. 즉, typedef 키워드를 사용해 C의 기본 자료형을 확장할 수 있다. 사용하는 방법은 다음과 같다. typedef unsigned char BYTE; unsigned char은 기존의 자료형, BYTE는 새로운 자료형이다. 기존의 자료형 unsigned char을 새로운 자료형 BYTE로 정의하는 것이다. unsigned char 형은 작은 정수를 저장하는 데에 사용할 수 있다. unsigned char만 보았을 때 정수를 저장하는 데 사용된다는 것을 알기 어렵기 때문에 BYTE라는 이름으로 새롭게 정의해준 셈이다. 이렇게 정의된 BYTE는 다음과 같이 사용할 수 있다. BYTE index; // unsigned char i..
공용체란? C에서 같은 메모리 영역을 여러 개의 변수들이 공유할 수 있게 하는 기능을 공용체라 한다. 같은 메모리 영역을 공유하게 되면 메모리를 절약할 수 있다. 공용체를 선언하고 사용하는 방법은 구조체와 비슷하며, 구조체와 똑같은 방법으로 태그를 붙여서 사용한다. 다만 공용체는 멤버들이 같은 공간을 공유하기 때문에 동시에 모든 멤버 변수들의 값을 저장할 수는 없으며, 어떤 순간에는 하나의 멤버만 존재할 수 있다. 구조체는 각 멤버가 독립된 공간을 할당 받고, 공용체는 가장 큰 멤버의 크기만큼 메모리가 할당된다. 공용체 선언 union example { char c; int i; } 여기서 union은 키워드이고 example은 공용체 태그 이름이며 변수 c와 i는 공용체의 멤버이다. 앞에서 말했듯이 공..