공부하자

[BOJ] #11376 열혈강호 2

https://www.acmicpc.net/problem/11376최대 유량 (Max Flow) 의 특수한 형태인 문제들은 기존의 O(V * E^2)의 시간복잡도 대신 이분 매칭이라는 또다른 알고리즘을 통해 O(VE)의 시간으로 해결할 수 있다. 이번 문제 같은 경우가 딱 그런 경우인데, #11375번 열혈강호 문제의 업그레이드 버전이라 볼 수 있다. 사실 업그레이드도 아닌 것이,,, 그냥 한 정점에 대해 DFS와 visited 배열 초기화를 두번씩 돌려주면 된다.다음 그림은 문제에서 주어진 입력값에 대한 이분 매칭 그래프를 그려본 것이다. 일할 사람을 1~5의 숫자로, 해야하는 일을 편의상 A~E까지의 알파벳으로 나타냈다. 또한 visited배열은 각 일에 대한 방문 여부, matched 배열은 해당 ..

https://www.acmicpc.net/problem/17412최근에 공부하고 있는 최대 유량 (Maximum Flow) 관련 문제이다. 기존에 #6086번 문제를 한번 풀어봤었는데, 해당 문제를 풀어보았거나 최대 유량에 대해 알고 있으면, 플래4 난이도의 문제임에도 불구하고 쉽게 해결할 수 있다.최대 유량을 해결하는 알고리즘으로는 다음의 방법이 있다. PS에서의 최대 유량은 보통 이걸 많이 사용하는 듯 하다. Max Flow : 에드먼드-카프 알고리즘(Edmonds-Karp Algorithm):• 포드-풀커슨 알고리즘의 BFS 버전: 포드-풀커슨 알고리즘을 BFS를 사용하여 구현한 것으로, 증강 경로를 찾는 데 BFS를 사용하여 최단 경로를 선택합니다.• 시간 복잡도: O(V * E^2), 여기서 ..

https://www.acmicpc.net/problem/1915배열의 인근을 탐색하며 정사각형이 되는 영역을 판별한 후, DP 배열에 저장하며 가장 큰 넓이 값을 출력해야하므로 계속 초기화 시켜주며 해결하면 된다.사실 DP문제 대부분이 그렇듯 맨 처음에 점화식을 도출하는것이 가장 어려운 법인데, 이 문제 또한 그렇다. 난이도가 골드4인 문제라 DP 이외에 다른 스킬이나 알고리즘이 들어가지는 않고 점화식 자체만 잘 세울수 있으면 쉽게 해결할 수 있을것이다. 문제 예제에서 나온 입력값을 그대로 주었을때, 2차원 배열은 다음과 같이 구성된다. 이때, 0인 원소는 패스하고 1인 원소에 대해 DP를 수행한다.arr[1][1]의 왼쪽, 왼쪽위, 위를 각각 L, LT, T라고 가정하고, 노란색과 주황색의 영역이 둘..

https://www.acmicpc.net/problem/6497난이도는 그렇게 높진 않았는데, 문제 자체에 함정이 몇 개 정도 있는 문제였던 것 같다. 질문 게시판에도 여럿 문제의 입력과 출력 조건에 대해 까다로워 하는 모습이 보였다. 다음은 질문게시판에 있는 한 글을 발췌한 것이다.  https://www.acmicpc.net/board/view/1453601. 제시된 예제는 테스트 케이스가 하나입니다만, 0 0이 등장하기 전에 테스트 케이스가 여러 개가 있을 수 있으므로, 각 테스트 케이스에 대한 정답을 차례차례 저장해두어야 합니다.2. 모든 정답은 '0 0'이 입력된 이후에 순차적으로 출력해야 합니다. (댓글 보고 추가: 하나씩 출력하는 것도 가능하다면 이 항목은 무시하셔도 됩니다.)=> 수정 :..

