알고리즘 풀이/알고리즘 해결전략 연습
-
K번째 LIS 구하기 (KLIS) :: 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 24. 23:08
문제 : https://algospot.com/judge/problem/read/KLIS algospot.com :: KLIS K-th Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 어떤 부분 수열이 _단조 증가_할 때 이 부분 수열을 증가 부분 수열 (increasing algospot.com 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 ..
-
모스 부호 사전 (MORSE) :: 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 23. 02:58
문제 : https://algospot.com/judge/problem/read/MORSE algospot.com :: MORSE 모스 부호 사전 문제 정보 문제 모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 들어 알파벳 J는 모스 부호 o---로 표현되고, M은 --로 표현됩니다. n개의 장점과 m개의 단점으로 구성된 모든 신호들을 담고 있는 사전이 있다고 합시다. 예를 들어 n = m = 2라면 다음과 같은 신호들이 포함되어 있는 것이죠. --oo algospot.com 문제 모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신..
-
POLY 폴리오미노 :: 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 13. 00:52
문제 : https://algospot.com/judge/problem/read/POLY 문제정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다.예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아닙니다. (c)는 맨 오른쪽 아래 있는 정사각형이 다른 정사각형과 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아닙니다.n개의 정사각형..
-
캐나다 여행 :: 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 8. 01:12
문제 : https://algospot.com/judge/problem/read/CANADATRIP 문제동건이는 여름 방학을 맞아 자동차를 끌고 캐나다 횡단 여행을 떠나기로 했습니다. 캐나다의 1번 고속도로는 세계에서 가장 긴 고속도로 중 하나로, 캐나다의 동쪽 끝에서 서쪽 끝까지 있는 모든 주요 도시를 연결합니다. 동건이는 이 고속도로를 타고 캐나다의 서쪽 끝 빅토리아에서 동쪽 끝 세인트 존까지 8,030km 를 달리기로 마음먹었습니다.이 고속도로는 굉장히 많은 표지판이 있기로도 유명합니다(이 문장부터는 사실이 아닙니다..). 이 고속도로는 N개의 주요 도시를 지나치는데, 각 도시까지의 남은 거리를 나타내는 표지판이 많기 때문입니다. i번째 도시까지의 거리를 나타내는 표지판은 도시에 도착하기 Mi미터 ..
-
남극 기지 :: 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 7. 03:59
문제 : https://algospot.com/judge/problem/read/ARCTIC 문제남극에는 N 개의 탐사 기지가 있습니다. 남극의 겨울은 혹독하기 때문에, 남극의 겨울이 찾아오면 탐사 기지들간의 왕래가 중단됩니다. 겨울에도 서로 통신하며 연구를 지속하기 위해, N 개의 무전기를 구입해 각 탐사 기지에 배치하려 합니다. 이 때, 두 탐사 기지 사이의 거리가 D 라고 하면, 무전기의 출력이 D 이상이어야만 통신이 가능합니다. 모든 탐사 기지에는 똑같은 무전기가 지급됩니다. 탐사 본부가 다른 모든 기지에 연락을 할 수 있기 위해 필요한 무전기의 최소 출력은 얼마일까요?탐사 본부는 다른 기지를 통해 간접적으로 연락할 수 있다고 가정합니다. 코드 ( C ++ ) 종만북 참조#include #incl..
-
Sorting Game 알고스팟알고리즘 풀이/알고리즘 해결전략 연습 2019. 9. 5. 01:53
문제 : https://algospot.com/judge/problem/read/SORTGAME 문제중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면 두 번만의 연산으로 정렬할 수도 있다.정렬을 위해 뒤집기 연산을 최소 몇 번 해야 하는지를 계산하는 프로그램을 작성하라. 코드 ( C++ ) 종만북 참조 #include #include #inc..
-
음주 운전 단속알고리즘 풀이/알고리즘 해결전략 연습 2019. 8. 22. 23:40
문제 : https://algospot.com/judge/problem/read/DRUNKEN 코드 ( C ++ ) 종만북 참조 #include #include #include using namespace std; int V, adj[500][500], E;// 각 정점에서 음주 운전 단속을 할 때 걸리는 시간int delay[500];int W[500][500];const int INF = 987654321;// 입력을 받을 때 1부터 시작하는 정점 번호를 0부터 시작하도록 변경했다고 가정한다void solve() {// 모든 정점들을 예상 시간 별로 정렬한다vector order;for (int i = 0; i < V; ++i)order.push_back(make_pair(delay[i], i));s..