Storage Gonie

그래프를 탐색하는 방법 - 그래프를 탐색하는 방법에는 DFS와 BFS가 있으며, 두 방식 모두 목적은 모든 정점을 1번씩 방문하기 위한 것이다. - 따라서, 두 방법 모두 각각의 노드에 방문 했는지 안했는지를 체크하는 check 배열이 필요하다. - 순서를 출력해 낼 때, 현재 정점의 위치만을 출력하며, 이것은 두 방식 모두 동일하다. # DFS(깊이 우선 탐색) 구현 : 스택 or 재귀호출 스택을 직접 컨트롤하는 경우, 재귀호출을 사용하지 않고 구현할 수 있고, 재귀호출을 사용하는 경우 중첩된 호출에 의해 스택을 간접적으로 사용하게 됨. 의미 : '최대한 깊숙히 많이 가는 방법'으로 모든 정점을 1번씩 방문하는 것 탐색방법 : 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정..

그래프의 표현 정점 : {1, 2, 3, 4, 5, 6} 간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} - '정점'이 V개 일 때 보통 정점에 1~V 혹은 0~V-1로 번호를 매기기 때문에 개수만 저장해둬도 된다. - '간선'은 무엇과 무엇을 연결하는지에 대한 중요한 관계를 나타내므로 간선을 저장하는 것이 그래프를 저장하는 것이 된다. - 그래서 보통 문제에서 그래프에 관해 입력데이터를 줄 때는 정점의 개수, 간선의 개수, 간선의 관계를 아래와 같이 준다. (양방향 그래프인지 단방향 그래프인지는 문제의 본문을 읽어야지만 알 수 있다) 예시 1) 가중치가 없는 경우 6 8 // n : 정점의 개수, m : 간선의 개수 1 2 /..

그래프의 개념 # 그래프(Graph) - 자료구조의 일종 - 그래프는 정점집합과 간선집합으로 만들어진다. G = (V, E) - 정점(Node, Vertex)은 말그대로 점을 의미하고, 간선(Edge)은 정점간의 관계를 나타낸다. - 예시1) 지하철노선이나 도로를 그래프로 나타낼 수 있음. - 예시2) 페이스북같은 경우는 사람이 정점이고 두 사람이 친구사이면 둘을 간선으로 연결해줄 수 있음 그래프에서 사용되는 용어 # 경로(Path) - 출발지와 도착지가 있고 그 사이를 연결하는 정점과 간선이 있으면 이것을 경로라고 한다. - 예시) A->C->D->E->B A->B A->C->B # 사이클(Cycle) - 경로 중에서 시작점과 도착점이 같은 경우를 사이클이라고 한다. - 예시) 'A'->C->B->'A..

용도 : sort()가 전체를 다 정렬시킨다면 nth_element()는 부분적으로 정렬을 시키는 함수이다. 1. 헤더파일 #include 2. 함수형태 - 시작과 끝 Iterator를 맨 왼쪽과 왼 오른쪽에 넣어주고, 가운데에 index로 어디 자리가 확정될 때까지 정렬을 진행할지 넣어줌. void nth_element( RandomIt first, RandomIt nth, RandomIt last ); 3. 사용방법 #include #include #include using namespace std; int main() { int n; cin >> n; vector v(n); for (int i = 0; i > v[i]; // index : 0번째 자리가 확정날 때 까지만 ..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터5-5-정렬-문제풀이2-1 # C++ #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; vector v(n); for (int i = 0; i > v[i].first; v[i].second = i; } sort(v.begin(), v.end()); // NlogN의 시간복잡도 int ans = 0; for (int i = 0; i < n; i++){ if (ans < (v[i..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터5-5-정렬-문제풀이2-1 # C++ #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; vector v(n); for (int i = 0; i > v[i]; nth_element(v.begin(), v.begin() + (k-1), v.end()); cout

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터5-5-정렬-문제풀이2-1 # C++(선정렬 후 카운트) #include #include #include using namespace std; int main() { int n; cin >> n; // 숫자입력받기 vector v(n); for (int i = 0; i > v[i]; // 정렬하기 sort(v.begin(), v.end()); // 숫자를 카운트 하기 long long num; int num_count = 0; int temp_count = 0; for (int i = 0; i < n; i++){ temp_count += 1; if(i == n-1 || v[i] != v..

용도 : pair가 그냥 두 자료형을 묶는 거라면, map은 왼쪽의 값을 key값으로 사용하고, 오른쪽의 값은 value값으로 사용한다. key와 value를 가지는 노드를 생성해서 정렬된 '트리형태'로 저장해두어 탐색속도를 높인다.(key를 기준으로 정렬됨) python의 딕셔너리와 비슷하나 딕셔너리는 해시테이블로 구성되고, map은 트리로 구성된다.(레드 블랙 트리가 사용됨) index를 이용해 자료에 접근하는 배열과 달리 key값을 이용해 value에 접근할 수 있다.(key는 unique해야함) 중복된 key를 사용하여 입력하면 덮어씌어짐. 추가, 삽입, 삭제 시 자동정렬된다는 것도 알아두자. 아래 사용할 수 있는 함수를 보면 알겠지만 pair로 map을 구현했다는 것을 알 수 있다. 1. 헤더파..

정렬을 적용한 문제풀이 # 가장 빈도가 높은 수를 출력하는 문제 - https://www.acmicpc.net/problem/11652 - 방법1) 정렬한 뒤 하나씩 카운트하기, if (a[i-1] != a[i]) 으로 서로 다른 수의 경계값을 인식함. 시간복잡도 = 정렬(NlogN) + 카운트(N) 정렬된 수에서 경계값을 인식시켜줄 때는 a[i] a[i+1]을 비교하고, 제일 마지막 값은 경계값을 인식 못 하므로 꼭 따로 조건 추가해주기! - 방법2) C++ STL의 map을 이용하여 개수를 카운트 하고, 가장 등장빈도가 높으면서 작은 수 인 것을 출력. 시간복잡도 = 하나씩 카운트(N) + 비교(N이하) * count 메소드를 사용할 수 없는 이유는 시간복잡도가 N*N이 되어버리기 때문. # 오름차순..

정렬을 적용한 문제풀이 # N개의 수를 입력받아서 정렬하는 문제 - https://www.acmicpc.net/problem/2751 - 퀵 정렬 직접구현, 병합 정렬 직접구현, STL sort함수 사용 3가지 방법으로 풀이를 진행하였음 # (x, y) 좌표 정렬하기 문제 - https://www.acmicpc.net/problem/11650 - 아래의 여러가지 방법으로 정렬할 수 있음 1) pair, vector, sort 사용 2) struct, vector, sort ( , , 비교함수) 사용 3) struct, vector, sort( , , 람다함수) 4) struct, vector, sort, 연산자 오버로딩 # (x, y) 좌표 정렬하기2 문제 - https://www.acmicpc.net/..