N

https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr Map을 이용한 문제 풀이. map = enroll과 referral 배열의 부모-자식 관계를 나타내기 위한 Map. profit = 각 사람들의 판매 이익을 나타내기 위한 Map. enroll을 순회하면서 부모-자식 관계를 나타내도록 하자. enroll[i]를 key, referral[i]를 value로 가지도록 하여 map에 저장한다. 이후 seller..

https://programmers.co.kr/learn/courses/30/lessons/86971?language=cpp 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr bfs를 활용한 문제 풀이. 우선 주어진 wires 벡터로 그래프를 그려 주도록 하자. 이후 한 노드를 선택해 연결 되어 있는 노드를 끊고 BFS 탐색을 진행하여 끊은 노드의 개수를 구하면 된다. 이때, n * n 크기의 visited 벡터를 만들어, 이미 끊었던 간선을 다시 끊는 일이 없도록 가지를 친다. bfs() 함수에 그려 놓았던 그래프와 n, 현..

그래프(Graph) 정점과 정점 사이를 연결하는 간선으로 이뤄진 비선형 자료구조. 정점 집합과 간선 집합으로 표현할 수 있다. 지하철 노선도나 인물 관계도를 떠올리면 쉽게 이해할 수 있다. 정점은 여러 개의 간선을 가질 수 있다. 방향 그래프와 무방향 그래프가 존재. 간선은 가중치를 가질 수 있다. 사이클이 발생할 수 있다. JS에서 인접 행렬, 인접 리스트로 그래프를 표현할 수 있다. 무방향 그래프 간선으로 이어진 정점끼리는 양방향으로 이동이 가능. ex) (A, B) == (B, A) 방향 그래프 간선에 방향성이 존재하는 그래프. 양방향으로 갈 수 있어도 와 는 다른 간선으로 취급된다. 코드 // 인접 행렬 const graph = Array.from(Array(5), () => Array(5).fi..

문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. N개의 노드와 M개의 간선을 그래프로 나타낸 후, DFS를 통해 연결 요소의 개수를 확인한다. 방향이 없기 때문에 graph[u][v] = true, graph[v][u] = true로 하여 한번 방문했던 노드는 방문하지 않도록 처리해야 한다. 또한, visited 벡터도 함께..

문제 이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다. 이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하..

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWbHcWd6AFcDFAV0&categoryId=AWbHcWd6AFcDFAV0&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 그래프에서 3개의 간선이 서로 이어져있는지 확인하면 된다. x, y 좌표를 입력받아 해당 좌표의 map을 true로 바꾼다. 3중 for문을 통해 [i][j], [j][k], [k][i]가 true이면 ans++을 해주고, 마지막에는 6을 나눠 출력한다. 왜냐하면 [i][j], [j][i] / [j][k], [k][j] / [k][..

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com DFS를 이용한 그래프 방문. #include using namespace std; int ans; int N, M; bool graph[11][11]; bool visited[11]; void dfs(int start, int current) { if(ans < current) ans = current; for(int i =..