https://www.acmicpc.net/problem/1647최소 신장 트리, MST를 다루는 기본적인 문제이다.인접리스트 형태로 주어지는 그래프에 대해 MST를 생성하면 되는 문제인데, 한가지 조건이 더 붙었다. 해당 MST를 두 집합으로 나누어서 가중치의 합이 가장 적은 MST 형태를 만들어 내면 되는 것이다. 당연히 그래프를 둘로 나누고 할 필요없이 결론적으로는 MST를 생성하여 구해진 가중치의 합에서 가장 가중치가 큰 간선을 빼주면 된다.이렇게 방향성을 잡고 풀면 되는데 MST 구현에는 보통 두가지 접근 방식이 있다. 하나는 프림 알고리즘 (Prim's Algorithm) 이고, 다른 하나는 크루스칼 알고리즘 (Kruskal's Algorithm) 이다. 전자는 우선순위 큐와 방문여부를 체크하..

https://www.acmicpc.net/problem/2268세그먼트 트리의 가장 대표격이라 할 수 있는 구간합 구하기 문제이다.하지만 이 문제에서 유의해야 할 부분이 두가지가 있는데,1. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 라고 나와있듯, 이 문제에서는 i > j 인 경우 말고도 i 2. 최대가 1,000,000인 경우까지 다루다 보니, 자료형을 신경써야한다. 물론 이는 세그먼트 트리 문제를 풀다보면 어지간해선 다 long long형을 쓰기 마련이지만, 필자는 그냥 아무생각 없이 int로 처음에 풀었다가 틀렸다...이 두 부분만 주의해서 풀면 나머지는 세그먼트 트리를 이용해 부분합을 구하는..

https://www.acmicpc.net/problem/2357시간초과가 나지 않게 세그먼트 트리를 사용해서 푸는 것이 핵심인 문제이다. 필자 또한 처음 풀때 별 생각없이 그냥 벡터 인덱스 접근해서 풀었다가 시간초과가 났다. 생각해보니, 입력값의 최대크기가 100,000이고 애초에 그렇게 해서 풀렸다면 골드1일 이유가 없다. 따라서 시간초과가 나지 않게 하기 위해서는 세그먼트 트리를 이용해서 풀어야한다.보통 세그먼트 트리를 이용해서 푸는 문제들은 보통 구간 합을 구하거나 구성된 트리를 업데이트 하는 그런 문제들이 많은데 (BOJ #2042같은 문제가 대표적) 이 문제는 꼭 구간합을 구하는 문제가 아니더라도 세그먼트 트리를 활용하여 트리를 탐색해야 하는 문제이다.필자는 최솟값을 저장하는 트리와 최댓값을 ..

https://www.acmicpc.net/problem/3197  BFS를 응용한 조금 난이도가 있는 문제이다. 확실히 실버나 골드 문제에 비해 플래티넘 난이도로 올라가다 보니 쉽지않았던 것 같다.필자가 해결한 방법은 이분 탐색을 이용한 풀이인데, 이 풀이의 핵심은 'N일차에 백조들이 만나지 못한다면, N일 전의 날들은 백조들이 모두 만날 수 없다는 점' 을 이용하는 것이다. 이를 이용하기 위해, 미리 얼음이 녹는 날에 대한 계산을 해야 한다. 즉, 1일차에 녹는 얼음, 2일차에 녹는 얼음 ... 이런 식으로 얼음에 번호를 부여하면 가장 마지막에 녹는 얼음을 구할 수 있고, 0일 차부터 마지막 날까지에 대해 이분 탐색을 진행할 수 있다. 테스트 케이스로 주어진 맵을 얼음이 녹는 날로 나타내면, 다음과 ..

최대공약수 GCD (Greatest Common Divisor) 두 자연수가 공통으로 가지는 약수들 중 가장 큰 값을 의미한다. 최소공배수 LCM (Least Common Multiple) 두 자연수의 배수들 중에서 가장 작은 값을 의미한다. 참고로 최소공배수는 최대공약수를 활용하여 바로 구할 수 있다. 최소공배수 = 두 자연수의 곱 / 최대공약수 유클리드 호제법 (Euclidean Algorithm) 유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a,b에 대해 a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀함수 호출을 통해 해결해야 하는 문제이다. 처음엔 주어진 전체 넓이 N을 탐색하다가 조건에 맞지 않으면 재귀적 호출을 통해 4등분된 넓이들을 조건에 맞는 모양이 나올때까지 탐색해야한다. 만들어진 코드 자체는 간단하게 보여도, 매커니즘을 떠올리는것이 좀 어려웠다. 특히 재귀함수에 전달할 인자들을 설정하고 범위를 지정해주는것에 많은 시간을 할애했던 것 같다. 재귀함수 문..