백사니

문제 설명해당 문제는 1번 노드에서 시작했을 때 최단 경로로 가장 멀리 떨어진 노드들의 개수를 구하는 문제다.BFS(너비 우선 탐색)을 사용하여 1번 노드부터 시작해 각 노드까지의 거리를 구한다.그 중 가장 멀리 떨어진 거리를 가지는 노드들의 개수를 세면 된다. 핵심 방법인접 리스트를 구성해 그래프 표현(index 1의 요소들은 1과 연결된 모든 노드)BFS를 통해 각 노드까지의 최단 거리 계산최댓값 거리를 구하고, 그 거리를 가진 노드 개수 반환#include #include #include #include #include #include using namespace std;// BFS를 통해 1번 노드에서 가장 멀리 있는 노드들의 개수를 구하는 함수int bfs(vector>& v){ queue..

문제 설명해당 문제는 불량 사용자 목록(banned_id)에 와일드카드(*)가 포함되어 있으며, 이 와일드카드에 매칭되는 사용자 ID(user_id)를 조합하여 가능한 제재 아이디 목록의 경우의 수를 구하는 문제다. 핵심 방법banned_id의 각 패턴에 대해 user_id에서 매칭 가능한 인덱스를 미리 구해둔다.BFS를 활용해 각 banned_id에 user_id를 하나씩 매핑하면서 중복되지 않도록 제재 아이디 조합을 만든다.각 조합은 set 형태로 저장하고, set>으로 중복 조합을 제거해 경우의 수를 센다. BFS에 대한 자세한 내용은 아래 블로그에서 확인할 수 있다. BFS(Breadth-First-Search) 넓이 우선 탐색BFS는 넓이 우선 탐색으로 이름에서 알 수 있게 넓게 탐색하는 알고..

문제 설명해당 문제는 정수 배열 numbers에서 서로 다른 인덱스에 있는 두 수를 골라 더할 수 있는 모든 경우의 수를 구하고, 그 결과를 오름차순 정렬된 배열로 반환하는 문제이다. 핵심 방법중복 제거를 위해 set을 사용하면 코드가 간결해지고, 자동 정렬도 된다.i와 j 쌍을 중복되지 않게 고르기 위해 j = i+1부터 시작하는 것이 중요하다. set에 대한 자세한 설명은 아래 링크에 정리해두었다. 중복을 방지해주는 자료구조 Setset은 중복을 허용하지 않는 자료구조이다. 즉 set에 중복된 값을 넣을 시 한 번만 저장된다. set은 2가지 종류가 있는데 set과 unordered_set이다. unordered_set은 unordered_map과 마찬가지로 jinho082008.tistory.com..

set은 중복을 허용하지 않는 자료구조이다. 즉 set에 중복된 값을 넣을 시 한 번만 저장된다. set은 2가지 종류가 있는데 set과 unordered_set이다. unordered_set은 unordered_map과 마찬가지로 순서를 보장하지 않는 set이다. 일반적인 set은 순서를 보장해주며 자동으로 정렬된다. 때문에 for문을 통해 원소를 추출 시 순서대로 추출할 수 있다. set과 unordered_set은 내부 구조의 차이가 있는데 이로 인해 정렬 여부와 속도가 차이난다. 이러한 특징 덕분에 set은 안정적으로 O(log N)을 보장하며 unordered_set은 O(1) ~ O(N)의 시간 복잡도가 나온다.SetUnordered_set 때문에 정렬이 필요한 경우엔 set을 정렬은 필요 없..

해당 문제는 원하는 숫자를 가장 빠른게 찾는 문제로 주어진 규칙을 가지고 원하는 숫자를 빠르게 찾는 알고리즘을 만들어야한다.첫 번째 시도#include #include #include using namespace std;int solution(int x, int y, int n) { int answer = 0; //int : 현재 연산 값, int : 연산 횟수 queue> q; //초기 값 x, 연산 횟수는 없으니 0 q.push(make_pair(x, 0)); //q에 원소가 없을때까지 같은게 안 나왔다면 값이 없다는 뜻 while(!q.empty()) { //같은 값이 나왔다면 if(q.front().first == y)..

해당 문제는 정해진 크기의 맵 내에서 움직이는 플레이어의 경로 길이를 계산하는 문제로 문제의 중점은 겹치는 경로를 어떻게 처리할 것인가 로 보인다.내가 접근한 방법은 set을 이용하는 방법이다. set의 특징은 중복되는 데이터를 저장하지 않는다. 즉 이미 저장된 경로라면 중복되게 저장하지 않기에 set의 크기를 확인하면 경로의 길이를 확인할 수 있다. Set에 대해 궁금하면 아래 글을 참고하면 자세히 설명해놨다https://jinho082008.tistory.com/24 #include #include #include using namespace std;int solution(string dirs) { //상하좌우 입력에 따라 움직여야할 좌표를 map으로 매핑 map> m; //입력에 따라 ..