자료구조 및 알고리즘 C++

출력)출력)getline(cin, s) : 공백(띄어쓰기)를 포함하여 한번에 입력을 받아들인다.

ios_base::sync_with_stdio(false);cin.tie(NULL);입출력 속도를 향상시킨다.freopen("input.txt", "rt", stdin);빌드되는 디렉토리에 input.txt라는 파일에서 입력을 읽어오는 코드이다.

cout << fixed;cout.precision(2);소수점 개수를 2개로 고정한다는 것이다. 3째자리에서 반올림하여 반영한다.ex) 출력

size() : string의 크기를 나타낸다.ai : string은 char의 연속으로 char를 원소로 갖는다고 생각할 수 있다.

num_arr1 : 가장 기본적인 형태의 vector 선언이다.num_arr2 : vector의 크기를 정함과 동시에 선언한다.num_arr3 : vector의 크기를 정하면서, 해당 vector의 값을 무엇으로 초기화할지도 정한다.ex) n=5일때의 출력push_ba

push : 스택에 원소를 삽입하는 역할을 한다.empty : 스택이 비어있는지 확인하는 역할을 한다.top : 스택의 최상단에 있는, 즉 마지막에 삽입된 원소를 가리킨다.pop : 스택의 최상단에 있는, 즉 마지막에 삽입된 원소를 삭제하는 역할을 한다.

queue는 원소를 back으로 삽입하고, front로 pop한다.push : 큐에 원소를 삽입하는 역할을 한다. back으로 삽입한다. empty : 큐가 비어있는지 확인하는 역할을 한다.front : 큐의 제일 앞의 원소를 가리킨다.back : 큐의 제일 뒤의 원소

deque는 원소를 front, back으로 삽입, 삭제할 수 있다.push_back() : 뒤로 삽입push_front() : 앞으로 삽입pop_back() : 뒤 삭제pop_front() : 앞 삭제ex) n = 6

\-1을 입력으로 주면, 해당 프로그램을 종료한다.0을 입력으로 주면, 해당 프로그램 진행중에 나온 최대값을 출력하고, 해당 값을 우선순위 큐에서 삭제한다.0을 입력으로 주었을때, 우선순위 큐가 비어있다면 -1을 출력한다.priority_queue : 우선순위 큐를 선

C++ 에서는 최대힙이 디폴트 값이다. 따라서 추가적인ㅇ 조치를 하지 않아도 내림차순으로 출력이 된다.priority_queue<int, vector, greater> pQ; : 최소 힙을 사용하게 하여, 오름차순으로 출력되게 한다.

https://www.acmicpc.net/problem/11286최소 힙을 간단하게 적용하면 되는 문제가 아니다. 절대값과 실제값 두개의 비교기준을 생각하여야 하기때문에, 연산자 오버로딩을 통해 경우의 수를 고려하여 작성한다.bool operator<

set S : set 자료구조 선언S.insert(Vi) : set 자료구조에 원소 삽입, 원소의 중복을 허용하지 않음S.size() : set의 크기auto it : iterator를 대신하여 auto 사용S.find(wnat_to_find) : set 자료구조에 해

https://www.acmicpc.net/problem/5397연결리스트의 삽입/삭제 시간 복잡도는 O(1)으로, 배열의 삽잆/삭제 시간 복잡오니 O(N)보다 훨씬 짧다. list<char> link_l : 링크드리스트 선언link_l.begin() :

strcut : 내가 사용하고자하는 자료형을 임의로 정의하여 사용할 수 있는 "구조체"라는 것이다.bool operator<(const Data &b) const 이하 부분 : 해당 구조체를 이용하여 sort를 할때 무엇을 기준으로 할지 오버로딩해주는 부분이다.

a0-48 : 문자형 숫자와, 숫자형 숫자의 차이는 48이다.

for(int i=0; ai!='\\0'; i++) : 문자열을 입력받을때, 문자열의 끝에는 '\\0'이 저장되기때문에, 이를 이요해서 문자열의 처음부터끝까지 출력할 수 있다.cout << a : 이와 같이 그냥 출력할 수도 있다.ex)kim

