나 요리학원 출신임

Cycle이 있는지 없는지 판단하는 문제다!간단하게 Cycle찾는 함수를 구현하면 풀수있다...! 소스코드123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;int n, m;int cycle[111];vector Graph; bool isCycle(int x) { if (cycle[x]) { if (cycle[x] == -1) return true; return false; } cycle[x] = -1; for (int i = 0; i

트리의 전위,중위 순회 결과를 주고 후위 순회 결과를 구하는 문제다재귀를 잘 이용하면 풀 수 있다 방법은1. 전위순회에서 첫번째 노드는 루트라는것을 기억한다!2. 후위순회에서 루트기준 앞쪽 노드들은 왼쪽, 뒷쪽은 오른쪽 서브트리다3. 후위 순회를 출력하므로 왼쪽 오른쪽 순서로 함수를 호출하고 루트를 출력한다 후위순회에서 루트 위치를 찾기 위해 map을 사용했다! 소스코드12345678910111213141516171819202122232425262728293031323334#include #include #include #include using namespace std;int t, n, pre[1010], in[1010];map mp; void go(int s, int e,int x, int y) { ..

전위순회를 주고 후위순회한 결과를 출력하는 문제다트리를 직접 만들어도 되지만 그러면 귀찮다 푸는방법은 전위,후위순회를 할 때 방문하는 노드를 생각해보면된다 전위순회한 결과에서 첫번째 노드는 항상 루트다그리고 두번째 노드부터 루트보다 큰노드가 나오기 전까지는 왼쪽서브트리큰노드부터 마지막까진 오른쪽 서브트리다 그럼 범위를 쪼개가며 재귀로 타고 들어가서왼쪽 오른쪽 순서로 들어가며 루트를 출력해주면 원하는 답을 얻을 수 있다!그림을 그려서 생각해보면 쉽다! 소스코드12345678910111213141516171819202122#include #include using namespace std;int arr[10010], n; void go(int l, int r) { if (l > r) return; int r..

문제 설명이 애매하다..! 풀이는 간단하다 1. 입력받은 인용수를 배열에 넣고 정렬시킨다.2. 0~10000까지를 다 돌아보며 k를 정해준다3. k의 lower_bound부터 upper_bound까지가 확인 해 줄 범위다왜냐하면 k의 lower_bound 부터 upper_bound 이전까지는 k번 이하를 만족한다!4. 범위를 돌며 k이상 인용한게 k와 같은지 확인한다 소스코드12345678910111213141516171819202122#include #include using namespace std;int n;int arr[1010]; int main() { scanf(" %d", &n); for (int i = 0; i

비트를 이용한 완전탐색 또는 DP로 해결할 수 있는 문제다삼성 소프트웨어 역량테스트에 자주 나오는 유형같다 1. 먼저 비트를 이용한다면 인사한사람은 1 안한사람은 0으로 표현해서 모든 수를 표현해보면 된다.최대 (1

1~n 까지의 수를 스택에 넣을 때 push , pop 을 이용해 주어진 배열을 만들수 있는지 알아보는게 문제다 1부터 차례로 넣으므로만약 스택이 비었거나 또는 top이 현재보는 수와 같지 않다면현재보는 수 까지 스택에 넣으면 된다 근데 만약 이 때 넣는수가 n보다 커진다면 만들수 없는 배열이 된다!!이것만 잘 처리해준다면 쉽게 풀 수 있다..! 소스코드12345678910111213141516171819202122232425262728293031323334#include #include #include #include using namespace std;int n;int arr[100010];stack st;vector ans; int main() { int it = 1; scanf(" %d", &n)..

차집합의 합집합 수를 구하는 문제이다set을 이용하면 쉽게 풀 수 있다 1. set을 하나 만들고 A의 원소를 다 넣는다2. B의원소를 확인하며 이미 set에 있다면 지우고 없다면 넣는다3. set의 크기가 곧 답이다! 소스코드123456789101112131415161718#include #include using namespace std;set a;int n, m;int main() { scanf(" %d %d", &n, &m); for (int i = 0; i

트리의 지름 구하는법을 들어만봤는데 이번에 처음으로 구해봤다weeklyps.com을 보며 공부했다! 2가지 방법이 있는데 그리디를 이용하는게 쉽길래 그리디 이용 ㅎㅎ 방법은 간단한다 1. 임의의 정점 a에서 가장 먼~~ 정점 b를 찾는다2. 그 후 찾은 정점 b에서 가장 먼~~ 정점 c를 찾는다3. 그럼 b에서 c까지의 거리가 트리의 지름이 된다 증명은 복잡하므로 생략 소스코드12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #include using namespace std;vector Graph;int n, d[10010];bool check[10010]; int dfs(int..

Cycle찾는 함수 만들어서 풀다가 계속 틀렸다 ㅎㅎ얼마전 코포 Div3 E번과 거의 똑같은 문제다 푸는 방법은 1. 각 정점의 deg배열을만들고 그래프를 입력받을 때 계산해준다2. check안된 곳에서 dfs를 돌린다3. (정점 == (간선/2)+1) 이라면 우리가 원하는 트리다 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include #include #include using namespace std;vector Graph;vector vt;int deg[505];bool check[505];int n, m, v, e; void dfs(int ..

하하하 알고리즘 하나도 기억이 안나서 오늘부터 글을 쓰면서 강제로 기억해야겠다. 쉬운것부터 차근차근 다시 해야지..! 이 문제는 Cycle을 찾는 문제이다. 조건은 처음시작한 정점으로 마지막에 다시 돌아오는 것인데 중간에 다른 정점으로 빠지는 간선이 존재하면 안된다..! 이 사진중에 (15, 5, 11, 9) / (7, 10, 16) 만이 조건을 만족하는 Cycle이다! 처음에 dfs를 돌리고 (정점*2 == 간선) 했다가 18번째 테케에서 틀렸다 ㅎ 솔루션은 1. 각 정점의 degree를 구한다 2. dfs를 돌리며 방문한점을 벡터에 넣어준다. 3. dfs가 끝난 후 벡터에 들어있는 정점들이 모두 2의 degree를 갖는다면 문제에서 원하는 cycle이다! 이렇게 찾아주면 된다! 소스코드12345678..