자료구조 알고리즘(C++)27 [C++] 프로그래머스(Lv.3) 다단계 칫솔 판매 난이도 : Lv3 (중하)알고리즘 유형 : 해쉬, Union-Find, 트리풀이 방법 : 해시와 Union-Find를 활용한 금액 분배 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 예시 문제는 다단계 판매 시스템에서 판매자가 얻은 수익을 그들의 상위 판매자에게 분배해야 합니다. 각 판매자는 10%의 수익을 상위 판매자에게 전달하며, 이 과정을 부모-자식 관계를 기반으로 반복합니다.예를 들어, young이 칫솔을 12개 팔았을 때, 칫솔은 100원이며, 수익은 1200원.. 2024. 11. 5. [C++]백준(BOJ) - 1240 노드사이의 거리(DFS) 난이도 : 골V알고리즘 유형 : 그래프 탐색(BFS, DFS), LCA(최소 공통 조상)풀이 방법 : DFS 문제 경로https://www.acmicpc.net/problem/1240 문제 예시N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 아주 간단한 DFS 문제입니다. 예시의 출력을 보면 노드와 간선 사이는 양방향이며,예외처리가 없는 것으로 보아 연결된 입력만을 받습니다.또한 번호가 중복되지 않기 때문에 간단하게 처리할 수 있습니다. 노드의 간선을 m만큼 탐색하기 때문에 시간복잡도는 O((v + e) * m) 이며,아래는 DFS로 구현한 코드입니다.#include #include #include using namespace std;vector.. 2024. 11. 3. [C++]백준(BOJ) - 2548 키 순서(플로이드-와샬) 난이도 : 골IV알고리즘 유형 : 플로이드-와샬, dfs풀이 방법 : 3중 for문(플로이드-와샬) 문제 링크https://www.acmicpc.net/problem/2458 문제의 예시자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산-> 모든 방법을 탐색한다. a에서 b로 화살표를 그려서 표현하였다.-> 방향 그래프이다. N (2 ≤ N ≤ 500) 인것을 보아 단순 계산을 한다면 O(N^3)으로 풀 수 있습니다.또한, 이 문제는 모든 방법을 탐색해야 하므로 플로이드-와샬을 이용하면 됩니다. 기본적인 min 연산을 하는 플로이드-와샬과 달리 이 문제는 비교를 하는 문제입니다.그렇기 때문에 방향 그래프로 경로가 있을때만 플로이드로 체크만 해주면 됩니다. 플로이드 연산이 완료되면 방향 그.. 2024. 11. 2. [C++]백준(BOJ) - 2457 공주님의 정원(그리디) 난이도 : 골III알고리즘 유형 : 그리디 알고리즘풀이 방법 : 정렬, 그리디 문제 경로https://www.acmicpc.net/problem/2457 문제의 예시오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다. 총 N개의 꽃 -> N (1 ≤ N ≤ 100,000)모두 같은 해에 피어서 같은 해에 짐 하나의 꽃은 피는 날과 지는 날이 정해져 있다. -> Start 와 End 가 있음 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. -> 6월 12일에 끝나면 13일에는 연결되지 않음공주가 가장 좋아하는 계절인 3월 1일부터 1.. 2024. 11. 1. [C++]백준(BOJ) - 1865 웜홀(벨만-포드) 난이도 : 골III알고리즘 유형 : 벨만-포드 알고리즘풀이 방법 : n - 1(간선 최단 경로), edge 순회 문제 경로https://www.acmicpc.net/problem/1865 문제의 예시시간 여행을 좋아하는 백준이는 한 지점에서 출발~도착 왕복했을 때음수가 되어서 시간 여행을 할 수 있는 지 확인하자. TC : 1 N : 1 M : 1 N이 최대 500, TC 최대 5 이기 때문에 5 * 500 플로이드로 한다면 시간초과가 발생할 수 있습니다. 두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. -> 양방향 그래프 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데 -> 방향 그래프 시작 위치에서 도착 위치로 가는 하나의 경로 -> 왕복을 해야함 그래서 왕복을 한다는 관점에서 .. 2024. 10. 31. [C++]백준(BOJ) - 2660 회장뽑기(플로이드-와샬) 난이도 : 골V알고리즘 유형 : 플로이드-와샬, bfs풀이 방법 : 3중 for문(플로이드-와샬) 문제 링크https://www.acmicpc.net/problem/2660 문제의 예시월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 몇 사람을 통하면 모두가 서로 알 수 있다. -> 모두 연결되어있음 가까운 정도에 따라 점수를 받게 된다.회장은 회원들 중에서 점수가 가장 작은 사람이 된다. -> 거리에 따른 정답 A와 B가 친구면, 1점A와 B가 친구고 B와 C가 친구면 A는 2점이렇게 점수를 계산해 두루두루 친한 사람들 회장으로 뽑는 문제입니다. -> 최단 거리라는 것을 알 수 있고, 모두 계산하기 때문에 플로이드로 풀 수 있다. -> 여기서 양방향 그래프라는 것도 알 수 있다. (B, .. 2024. 10. 30. 이전 1 2 3 4 5 다음
