공부하자

https://www.acmicpc.net/problem/1504문제에서 요구하는 조건은 상당히 간단하다. 특정 정점 두개를 입력받아서 해당 정점들을 무조건 통과하는 경로 중 최단 경로를 출력하면 된다. 이때 출발지점은 1로 고정이고, 도착지점은 N으로 고정이다. 즉, 출발지점 -> v1 -> v2 -> 도착지점 이렇게 3개의 경로로 나누어 다익스트라를 3번 수행해주면 된다.이때 주의할 점은 v1 -> v2 로 가는 경우와 v2 -> v1으로 가는 경우가 다르기 때문에 케이스를 두개로 잡고 계산하여야 한다. 기존에 void 타입으로 쓰던 dijkstra algorithm을 int 타입 벡터 dist를 리턴하도록 설계하여 각 경로마다 다른 dist 벡터를 도출하고, 도출된 dist 벡터에서 각 출발지와 도..

https://www.acmicpc.net/problem/9789실버1 난이도라 문제 자체는 그렇게 어렵지 않은데, 그래프를 탐색하는 방법 중 가장 대중적인 DFS와 BFS를 한번에 연습하기 좋은 문제이다. 또한 아예 영어로만 되어있는 문제라 ICPC 대회를 준비하기 위해 영어문제 푸는 연습을 하기 위해 한번 풀어보았다. 입력에서 주어진 그래프를 구성하고, 해당 그래프에서 A -> B로 갈수있는지 없는지 여부를 판단하여 출력해주면 되는 문제이다. 당연히 A -> B의 입력이 들어올때마다 DFS나 BFS를 돌려 최적화된 visited 배열을 가지고 방문 가능 여부를 판단해주면 된다.이번 문제를 풀면서 확실히 왜 PS에서 BFS보다 DFS를 더 선호하는지 알 수 있었다. 일단 코드 자체가 굉장히 간단하고, ..

https://www.acmicpc.net/problem/1956플로이드-워셜 알고리즘을 활용해서 그래프 내에서 가장 최소비용의 사이클 여부를 판별하는 문제이다. 사이클이 존재하면 가장 최소비용의 거리를, 존재하지 않으면 -1을 출력하면 된다.여기서 "사이클" 이란, 자기 자신의 정점에서 출발에 다시 자기 자신으로 돌아오는 경로를 말한다. 따라서 필자는 플로이드-워셜 알고리즘을 이용해 출발정점과 도착정점이 같은 것들 중, 거리가 INF가 아닌 것들을 골라서 set 자료구조에 담고, set이 비어있으면 (즉, 자기 자신에서 자기 자신으로 돌아오는. 사이클이 존재하지 않으면) -1을 출력하고, 그렇지 않을 경우 set의 가장 첫번째 인자를 역참조하여 출력해내는 방식으로 설계하였다.set을 쓴 이유는, BST..

https://www.acmicpc.net/problem/14433상당히 가슴아픈 문제이다. 양 팀에 트롤짓을 하는 팀원이 무조건 있는데, 트롤링을 하는 팀원이 더 적은쪽이 이겼다는 문구를 띄워야 한다. 한쪽 집합은 게임에 임하는 플레이어의 집합, 다른 한쪽은 각 팀별 트롤픽 집합을 둔 뒤에 이분 매칭을 통해 어떤 쪽이 매칭이 더 적은지 판별하면 되는 문제이다. 사실 플래티넘4 난이도의 문제라고 하기엔 알고리즘 딱 하나만을 써서 푸는 문제여서 그다지 어렵진 않았다. 이분 매칭 알고리즘을 잘 적용할 수 있으면 바로 풀 수 있는 문제인 듯.다음 그림을 보자. 기본으로 주어져있는 입력 예시를 그대로 이분그래프 형태로 나타낸 것이다.파란색으로 쓴것이 팀원의 숫자이고, 빨간색이 각 팀별 트롤픽의 수인 K1 과 K..

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로 처음에 풀었다가 틀렸다...이 두 부분만 주의해서 풀면 나머지는 세그먼트 트리를 이용해 부분합을 구하는..