1. 기본공백 포함 하는 문자열 입력 받을 때string str;getline(cin, str); 문자 -> char'a' -> 97'z' -> 122'A' -> 65'Z' -> 90 2. 특정 문자 고르기int idx = pattern.find('*'); st = pattern.substr(0, idx);en = pattern.substr(idx + 1); 3. 숫자만 있는 string인지 체크하기bool IsNumber(string query){ for (const char& ch : query) { if (!isdigit(ch)) return false; } return true;} 4. char 로 string 만들기https://www.acmicpc.net/problem/1213연속한..

이전 내용https://gbleem.tistory.com/87 1, 2 주차 알고리즘 정리1. STL 기본 구조STL이란C++ 내장 템플릿 기반 라이브러리컨테이너, iterator, 알고리즘으로 구성되어 있다.주요 컨테이너vector동적 배열로 구현된 컨테이너원소 삽입/삭제를 마지막 원소에 할때는 O(1gbleem.tistory.com 1. 정렬https://gbleem.tistory.com/98 버블, 선택, 삽입 정렬 + 퀵 정렬업데이트) 병합 정렬과 이분탐색 알고리즘 추가자세한 예시는 해당 글에 있고, 전반적인 정리는 아래 링크의 글을 참고하면 된다.https://gbleem.tistory.com/128 정렬 및 탐색 알고리즘 정리1. 정렬 알gbleem.tistory.com 버블 정렬앞에서부터 ..

참고자료https://blog.encrypted.gg/1024 [실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Spanning이나 신장 이 단어가 너무 낯설지blog.encrypted.gg 1. 최소 스패닝(신장) 트리신장 트리란주어진 방향성이 없는 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리를 말한다.부분 그래프란 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 그래프를 말한다.참고) 트리는 무방향이면서 사이클이 없는 연결 그래프그림 예시신장트리가 아닌 예시는 모든 정점을 포함하지 않거나, 사이클이 존재하기 때문..

