문제 https://algospot.com/judge/problem/read/PACKING algospot.com :: PACKING 여행 짐 싸기 문제 정보 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 algospot.com 풀이 종만북 난이도: 중 일반적인 배낭 문제(Knapsack)에서 추가적으로 어떤 물건을 선택했는지까지 출력해야 하는 문제이다. 배낭 문제는 DP의 대표적인 문제로, 구현 방법에는 재귀 함수를 통해 큰 문제에서 작은 문제로 내려가며 해결하는 Top-Down 방식과 작은 문제에서부터 차례로 답을 찾아 올라가는 Bottom-Up방식이 있다. 이번 문제는 Bottom-Up..

문제 https://algospot.com/judge/problem/read/MATCHFIX algospot.com :: MATCHFIX 승부조작 문제 정보 문제 한때 세계대회 준우승까지 하며 최강의 프로그래머로 칭송 받았던 J씨는 성적이 떨어진 이후 유혹을 이기지 못하고 승부 조작의 세계에 손을 댔습니다. 프로그래밍 대 algospot.com 풀이 종만북 난이도: 중 이 문제를 최대 유량(네트워크 유량)으로 해결하는 방법은 다음과 같다. 이번 문제에서 유량은 승리의 횟수로 생각해 보자. 1. Source에서 각 결승 경기로의 간선 경기는 단 한 번씩만 진행할 수 있기 때문에 간선의 용량은 1로 설정해주자. 결국 모든 경기는 진행되어야 하므로 source에서 각 경기로는 1의 유량이 흐르게 된다. 2. ..

문제 https://algospot.com/judge/problem/read/TPATH algospot.com :: TPATH 여행 경로 정하기 문제 정보 문제 당신은 철도망을 이용해 한 도시에서 다른 도시까지 여행을 하고 싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의 algospot.com 풀이 종만북 난이도: 상 최소 스패닝 트리(MST, Minimum Spanning Tree)을 잘 응용해야 풀 수 있는 문제. MST 문제임에도 0번 도시에서 N-1번 도시까지의 경로 중 속도 차이의 최솟값을 묻고 있다. 최단 경로와는 다르게 경로들 중에서 최대 속도와 최소 속도의 차가 최소가 될 수 있게 만드는 길을 찾고 있다. 이런 문제에서 MST를 어떻게 이용해야 할..

문제 https://algospot.com/judge/problem/read/LAN algospot.com :: LAN 근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일 algospot.com 풀이 종만북 난이도: 하 모든 건물들이 같은 컴포넌트에 속하도록 새로 연결하는 간선들의 최솟값을 구하는 문제이므로 최소 스패닝 트리(Minimum Spanning Tree) 문제이다. 최소 스패닝 트리를 해결하기 위한 알고리즘은 대표적으로 두 가지가 존재한다. 1. 크루스칼(Kruskal) 최소 스패닝 트리 알고리즘 크루스칼 알고리즘은 모든 간선을 저장한..

문제 https://algospot.com/judge/problem/read/DRUNKEN algospot.com :: DRUNKEN Drunken Driving 문제 정보 문제 As the holiday season approaches, the number of incidents caused by Driving While Intoxicated (known as DWI) increases rapidly. To prevent this, the city of Seoul has proclaimed a war against drunken driving. Every day, algospot.com 풀이 종만북 난이도: 중 알고스팟 사이트에는 영문의 문제로 나와있어 당황했지만 종만북의 문제와 동일한 문제가 맞다. ..

문제 https://algospot.com/judge/problem/read/NTHLON algospot.com :: NTHLON 철인 N종 경기 문제 정보 문제 두 나라 A국과 B국은 항상 사이가 좋지 않은데, 국민들 간에 쌓인 감정을 털어버리기 위해 양국의 대표 선수들이 한 명씩 나와 친선 스포츠 경기를 하기로 했다. 채 algospot.com 풀이 종만북 난이도: 상 다익스트라를 이런 식으로도 이용이 가능하다는 것을 알 수 있는 좋은 문제. 그만큼 어렵다... 이번 문제에서 가장 중요한 것은 종목의 진행 순서는 총 코스 소요시간과 상관이 없다는 것이다. 즉, 각각의 종목을 정점으로 설정하여 경로를 만드는 것은 결국 종목의 진행 순서를 만드는 것이므로 이러한 구현이 필요가 없다. 더군다나 이러한 구현..

문제 https://algospot.com/judge/problem/read/FIRETRUCKS algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 algospot.com 풀이 종만북 난이도: 중 처음 문제를 접하면 여러 소방서들에서 불이난 곳으로의 최단 거리를 구해야 된다고 생각하게 됩니다. 하지만 단일 시작점 알고리즘인 다익스트라 최단 경로 알고리즘으로 모든 소방서로부터 불난 곳의 최단 거리를 구하는 것은 시간 초과를 발생시킵니다. 다익스트라 알고리즘의 복잡도는 간선(edge)의 개수를 E라고 할때 O(E logE) 이기..

문제 https://algospot.com/judge/problem/read/HANOI4 algospot.com :: HANOI4 하노이의 네 탑 문제 정보 문제 하노이의 탑은 세 개의 기둥에 꽂혀 있는 N개의 원반을 가지고 하는 게임입니다. N개의 원반은 크기가 모두 다르며, 게임의 시작 때는 그림과 같이 맨 왼쪽의 기둥 algospot.com 풀이 종만북 난이도: 중 재귀 함수 문제의 대표 격인 하노이 탑 문제에 기둥을 1개 더 추가하여 4개인 상태로 해결하는 문제이다. 이번 문제의 핵심은 각 기둥에 꽂혀있는 원판들의 상태를 어떻게 저장하느냐이다. 단순히 4개의 기둥들이 어떤 원판을 가지는지 stack을 사용하여 표현한다면 4개의 스택(각각의 기둥)을 가지는 구조체로 나타낼 수 있을 것이다. 1 2 ..

문제 https://algospot.com/judge/problem/read/CHILDRENDAY 풀이 종만북 난이도: 상!! 상당히 어려운 BFS 문제이다. 문제를 보면 생각나는 간단한 풀이는 자릿수를 사용해 모든 경우의 수를 생성해 보는 것이지만 당연히 시간 초과가 발생한다. 일단 다음의 두 가지 조건만을 만족하는 최소 자연수 C를 구하는 방법을 생각해보자. (어린이의 수를 children_num, 욕심쟁이의 수를 greedy_num이라고 하자.) C를 children_num으로 나눈 나머지는 greedy_num이다. C는 d에 포함된 숫자들로만 구성된다. 이를 구하기 위해서 나머지 연산의 분배 법칙을 이용하자. (A*B) mod n = ((A mod n) * (B mod n)) mod n 따라서 다..

문제 https://algospot.com/judge/problem/read/SORTGAME algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com 풀이 종만북 난이도: 중 BFS문제들은 2차원 좌표상에서 이동하는 문제가 많은데 이번 문제는 전혀 다른 BFS 적용 문제라 신선했다. (그리고 어려웠다...) 1 2 3 4 수열의 구간들이 반전되어 나타나는 수열은 다음과 같이 그래프로 표현이 가능하다. 각 노드들은 1 2 3 4에서 한 구간 만을 반전시킨 것이므로 1번의 뒤집기 연산으로 이동..