cin : 띄어쓰기 즉 공백을 기준으로 입력을 받는다. 또한 '\\n'를 만나면 이를 저장하지 않고 버퍼에 남기고 그 전까지 있던 입력을 받는다.getline : 3번째 파라미터로 주어지는 것을 기준으로 입력을 분할하여 받는다. default값은 '\\n'이다. cin

i번째 순서에 와야하는 원소의 위치를 idx로 저장하고, 현재 i번째에 있는 숫자와 자리를 바꾼다.시간복잡도는 n^2

오름차순 내림차순 기준에 따라, 각 인접한 원소와 자리를 연속해서 바꾼다.시간복잡도는 n^2ex)513 5 11 7 23 15

오름 차순 내림 차순 정렬의 기준에 따라, 0번째 원소가 아닌 1번째 원소부터 자신보다 아래 수의 위치하는 원소들의 자리와 비교하여, 기준에 따라 각 원소들의 자리를 하나씩 뒤로 미루고 해당 원소를 삽입한다.시간 복잡도 : n^2ex)513 5 11 7 23 15

divide함수 : 배열의 크기가 1이 될때까지, 연속적으로 분할한 뒤, 오름차순 내림차순의 기준에 의하여 원래의 배열크기까지 병합하는 역할을 한다.ex)513 5 11 7 23

Vmid == want_to_find : 찾고자 하는 원소를 찾았을 때이다.Vmid > want_to_find : 찾고자 하는 원소가 더 작을 때, 따라서 rt = mid -1;Vmid < want_to_find : 찾고자 하는 원소가 더 클 때, 따라서 lt =

root가 1이고, 1~7까지의 원소들로 이루어진 완전 이진트리라고 생각해보자.\---1\--2 34 5 6 7전위, 중위, 후위 순회는 각 재귀적으로 불리는 DFS의 함수부분에서, 호출하는 함수를 바꿔주면 된다.

이진트리라고 생각하고, 각 Level에서의 원소가 사용될때(ch\[] = 1)와 사용되지 않을때(ch\[] = 0)를 나누어서 생각한다.

첫째 줄에는, 정점의 수 N과, 간선의 수 M이 주어진다.Va.push_back : vector의 배열을 선언하여, 해당 vertext에서 갈 수 있는 vertext를 삽입하였다.chnext_vertex = 1 : 해당 vertex를 방문하다고 가정 하였을 때chnex

if(Level == r) : Level은 0부터 시작하므로, r에 도달할때를 종료조건으로 한다.chi = 1 : arr의 i번째 숫자를 resLevel에 사용한다고 가정할 때chi = 0 : arr의 i번째 숫자를 resLevel에 사용하지 않는다고 가정할 때ex)

if(Level == r) : 0부터 시작하였으므로, r에서 종료for(int i= start; i<n; i++) : start하는 부분을 달리하여, 순열이 중복되지 않도록 한다.ex) 4 6

BFS는 일반적으로 자료구조 queue를 사용하여 구현한다.grapha.push_back(b) : 이진트리를 방향 그래프라고 생각ch\[graphx] : 해당 위치를 방문하였는지 확인ex)1 21 32 42 53 63 7

1. 한 정점에서 출발하여, 방향 그래프내에서 각 정점까지 최단거리를 구하는 코드 출발하는 정점은 1번 정점으로 한다. #include #include using namespace std; int n, m; int ch[101], dis[101]; vector gra

disx : 위치x에 있을때, 몇번 움직였는지 기록ex)5 14

숫자 n개와, 숫자쌍의 갯수 m이 주어진다.숫자를 통해 연결이 되면 한 사슬이라고 칭한다.같은 사슬이면 YES, 아니라면 NO를 출력한다.메모이제이션을 통해, 다음 연산시 연산의 절차를 줄일 수 있다.Find : 같은 사슬인지를 확인Union : 사슬을 형성ex)9 7

정점의 수 v, 모든 간선의 수 e,e개의 간선에 대해서는 출발 정점, 도착 정점, 간선의 비용이 주어진다.간선의 비용에 따라 간선을 오름차순으로 정렬한뒤, 각 간선들을 연결해 나간다.struct Data : 출발 정점, 도착 정점, 간선의 비용을 저장하기위한 구조체b

정점의 수 v, 모든 간선의 수 e,e개의 간선에 대해서는 출발 정점, 도착 정점, 간선의 비용이 주어진다.임의의 시작정점을 정한뒤, 해당 정점에서 갈 수 있는 간선을, 우선순위 큐를 이용하여 val이 최소값인 것만을 res결과 값에 더한다.bool operator&l

