우노

문제 링크 https://www.acmicpc.net/problem/2178 풀이 중요 내용 (0, 0) 에서 (N-1, M-1) 까지의 최소 칸수를 구하는 문제 최단 경로 탐색 시, 현재까지 이동한 칸의 개수를 저장해나가며 탐색하는게 중요하므로, 이동한 칸의 개수를 2차원 배열에 저장하며 진행 탐색은 상하좌우로만 진행하며, 아직 방문하지 않았고, 이동 가능한 칸일 경우에만 이동함 좌측 미로를 BFS 탐색할 경우, 이동칸 결과는 우측과 같음 코드 #include #include #define MAX 101 using namespace std; int N, M; // 미로 크기 int maze[MAX][MAX]; // 미로 표현용 2차원 배열 int visited[MAX][MAX]; // 방문 기록용 2차..

문제 링크 https://www.acmicpc.net/problem/9466 풀이 중요 변수 설명 done : 팀 매칭 결과 배열 0 : 아직 팀 매칭 결과를 모르는 학생 1 : 팀 매칭 결과를 아는 학생 visited : 방문 배열 0 : 아직 방문하지 않은 학생 1 : 방문한 학생 알고리즘 반복문을 통해, 현재 학생이 아직 방문한 적이 없는 학생이라면, 탐색 시작 현재 학생은 방문한 것으로 처리 현재 학생이 원하는 다음 학생이, 이전에 방문된 적이 없다면, 다음 학생을 탐색 현재 학생이 원하는 다음 학생이, 이전에 방문된 적은 있지만, 아직 팀 매칭이 끝나지 않은 학생이라면 현재 학생과 다음 학생을 기준으로, 연결된 사이클을 확인하며, 사이클에 속한 인원을 계산 4 → 7 → 6 → 4 인 경우, 팀..

문제 링크 https://www.acmicpc.net/problem/2110 풀이 중요한 부분 문제가 원하는 것은, 가장 인접한 두 공유기 사이의 거리가 최대인 것이지만, 결국, 모든 공유기들의 간격이 공평하게 설치되기를 원한다고 해석할 수 있습니다. 따라서, 모든 공유기들을 공평하게 설치할 수 있는 간격을 이분 탐색을 통해 찾아야합니다. 진행 순서 공유기 설치 좌표들을 오름차순으로 정렬합니다. 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한 뒤, 공유기를 가장 공평하게 설치할 수 있는 간격(mid)을 구합니다. 첫 번째 집에 공유기를 설치한 뒤, 첫 번째 집에서 나머지 집들 간의 간격을 확인하며, mid 이상으로 떨어져 있는 집을 탐색합니다. 첫 번째 집으로부터 mid 이상 떨어진 집을 찾은 경..

문제 링크 https://www.acmicpc.net/problem/2447 풀이 N 은 반드시 3의 거듭제곱(3, 9, 27, ...)입니다. 따라서, 우선 작은 N 을 가지는 정사각형에 별을 찍어보며, 어떤 좌표값이 공백인지를 확인해, 공백인 좌표를 일반화 해야합니다. N=3 3x3 크기 기준, 중앙 공백 좌표 (1, 1) i % 3 == 1 && j % 3 == 1 N=9 9x9 크기 기준, 중앙 공백 좌표 (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5) (i / 3) % 3 == 1 && (j / 3) % 3 == 1 3x3 크기 기준, 중앙 공백 좌표 (1, 1), (1, 4), (1, 7), (4, 1), (4, 4..

문제 링크 https://www.acmicpc.net/problem/6086 풀이 우선, 해당 문제를 해결하기 위해선, Network Flow 의 기본 개념과 주요 알고리즘에 대해서 알고 있어야합니다. https://wooono.tistory.com/401 해당 문제는, A 부터 Z 까지의 최대 유량을 구하는 것입니다. Network Flow 주요 알고리즘인 에드몬드-카프 알고리즘을 사용해 해결할 수 있습니다. 주의할 점은, 해당 문제의 모든 간선은 양방향이므로, A → B 간선의 유량을 입력 받았을 때, B → A 간선의 유량도 동일하게 할당해야한다는 것입니다. 코드 #include #include #include #include using namespace std; #define MAX_NODE 52..

