본문 바로가기

전체 글69

[알고리즘] - 투 포인터 (Two-Pointers) 1. 투 포인터 알고리즘 (Two - Pointers Algorithm) 투 포인터 알고리즘은 1차원 배열에서 활용할 수 있는 알고리즘이다. 배열에서 특정 원소를 가리키는 2개의 포인터를 사용하여 목표값을 찾는다. 이중 반복문을 이용하면 시간 복잡도가 O(n^2)이지만, 투 포인터 알고리즘을 이용하면 O(n)으로 해결이 가능하다. 코딩테스트에서 자주 나오는 편은 아니지만 종종 사용되므로 알아두고 넘어가자. 2. 투 포인터 알고리즘 활용하기 N개의 자연수가 저장되어 있는 수열이 있다고 했을 때, 이 수열에서 연속된 특정 구간의 합이 K이 되는 부분을 찾고자 한다. 예를 들어, 7개의 자연수가 들어있는 배열 arr에서 구간 합이 6인 경우의 수를 세어 보자. N = 7 / K = 6 초기 설정 기본 알고리즘.. 2024. 1. 19.
[C++] - 덱(deque) 사용법 정리 (STL) 덱(deque)이란? 덱(deque)이란, double-ended-queue의 줄임말로, 큐의 양쪽에서 원소를 삽입하거나 삭제할 수 있는 자료구조이다. 덱은 C++에서 많이 쓰이는 STL 자료구조 중 하나이다. 1. 헤더파일 #include using namespace std; deque를 사용하기 위해서는 헤더파일을 include 시켜주어야 한다. STL deque는 std namespace에 있기 때문에 cin이나 cout을 사용할 때와 같이 using namespace std;를 써주면 std::를 일일이 써주지 않아도 되어 편리하다. 2. deque 선언하기 deque 이름; #include #include using namespace std; int main(){ deque dq;//D라는 이름.. 2024. 1. 16.
[C++] - string → int 로 형변환하기 1. stoi() 메소드 이용하기 (string -> 모든 숫자형 가능) stoi() 메소드는 간단하게 string을 int로 바꿀 수 있는 함수이다. (string to int 에서 앞 문자를 따와서 stoi라고 부른다.) stoi(string변수명) 이라고 써주면 된다. stoi() 함수를 사용하려면 헤더파일을 include 시켜줘야 한다. -> C언어에서 사용하는 #include 가 아닌 #include 을 사용하므로 혼동하지 않도록 주의하자 int 뿐만 아니라 long, double, float 등도 변환이 가능하다. (값 손실이 있을 수 있으니 주의하자) int로 변환 stoi(); long으로 변환 stol(); double로 변환 stod(); float로 변환 stof(); #include.. 2024. 1. 12.
[C++] - int → string 으로 형변환하기 1. to_string() 메소드 이용하기 to_string() 메소드는 숫자형을 string으로 변환할 수 있는 간단한 방법이다. to_string(변수 이름)이라고 써주면 된다. int뿐만 아니라 long, double, float 등도 string형으로 형 변환이 가능하다. to_string()을 사용하기 위해서는 헤더파일을 include 시켜주어야 한다. -> C언어에서 사용하는 #include 가 아닌 #include 을 사용하므로 혼동하지 않도록 주의하자. #include #include using namespace std; int main() { int i_num = 2024; long l_num = 20242024; double d_num = 1234.12; float f_num = 123.. 2024. 1. 10.
[알고리즘] - 구간 합 (Prefix sum) 1. 구간 합(Prefix sum)이란? 수열에서 특정 구간의 합을 구할 때 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. 코딩 테스트에서 유용하게 활용 가능하니 꼭 알고 넘어가야 하는 알고리즘 중 하나이다. 부분 합과 혼동할 수 있어 정리해보자면, 일차원 배열 A가 있다고 하자. - 부분 합(Partial sum) : 처음부터 k번 인덱스까지의 합 ( = A[0] + A[1] + ... A[k] ) - 구간 합(Prefix sum) : i번부터 j번 인덱스까지의 합 ( = A[i] + A[i+1] ... + A[j-1] + A[j] ) 반복문으로 i번부터 j번 인덱스까지 더한다면? #include using namespace std; int main() { int i, j; cin.. 2024. 1. 9.
[C++] - vector를 2차원으로 사용하기 (STL) vector는 동적으로 메모리를 할당한 배열이다. 기존 1차원 vector를 값을 초기화하여 선언하는 방법은 다음과 같았다. vector 이름 (크기, 초기값) ; ex) vector v; 2차원 vector를 선언하려면, vector의 데이터 타입에 vector를 또 담는다고 생각하면 된다. vectorv; → 벡터의 자료형에 또 다른 벡터가 들어간다. 2차원 벡터는 2차원 배열과 같이 대괄호를 이용한 v[i][j]로 각 원소에 접근이 가능하다. 1. 행이 m개, 열이 n개인 2차원 벡터를 0으로 초기화하여 선언 vector v(m, vector(n,0)); 벡터 v는 m개의 원소를 가지고 있으며, 이 m개의 원소들은 각각 n개의 원소를 0으로 초기화한 벡터를 담고 있다. int m, n; cin >>.. 2024. 1. 8.

티스토리툴바