임의의 정점은 1번 정점으로 한다.정점의 수 n, 간선의 수 m이 주어진다.각 간선은, 출발 정점, 도착 정점, 비용을 입력으로 받는다.임의의 정점에서 시작한다고 가정한다.해당 정점에서 최소의 간선비용을 찾아, 해당 도착 정점으로 이동할때 값이 더 작다면 간다.vect

정점의 수 n, 간선의 수 m이 주어진다.마지막 입력으로는, 알고자하는 비용의 구간인 출발 정점과 도착정점이 주어진다.음의 사이클이 존재하여 답이 나올 수 없는 경우에는 -1출력.disti : 출발정점에서 i번째 정점까지의 비용을 기록한다.disti = 21470000

dp1 : 선의 길이가 1일때, 자르는 경우의 수 dp2 : 선의 길이가 2일때, 자르는 경우의 수dpi : 선의 길이가 i일때, 자르는 경우의 수문제의 크기를 아주 작은 단위로 축소한 뒤, 그 작은 단위에서의 답을 구하고, 살짝 더 큰 단위의 문제를 푸는 형식이다.이

메모이제이션을 통해, 다음번에 동일한 계산을 반복하지 않도록한다.dp1 : 선의 길이가 1일때, 자르는 경우의 수dp2 : 선의 길이가 2일때, 자르는 경우의 수dpn : 선의 길이가 n일때, 자르는 경우의 수문제의 크기를 아주 작은 단위로 축소한 뒤, 그 작은 단위에

else if (n == r || r == 0) return 1 : 종료 조건return dpn = DFS(n - 1, r) + DFS(n - 1, r - 1) : 메모이제이션을 활용ex)5 3

dpi : i번째 원소를, 증가수열 부분의 마지막이라고 할때의, 최대 부분 증가수열의 크기i번째의 원소보다 작은 j의 범위에서, i번째 원소보다 작은 j번째 원소 중에, 가장 큰 부분 증가수열 크기에 +1을 한다.if(arrj < arri) : i번째 원소보다 작

두개의 문자열이 주어질때, 첫 번째 문자열에서 두 번째 문자열에 해당하는 아나그램의 총 개수를 출력하는 코드 ex) eabcbacade abc

사람의 숫자는 n으로 주어진다.각 사람이 좋아하는 숫자는, m개로 각 사람마다 숫자 m이 주어진다.연속된 m개의 숫자가 이어서 주어진다.숫자 k가 주어진다.1부터 k까지의 숫자 배열중 d개를 선택했을때, 사람들이 좋아하는 숫자들을 모두 포함하는 경우에 결과값에 +1을

배를 타고 강을 건너야 한다.배에는 단 두명의 사람만이 탈수 있다.n명의 사람들이 주어지고, 각 사람들은 노를 젓는 속도가 다르다.배의 속도는 노를 늦게 젓는 사람의 속도에 맞춰진다.모든 사람이 강을 건널때 시간이 얼마나 걸리는지 계산하라.ti + t1 + ti-1 +

isupper(ai) : 대문자인지 확인islower(ai) : 소문자인지 확인isdigit(ai) : 숫자인지를 확인toupper(c1) : char형 자료를 대문자로 바꾼다.tolower is : char형 자료를 소문자로 바꾼다.transform(lower_str

a.find('a') : 문자의 위치를 찾는다.a.find("not_exists") : 문자열의 위치를 찾는다. 찾지 못한다면 string::npos 값을 return한다.count(a.begin(), a.end(), 'a') : 문자열 a에서, 알파벳 a가 몇개인지

a.back() : 문자열의 맨뒤 문자를 가리킨다.a.front() : 문자열의 처음 문자를 가리킨다. a.push_back('a') : 문자열의 맨뒤에 문자를 삽입한다.a.pop_back() : 문자열의 맨뒤 문자를 삭제한다.a = a + "September 21."

map<string, int> : 맵 자료구조를 선언하는 부분이다.map<string, int>::iterator it : 맵 자료구조의 원솓르을 가리키는 역할을 하는 iterator라고 하는 것이다. 이것을 이용해서 각 원소에 접근한다.it->first,