백준
-
백준(BOJ) 11051번 이항 계수 2알고리즘 풀이/백준(Boj) 2019. 7. 30. 01:27
문제 : https://www.acmicpc.net/problem/11051 문제자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 나의 풀이: 이항계수(N, K) 를 구하는 방법은 (N-1, K-1) + (N-1, K) 이고 재귀적으로 호출해주면 된다. 하지만 N이 1000이기에 시간내에 풀기에는 불가능하다. ex ) 이항계수(5, 2)를 예로 이항계수(4,1) 부터 쭉 재귀적으로 내려가서 답을 구한 다고 가정하면 또 (4,2)를 구할 때에도 (3,1), (2,1) 등 구한 값을 다시 구해야 한다. 따라서 중복이 되는 경우는 메모이제이션을 통하여 중복을 제거 해주어야 한다. 코드 ( C++ ) #include #include using n..
-
백준(BOJ) 1507번 궁금한 민호알고리즘 풀이/백준(Boj) 2019. 7. 29. 17:12
문제 : https://www.acmicpc.net/problem/1507 문제강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다. 하지만, 이 도로의 개수는 최솟값이 아니다...
-
백준(BOJ) 2884번 알람 시계알고리즘 풀이/백준(Boj) 2019. 7. 29. 03:11
문제 : https://www.acmicpc.net/problem/2884 문제상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다.상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다.이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다.바로 "45분 일찍 알람 맞추기"이다.이 방법은 단순하다. 원래 맞춰져있는 알람을 45분 앞서는 시간으로 바꾸는 것이다. 어차피 알람 소리를 들으면, 알람을 끄고 조금 더 잘 것이기 때문이다. 이 방법을 사용하면, 매일 아침 더 잤다는 기분을 느낄 수 있고, 학교도 지각하지 않게 된다.현재 상근이가 맞춰논 알람 시..
-
백준(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]; ..
-
백준(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이라고 하자. ..