C++

이 게시글은 계속 업데이트되고 있습니다. [최신 업데이트 12/18 ] ⭐️C++의 value category C++의 표현식(expression)들은 type과 value category라는 두 개의 독립적인 속성(property)을 통해 특징 지을 수 있다. C++ 11이 나오기전, C++ 03까지는 l-value와 r-value를 각각 assign operator(operator =)의 왼쪽에 올 수 있는 값, 오른쪽에 올 수 있는 값으로 정의 내렸었다. 이후 C++ 표준 개정안이 변경되면서 C++ 11부터는 value category에 x-value, gl-value, pr-value가 추가되었다. value category는 두 가지의 기준 identity과 move를 통해 밑의 표와 같이 구분..

⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net ⭐️ Idea flow 이 문제는 GCD와 LCM의 특징을 이용하여 풀 수 있는 문제였다. 문제에서 어떤 두 자연수 A와 B의 최소 공배수(LCM)과 최대 공약수(GCD)가 주어지는데, 이 때, 두 자연수를 구해야 하는 문제였다. 처음에 떠올린 식은 A * B = GCD(A, B) * LCM(A, B) 였다. 문제에서 lcm과 gcd가 주어지기 때문에 두 수를 ..

⭐️ Topology Sort (위상 정렬)이란? - "순서가 정해져 있는 작업"을 차례로 수행해야 할 때, 그 순서를 정렬하기 위해 사용 - 자료구조 queue를 이용해서 구현 가능 - 위상 정렬이 가능한 조건 : DAG DAG란? Directed Acyclic Graph의 약자로써, 사이클이 존재하지 않는(Acyclic) 방향이 있는(Directed) 그래프(Graph)이다. 만일 사이클이 있는 그래프라면 위상 정렬을 할 때 시작점을 설정할 수 없으므로 위상 정렬을 수행할 수 없다. - Time complexity : O(V+E) V: 정점의 개수, E: 간선의 개수 ⭐️ 변수 설명 1. int v 정점의 개수를 뜻한다. 이 정보를 통해서 다른 변수의 메모리 공간을 미리 할당할 수 있다. 2. vec..

⭐️ BFS : Breadth-First Search (너비 우선 탐색) 이란? 출처 : 위키백과 BFS - 그래프 전체를 탐색하는 하나의 방법으로써, 현재 정점으로부터 가까운 정점들을 먼저 방문한다. - DFS와 다르게 깊게 파고 드는 것이 아니라, 인접한 정점부터 넓게 탐색한다. - queue(큐)를 이용해서 구현할 수 있다. ⭐️ BFS의 특징 - 정점 방문 시, 반드시 방문 여부(isVisited)를 검사하고, 방문 시 isVisited를 true로 표시한다. - 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E) // 인접 행렬로 구현 시 O(V^2) - queue에 다음에 탐색할 정점들을 push하고 pop하는 과정을 거치기 때문에 DFS에 비해서 메모리가 더 필..

⭐️ DFS : Depth-First Search (깊이 우선 탐색) 이란? [출처 : https://en.wikipedia.org/wiki/Depth-first_search] - 그래프 전체를 탐색하는 하나의 방법으로써, 하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동한다. - 넓게 탐색하는 것이 아닌, 깊게 탐색하는 방법이다. - stack 또는 recursive(재귀 함수)로 구현할 수 있다. ⭐️ DFS의 특징 - 정점 방문 시, 반드시 방문 여부(isVisited)를 검사하고, 방문 시 isVisited를 true로 표시한다. 정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있다. - 시간 복잡도(Time complexity) : 인접 리스트로 구현 시 O(V+E..

⭐️ 난이도 Gold 4 ⭐️ 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net ⭐️ Idea flow 이분 그래프 기본 문제였다. 각 테스트 케이스마다 주어진 그래프에 대해서, 해당 그래프의 이분 그래프 여부를 구하는 문제이다. 따라서 이분 그래프에 대해서 알고 있으면 풀 수 있는 문제였다. 이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 그룹으로 나누고, 서로 다른 그룹의 정점을 간선으로 연결한 그래프를 말한다. ..