최대 유량 문제 (Maximum Flow Problem) 특정한 지점에서 다른 지점으로, 얼마나 많은 유량(flow)을 동시에 보낼 수 있는지 계산하는 문제입니다. 네트워크 플로우(Network Flow)라고도 합니다. 기본 용어 용량 (Capacity) c(u, v) : 정점 u 에서 v 로 전송할 수 있는 최대 용량 유량 (Flow) f(u, v) : 정점 u 에서 v 로 실제 흐르고 있는 유량 잔여 용량 (Residual Capacity) r(u, v) = c(u, v) – f(u, v) 간선의 용량과 살제로 흐르는 유량의 차이 소스 (Source) s : 모든 유량이 시작되는 정점 싱크 (Sink) t : 모든 유량이 도착하는 정점 증가 경로 소스에서 싱크로 유량을 보낼 수 있는 경로 기본 속성 ..

문제 링크 https://www.acmicpc.net/problem/1753 풀이 해당 문제를 해결하기 위해선, 다익스트라 알고리즘에 대한 이해가 필요합니다. https://wooono.tistory.com/397 다익스트라 알고리즘은, 시작 노드와 다른 노드들 간의 최단 경로를 구하는 알고리즘입니다. 다익스트라는 최소 비용 배열을 갱신하는 과정에서, 배열 또는 우선순위 큐 자료구조가 사용되지만, 배열은 방문 여부 확인 및 최소 비용 노드 탐색 과정에서, 선형 탐색으로 인해 시간 복잡도 문제가 발생하기 때문에, 해당 포스트에서는 우선순위 큐를 사용합니다. https://wooono.tistory.com/392 우선 순위 큐는, 시작 노드부터 어떤 도착 노드까지의 최소 비용으로 확인되는 경로들을 담아놓으며..

다익스트라(Dijkstra) 최단 경로 알고리즘이란? 다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다. ‘음의 간선'이 없을 때 정상적으로 동작합니다. 물론, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로, 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 합니다. 다익스트라 최단 경로 알고리즘은 그리디 기반입니다. 그리디 매번 ‘가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복합니다. 구체적인 동작 과정 출발 노드를 설정한 뒤, 방문합니다. 최단 거리 배열을 초기화합니다. 아직 방문하지 않은 전체 노드들 중에서, 최단 거리..

문제 링크 https://www.acmicpc.net/problem/2156 풀이 포도주는 두 잔까지만 연달아 마실 수 있다. Wine 라는 배열이 존재하며, Wine[N] 은 N 번째 잔의 양을 의미한다. D 라는 배열이 존재하며, D[N] 은 N 번째 잔까지 탐색했을 때의 마실 수 있는 최대 양을 의미한다. D[4] 는 4번째 잔까지 탐색했을 때, 마실 수 있는 최대 양을 의미한다. D[N] 은 아래와 같은 경우의 수로 계산할 수 있다. Wine[N] 번째 잔을 마신다. Wine[N - 1] 번째 잔을 마셨을 경우 Wine[N - 1] 번째 잔과 Wine[N] 번 째 잔까지 총 2 잔을 마셨으므로, 더 이상의 잔을 더할 순 없다. 따라서, D[N] 은, [N - 3] 번째 잔까지 마신 포도주의 양 D..

문제 링크 https://www.acmicpc.net/problem/11000 풀이 해당 문제를 풀기 위해, 요소 삽입과 동시에 내부 요소를 정렬하는 Priority Queue 라는 자료구조를 사용했으며, 개념에 대해선 추가적인 숙지가 필요합니다. https://wooono.tistory.com/392 이제, 문제에서 주어진 예제 (1,3) (2,4) (3,5) 를 통해서 풀이해보겠습니다. 우선 수업 목록을, 시작 시간 기준으로 오름차순 정렬합니다. 그 다음, 시작시간이 가장 빠른 수업(1, 3) 의 종료시간(3) 을 Priority Queue 에 push 합니다. 그리고, 두 번째로 시작시간이 빠른 수업(2,4) 의 종료시간(4) 을 Priority Queue 에 push 합니다. 이제, Priorit..