1. Longest Common Substring두 문자열 사이에서 연속적으로 공통된 문자 중 가장 긴 문자열 찾기 (최장 공통 문자열) 과정2차원 배열을 통해서 하나씩 비교하면서두 문자가 다르면 dp[i][j] = 0같은 문자가 나온 순간 dp[i][j] = dp[i-1][j-1] + 1아래와 같은 표의 형태로 dp 배열을 구성할 수 있다 -ABC DEF-0000000G0000000B0010000C0002000D0000300F0000001E0000010 결론적으로 최장 공통 문자열의 길이는 3이 된다. 2. Longest Common Subsequence최장 공통 "부분수열" -> 중간에 끊기더라도 부분수열로서 연속된 문자열을 찾기 과정2차원 배열을 통해서 하나씩 비교하기두 문자가 다르면 dp[i -..

1. 특징배낭 문제 유형의 경우, 특정 스텝을 나아가는 도중에 "제약조건" 을 가지고 있어서 해당 조건을 체크해주는 작업이 필요하다. 예를 들어,물건들을 고르는 방법의 수를 구하는데 "최대 무게"가 정해져 있음동전을 모으는 방법의 수를 구하는데 "최대 금액" 이 정해져 있음인사를 하면서 얻는 기쁨을 구하는데 "최대 체력"이 정해져 있음  그렇기 때문에, 이중 for문을 사용해야 하는 경우가 많다.step을 밟아 나가는 for문제약조건을 지켜주는 for문 2. 예시https://www.acmicpc.net/problem/1535 이 문제는 가장 스탠다드한 형태의 문제이다.바깥 for문을 통해 step을 밟아 나가면서안쪽 for문을 통해서 제약조건을 지켜준다.더보기#include using namespace..

백트래킹 문제를 풀다가 중복제거, 오름차순 정렬 등을 좀 더 간단하게 하고 싶어서 정리한 내용입니다. 기존에 정리한 글https://gbleem.tistory.com/124 백트래킹1. 백트래킹쉽게 말해서 가능한 모든 경우의 수를 다 해보는 알고리즘이다.재귀 함수를 사용하여, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘! 문제를 보고, 주어진gbleem.tistory.com 1. 순열 구하기기본 형식의 백트래킹 코드를 돌리면 순열을 구할 수 있다. 1 ~ n까지의 숫자 중에서 m개를 뽑는 경우중복은 제거void Choose(int cur){ if (cur == m) { for (const int& a : ans) { cout  4 2를 input으로 넣었을 때 아래와 같은 ..

1. 다익스트라 알고리즘가중치가 있는 그래프의 최단경로를 구할 때 사용하는 알고리즘 다익스트라 알고리즘의 동작 방식은모든 노드의 최소 비용을 INF로 초기화한다.시작한 노드의 최소비용은 0, 직전 노드는 자기 자신으로 두고 시작이후 최소 비용이 가장 낮으면서 방문하지 않은 노드를 선택하여 최소 비용을 업데이트 한다.아래의 그림을 통해 어떤 방식으로 동작하는지 알 수 있다.최소 비용이 가장 낮은 A로 시작하여 모든 연결된 노드의 최소비용을 갱신 (A 방문)이후 최소비용이 가장 낮은 E노드를 시작으로 더 작은 최소비용이 되는 경로가 있다면 갱신 A->E->C가 기존의 A->C 보다 최소비용이 작으므로 갱신! (E 방문)이 방식을 모든 노드 방문할 때 까지 반복하기결과우리가 C까지의 경로를 알고 싶다면, C의..

1. 정렬 알고리즘1 - 1. 버블정렬배열에서 두개의 원소 선택하고 비교 후, 왼쪽 원소가 오른쪽 원소보다 큰 경우 swap 한다.시간 복잡도는 O(N^2), 공간 복잡도는 O(1)만약 아래 코드에서 swap이 발생하지 않는 경우 break하는 코드를 넣으면, 정렬된 경우 시간 복잡도를 O(N)으로 줄일 수 있다.더보기#include #include using namespace std;int main(){ vector vec = { 4,6,2,9,1 }; for (int i = 0; i vec[j + 1]) swap(vec[j], vec[j + 1]); } } for (const auto v : vec) cout  1 - 2. 선택 정렬배열의 한가지 값을 선택하고, 자신을 제외한 나머지 값들과..

1. 백트래킹쉽게 말해서 가능한 모든 경우의 수를 다 해보는 알고리즘이다.재귀 함수를 사용하여, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘! 문제를 보고, 주어진 전체 배열의 크기가 크지 않을 때 사용해 볼 법한 알고리즘이다.(너무 큰 경우 시간 초과가 날 것이다) 가장 기본적인 형태로, N개 중 M개를 뽑는 문제가 존재한다.https://www.acmicpc.net/problem/15649 코드 설명기본적으로 아래와 같은 형태로 재귀함수를 구성하게 된다.isused 라는 이미 사용한 것인지를 체크하는 배열을 통해 중복을 제거하게 된다.Choose라는 함수 안에서 경우의 수를 뽑는 과정이 이루어진다.cur은 현재 뽑은 갯수가 되고, cur이 m이 되는 순간 특정 처리를 해주면 된..

비트 마스킹이란 0과 1을 이용해서 연산하는 방식을 말한다.이 방식을 통해서 효율적인 연산이 가능할 때가 있다. 많이 안 써본 방식이기 때문에 관련 수업을 들은 후 내용을 정리하게 되었다.추가적으로 아래 글을 참고해서 정리해 보았다.https://blog.encrypted.gg/1093 [실전 알고리즘] 부록 C - 비트마스킹네 반갑습니다. 이번 부록 C에서는 비트마스킹을 다뤄보겠습니다.  이번 강의에서는 간단하게 비트 연산자들을 살펴보고 비트마스킹을 익힌 후에 문제를 같이 풀어볼 예정입니다. 이것도 다른blog.encrypted.gg  1. 비트 연산자0은 false 1은 true를 뜻한다.AND (둘다 참인 경우 참)0 & 0 = 00 & 1 = 01 & 1 = 1OR (둘중 하나만 참이어도 참)0 ..