Brute force Study

스프링 핵심 원리 이해2 - 객체 지향 원리 적용새로운 할인 정책 개발새로운 할인 정책을 확장해보자.주문한 금액의 %를 할인해주는 새로운 정률 할인 정책을 추가하자.RateDiscountPolicy 코드package hello.core.discount;import hello.core.member.Grade;import hello.core.member.Member;public class RateDiscountPolicy implements DiscountPolicy { private int discountPercent = 10; @Override public int discount(Member member, int price) { if (member.getGrade() == G..

문제https://www.acmicpc.net/problem/11724   무방향 그래프에서 연결 요소를 찾는 문제틀렸던 부분N개의 노드가 있고, 1개의 간선이 있다고 하자. 그러면 연결 요소는 1개가 아니라 N-2개여야 한다. 즉, 연결되어있지 않은 노드들을 고려하지 않아서 2트한 문제이다. 코드#include using namespace std;bool vis[1002];unordered_set sub;vector adj[1002];void DFS(int start) { vis[start] = 1; sub.erase(start); for (int i = 0; i > n >> m; for (int i = 0; i > s >> e; adj[s].push_back(e); ..

강한 연결 요소동영상 서비스 사이트에서 다양한 채널 구독자 간의 공통점에 대한 통계를 작성하여, 서로 연관이 있는 구독 정보 그룹으로 나누려고 한다. 이 때 방향 그래프에서 나타나는 공통적인 특징을 이용하여 이러한 복잡한 문제를 해결할 수 있다. 방향 그래프에서 에지는 명시적인 "방향" 정보를 가진다. 방향 그래프에서 에지는 한쪽 방향으로만 이동할 수 있기 때문에 그래프의 특정 정점에 도달할 수 있는지 여부는 탐색을 어느 정점에서 시작했는지에 따라 다르게 결정된다.주어진 그래프를 여러 개의 구역으로 나누되 같은 구역 안의 정점끼리는 서로 이동 가능한 경로를 갖도록 나눌 경우, 각 구역은 해당 그래프의 강한 연결 요소를 나타낸다. 방향 그래프와 무방향 그래프에서 연결성무방향 그래프에서 연결 요소(conne..

벨만 포드 알고리즘그래프의 모든 에지에 대해 다익스트라의 그리디 선택 방법을 (V - 1)번 반복하여 점진적으로 최단 거리를 찾는다 (V는 정점의 개수)음수 가중치가 있는 그래프를 다룰 때 벨만 포드 그래프를 사용할 수 있다.다익스트라 알고리즘에 비해 높은 점근적 시간 복잡도를 가지지만, 다익스트라 알고리즘이 잘못 해석할 수 있는 그래프에 대해서도 정확한 결과를 제공한다. 벨만-포드 알고리즘 구현각 정점의 최단 거리 값 배열을 반환하는 함수struct Edge{ int src; int dst; int weight;};const int UNKNOWN = INT_MAX;vector BellmanFord(vector edges, int V, int start){ vector distance(V, UNKNOWN..

단일 시작 최단 경로 문제"주어진 그래프에서 시작 정점과 목적 정점이 주어질 때 시작 정점에서 목적 정점까지 이어지는 최소 비용 경로를 구하는 문제" 다익스트라 알고리즘이란?음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변형한 형태이다.프림 알고리즘과 다익스트라 알고리즘의 차이점프림 알고리즘 : 경계로부터 최소 거리의 정점의 거리 값으로 설정. 모든 정점을 방문해야 종료다익스트라 알고리즘 : 시작 정점으로부터 각 정점까지의 전체 거리를 사용. 목적 정점이 나타나면 종료 다익스트라 알고리즘의 동작모든 정점의 거리 값을 무한대로 초기화한다. 시작 정점에서 자기 자신까지의 거리는 0이므로 시작 정점의 거리 값은 0으로 설정한다. 그리고 모든 거리 값을 최소 ..

크루스칼 알고리즘그래프의 최소 가중치 에지를 차례대로 추가하여 MST를 구현한다.시간 복잡도 : O(E log V)주로 적은 수의 에지로 구성된 희소 그래프(sparse graph)에서 사용된다 프림 알고리즘그래프의 아무 정점부터 시작하여 MST를 구성한다가장 널리 알려진 시간 복잡도는 O(E + V log V)이다.주로 많은 수의 에지로 구성된 밀집 그래프(dense graph)에서 사용된다

MST 문제란?정점 집합 V와 가중치를 갖는 에지 집합 E로 구성된 그래프 G = 가 주어질 때, 모든 정점을 연결하고 연결된 에지의 가중치 합이 최소인 트리 T를 구하는 문제 Cf) 크루스칼 알고리즘그래프의 모든 에지를 최소 힙에 추가하고 사이클을 만들지 않는 최소 가중치의 에지를 이용하여 MST를 구성한다 프림 알고리즘은?BFS의 동작 방식과 유사하다.먼저 시작 정점을 이용하여 경계를 구성한다경계는 이전에 방문했던 정점들에 의해 구성된다현재 경계에 인접한 정점을 반복적으로 탐색한다이 때 경계를 관통하는 에지 중에서 가장 가중치가 적은 에지를 선택하고, 이 에지이 연결된 정점을 방문한다'프림 알고리즘을 구현하려면 그래프의 각 정점에 경계로부터의 거리(distance)정보를 기록해야 한다. 프림 알고리즘..

이분 그래프란?정점을 두 개의 집합으로 나눌 수 있는 그래프그래프의 모든 에지는 서로 다른 집합에 속한 정점끼리 연결되어야 한다.ex) 학생 목록과 수업 목록을 모델링하는 경우ex) 스트리핑 플랫폼에서 영화 목록과 시청자 사이의 관계를 모델링하는 경우최대 매칭 또는 최소 정점 커버 문제와 같은 NP-완전 문제들이 이분 그래프에서는 다항시간으로 풀 수 있다.따라서 주어진 그래프가 이분 그래프인지 아닌지 판별하는 것은 매우 중요하다 이분 그래프의 구현DFS를 변형하여 만들 수 있다.1번 정점부터 DFS를 시작한다고 가정한다(1번 정점을 스택에 추가한다)스택에 방문하지 않은 정점이 남아있다면 스택에서 정점을 하나 꺼내고 이를 현재 정점으로 설정한다이전 정점에 할당된 색상이 검은색이면 현재 정점에 빨간색을 할당..

이 내용에 대해선 앞으로 보완해나갈 예정입니다. 많은 문제를 풀어보면서 최대한 정리해보겠습니다.BFS vs DFSBFSBFS는 시작 정점에서 가까운 정점을 찾는데 적합하다큐를 이용하여 가까운 원소들부터 탐색하기 때문최단 거리 경로를 찾는데 적합하다.BFS에서는 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장된다.BFS는 현재 경계에서 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며, 많은 메모리를 필요로 한다DFSDFS는 대체로 시작 정점에서 멀리 있는 정점을 찾을 때 적합하다.재귀적인 풀이 방식에 적합하다 (후입선출의 스택 구조를 사용하기 때문)백트래킹 방식의 PS 풀이에서 적합하다.모든 경우를 하나 하나 다 탐색해야 하는 경우 적합하다..

깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)는 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방법을 백트래킹(backtracking)이라고 한다.DFS 구현BFS에서는 방문하지 않은 정점을 저장하기 위해 큐를 사용했다.큐를 사용하기 때문에 가장 가까이에 있는 정점부터 접근이 가능했다.하지만 DFS는 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하기 때문에, 스택을 사용한다.후입 선출 속성을 갖는 스택을 사용하기 때문에 현재 정점과 인접한 정점들을 재귀적으로 이동하면서 방문할 때 사용하기에 적합하다.PS에서 그래프를 나타내야하는 경우 인접 행렬..