Do you believe in you?

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ++relationDepth 아니고 relationDepth+1 이 맞음!!!!!!!!!!! #include #include using namespace std; const int MAX_SIZE = 2001; vector graph[MAX_SIZE]; bool visited[MAX_SIZE]; int answer; void DFS(int person, int relationDepth); int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.ti..

[문제] 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net [풀이] 벡터를 활용한 인접리스트와 DFS로 품~! *동적할당부분 기억하깅... vector *graph = new vector[vertexNum + 1]; //인접리스트 동적할당 bool *visited = new bool[vertexNum + 1]; [풀이 코드] #include #include using namespace std; void dfs(int vertex, vector grap..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int calculationNum, bit = 0, num; // bit 초기화 필수 string calculationString; cin >> calculationNum; for (int i = 0; i < calculationNum..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net #include #include #include using namespace std; void SearchCity(int startCity, int currentCity, int costSum, int count, vector visitedCityArr, vector visitedCityVector); int leastCost = INT_MAX; int..

[문제] 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 는 골드바흐의 추측이 맞는지 틀렸는지 확인하는 문제. 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다. [..

[문제] 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 주어진 수 N개 중에서 소수가 몇 개인지 찾는 문제. [풀이] 우선 소수란, 1보다 크며 1과 자기 자신 이외엔 나누어지지 않는 수를 말한다. 그리고 소수 찾는 법은 크게 2가지로 나뉜다. 1. 2부터 루트N까지 소수인지 아닌지를 판별하는 법. 시간복잡도 O(루트N). 2. 에라토스테네스의 체 방법을 이용하여 2부터 자신의 배수를 다 지우는 방법. 시간 복잡도 O(N(log(logN))). 1번 방법에서 루트N까지만 확인하는 이유는 그 이상은 루트N 이하의 배수이기 때문이다. 예를 들어 N으로 24가 주어지고 24의 약수..

문제 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 풀이 유클리드 호제법을 이용하여 주어진 숫자에 모든 경우의 수에 따라 최대공약수를 구하는 문제. 고민했던 부분은 3가지였다. 1. 최대공약수를 구할 두 수를 선택(조합을 이용해서)하는 방법 2. 선택한 두 수를 저장 및 최대공약수 연산 함수에 보내는 방법 3. 항상 큰수를 작은 수로 나누게 숫자를 배치하는 방법 무식하게 일단 구현해보자!는 맘으로 덤볐더니 반복문과 벡터를 좀 많이 썼다... (상세 설명은 주석 참조...) 인터넷을 찾..

코딩을 할 때, 메모리를 효율적으로 사용하기 위해 동적할당을 사용하곤 합니다. 원하는 만큼 메모리를 할당하고 사용이 끝나면 메모리를 해제해서 메모리를 관리하는 것이지요. 참고로 정적변수들은 stack 메모리에 생성되고 동적변수들은 heap 메모리에 생성됩니다. stack영역은 컴파일 동안 메모리가 결정되고 CPU에 의해 관리되어 함수 호출이 완료되면 사라집니다. 선입선출구조로. heap영역은 런타임 동안 메모리가 결정되고 프로그래머가 요구한 만큼 OS가 빈공간을 찾아서 할당해줍니다. 선입선출 구조가 아니고 유동적으로 할당/해제되므로 꼭 해제가 필요합니다. (메모리가 조각조각 배분되어 메모리 누수가 발생할 수 있음) 1. 1차원 배열 동적할당 int* arr = new int[5]; //크기가 5인 일차원..

C++은 해시테이블을 unordered_map 이라는 STL로 구현할 수 있다. unordered_map 클래스 다양한 길이의 요소 시퀀스를 제어하는 C++ 표준 라이브러리 컨테이너 클래스 에 대한 API `unordered_map` 참조입니다. docs.microsoft.com * 시간복잡도 해쉬테이블은 key 값으로 탐색하기 때문에 탐색 시간복잡도는 O(1) 밖에 걸리지 않는다. 또한, 정렬할 필요가 없으므로 데이터 추가, 삭제 시에도 그 성능이 꾸준히 보장된다. * map vs unordered_map map 은 정렬이 된다. 레드블랙트리기반이므로 탐색, 삽입, 삭제에 O(longN)의 시간복잡도가 걸린다. unordered_map 은 정렬이 안된다. 해시테이블 기반이므로 탐색, 삽입, 삭제에 평균..

[문제] 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N×M의 행렬로 표현된 맵에서 (1, 1)에서 (N, M)까지 이동할 때 걸리는 최단 경로를 구하는 문제. 이 때, 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타내며 1회에 한하여 벽을 부수고 이동할 수 있다. [풀이] Break 유무를 저장해놓고 한번도 깬 적 없는 벽을 깨가면서 탐색해야 할 것 같은데 그 구조를 못짜겠어서 한참을 헤맸다. 결국 풀이 참조... 이 문제의 핵심은 탐색한 경로를 ..