알고리즘 풀이
-
백준(BOJ) 1436번 영화감독 숌알고리즘 풀이/백준(Boj) 2019. 7. 29. 01:00
문제 : https://www.acmicpc.net/problem/1436 문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다..
-
백준(BOJ) 2750번 수 정렬하기알고리즘 풀이/백준(Boj) 2019. 7. 26. 16:39
문제 : https://www.acmicpc.net/problem/2750 문제N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 나의풀이 : N이 최대 1000이니 삽입정렬의 시간복잡도(N^2)로도 충분히 가능하기에 삽입정렬로 풀이 하였다. 삽입정렬은 필요한 만큼만 정렬을 할 수 있기에N^2의 복잡도중 가장 효율이 좋다. 사실 이 문제는 c++ stl algorithm에 std::sort 로 간단히 해결 가능하다. std:sort는 quicksort를 기반으로 구현되며 nlgn 에 복잡도를 보장하기 때문에 가능하다. 코드 ( C ++ ) #include #include using namespace std;int N;const int MAX = 1000;int arr[MAX]; ..
-
소풍알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 26. 03:33
문제 : https://algospot.com/judge/problem/read/PICNIC 문제안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.(태연,제시카) (써니,티파니) (효연,유리)(태연,제시카) ..
-
합친 LIS알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 25. 17:57
문제 : https://algospot.com/judge/problem/read/JLIS 문제어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다.두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '1 3 4 7 ..
-
백준(BOJ) 2252번 줄 세우기알고리즘 풀이/백준(Boj) 2019. 7. 25. 02:27
문제 : https://www.acmicpc.net/problem/2252 문제N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 나의풀이 : DFS를 이용한 위상 정렬로 문제를 풀어 보았다. 1~N까지 dfs가 종료하는 순서를 기록한 뒤 이 순서를 뒤집는다. 그래프에 사이클이 없다면 이 순서는 그래프의 위상 정렬 결과가될 것. 코드 ( C ++ ) #include #include #include #include u..
-
백준(BOJ) 10816번 숫자 카드 2알고리즘 풀이/백준(Boj) 2019. 7. 23. 14:40
문제 : https://www.acmicpc.net/problem/10816 문제숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 나의풀이 : 가지고 있는 카드를 이진탐색을 통한 upper_bound 와 lower_bound를 이용하기 위해 오름차순 정렬해준다.그 후 upper_bound에서 num에 lower_bound로 찾은 값을 빼주면 그 개수를 구할 수 있다. #include #include #include using namespace std; int main(){ios_base::sync_with_stdio(0);cin.tie(0);int ..
-
백준(BOJ) 2805번 나무 자르기알고리즘 풀이/백준(Boj) 2019. 7. 22. 16:22
문제 : https://www.acmicpc.net/problem/2805 문제상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. ..
-
백준(BOJ) 1931번 회의실배정알고리즘 풀이/백준(Boj) 2019. 7. 19. 01:19
문제 : https://www.acmicpc.net/problem/1931 문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 풀이:회의가 끝나는 시간으로 오름차순으로 정렬한다. 정렬된 배열의 첫 번째 회의는 무조건 선택한다. 그 후 겹치는 회의를지울 필요 없이 정렬된 배열을 순회하면서 첫 번째 회의..