C++
-
백준(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이라고 하자. ..
-
백준(BOJ) 1931번 회의실배정알고리즘 풀이/백준(Boj) 2019. 7. 19. 01:19
문제 : https://www.acmicpc.net/problem/1931 문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 풀이:회의가 끝나는 시간으로 오름차순으로 정렬한다. 정렬된 배열의 첫 번째 회의는 무조건 선택한다. 그 후 겹치는 회의를지울 필요 없이 정렬된 배열을 순회하면서 첫 번째 회의..
-
백준(BOJ) 1699번 제곱수의 합알고리즘 풀이/백준(Boj) 2019. 7. 18. 13:44
문제: https://www.acmicpc.net/problem/1699 문제어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 나의 풀이: 어떤 한 수를 제곱수의 합으로 나타낸다면 그 수의 ..
-
숫자 게임알고리즘 풀이/알고리즘 해결전략 연습 2019. 7. 17. 06:13
문제 : https://algospot.com/judge/problem/read/NUMBERGAME 문제n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다.게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다.게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지웁니다.게임은 모든 숫자가 다 없어졌을 때 끝나며, 각 사람의 점수는 자신이 가져간 숫자들의 합입니다. 현우와 서하는 점수가 더 낮은 쪽이 점수 높은 쪽에 한 점 차이마다 백 원씩 주기로 내기를 했습니다. 두..
-
백준(BOJ) 2156번 포도주 시식알고리즘 풀이/백준(Boj) 2019. 7. 16. 15:07
문제 : https://www.acmicpc.net/problem/2156 문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양..