본문 바로가기

알고리즘 문제풀이200

[백준 11931] 알고리즘 67일차 : 수 정렬하기4 www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 정렬 C++ 아 무엇. 입력에 중복 없는거 지금봄. 일단 내림차순 정렬 문제고 변명시작. 오늘 정말 상당한 투두를 소화해냈거든요. 그래서 사실 문제풀이는 3/4쯤 포기 했었어요. 하지만 어쩌다보니 시간이 돼서 풀었어요. 하지만 그게 마음대로 되나요 문제 한 4개정도 간보다가 문제 랭크 실버 이상 풀어야해서 실버 5정도만 골라보다가 진짜 안되겠다 싶어서 정렬을 풀기로 했습니다.. 양아치같은 문제 .. 2021. 1. 18.
[백준 2776] 알고리즘 66일차 : 암기왕 www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net C++ 이분탐색 두개의 정수배열이 있고 하나의 배열에서 다른 하나의 배열의 수를 찾는 간단한 문제다. 이번엔 최대값 혹은 최솟값구하는 문제도 아니고 그냥 이분탐색이다. 오히려 이런게 오랜만.. 처음에 시간초과 걸렸었는데 ios::sync_with_stdio(false); cin.tie(0); 쓰고 통과 소스코드 #include #include using namespace std; int T,N,M; int note1.. 2021. 1. 15.
[백준 2343] 알고리즘 65일차 : 기타 레슨 www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 이분탐색 C++ 음 메모리 파티션을 나눈다고 생각하면 이해가 쉬울 것 같다. N개의 레슨 영상의 시간이 주어지고 이걸 용량이 동일한 M개의 usb에 담아야할때 usb용량의 최소크기를 구하는 것이다. (내맘대로 문제 변경) 접근방법 우선 이분탐색이기 때문에 범위만 산정되고 기준을 정하는 함수만 설계하면 끝난다. 범위는 레슨 길이 중 최댓값 ~ 모든 레슨 길이의 합이다. *처음 제출할때 이분 탐색 start 값을 1로 설.. 2021. 1. 14.
[백준 1072] 알고리즘 64일차 : 게임 www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net C++ 이분탐색 (12분전) 앞으로 하는 게임은 모두 이긴다는 가정에서 최소 몇판을 더해야 승률이 변하는지 구하는 문제 99%일때와 100%일때는 아무리 게임을 더해도 승률이 절대 변하지 않는다 (-1출력) X의 최댓값이 1000000000이라 추가로 더 하는 게임 횟수의 최댓값도 1000000000이다. 이분탐색의 범위는 1,1000000000 Z(승률) 구하는 식을 그대로 쓰면 50 29 일때 값이 틀리게 나온다 그래서 Y*100/X로 구해야하는데 Y/X를 .. 2021. 1. 13.
[백준 1789] 알고리즘 63일차 : 수들의 합 www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net C++ 이분탐색.. 16분전. 시간에 쫓기고 있습니다. 이분탐색인데 이분탐색으로 안해도 풀리네요. 문제 한문장 대로 서로다른 N개의 자연수의 합이 S가 될때 N의 최댓값을 구하는 문제 접근방법 합이 S가 되는 수들의 개수가 최대가 되려면 적은 수부터 연속된 수를 더하는 경우가 가장 최대가 되겠죠. 그래서 우리가 알고 있는 공식 1부터 N까지 연속된 수의 합을 구하는 공식인 N(N+1)/2 을 활용하면 됩니다. 이 N에 들어가는 수를 이분탐색으로 탐색하면 시간이 더 적게 들겠지만 1부터 차례로 대입해가면서 공식의 값이 S를 넘을때.. 2021. 1. 12.
[백준 11659] 알고리즘 62일차 : 구간 합 구하기4 www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net C++ 누적합 문제 처음 보면 엥 이게 왜 실버3이지 싶은데 풀고나면 아ㅇㅇ 그냥 수배열 주고 일정 구간 수의 합 구하는건데 시간복잡도 때문에 그냥 합하는 식으로 구하면 시간초과나고 누적합.. 아 이 문제 분류가 누적합이구나.. 입력받을때 누적합을 같이 구해서 구간 합 구할때는 sum[end] - sum[start] (단, start != 1) 로 구해야 함 근데도 시간초과 나서 sync.. 2021. 1. 11.
[백준 2512] 알고리즘 61일차 : 예산 www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net C++ 이분탐색 연초에 시기적절한 문제인 것 같아서 풀어봤다(변명) 이분탐색은 진짜 한번 풀면 계속 풀 수 있을 것 같다(그러면서 왜 골드는 안푸는데요) 아무튼. 접근방법 지방의 예산요청액 입력받을때 합이랑 최댓값 같이 구해놓고 합이 전체 국가 예산보다 작으면 최댓값 출력하고 끝. 아니면 이분탐색 함수 부를때 (1,최댓값)으로 범위설정해서 보내고 이분탐색 기준 함수는 지방 예산요청액 배열 다 돌면서 상한액.. 2021. 1. 8.
[백준 1764] 알고리즘 60일차 : 듣보잡 www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net C++ 이분탐색 모닝 코딩이네요 또 쉽게가려고 이분탐색 들여다보고있는데 제목이 재밌어서요..(핑계) 근데 문제가 더 재밌네요 듣도 못한 사람과 보도 못한 사람들이 주어지고 듣도 보도 못한 사람을 구하는거라니..ㅋㅋ 문자열 벡터 이분탐색 정렬 썼습니다. 접근방법 듣도 못한 사람 명단 벡터에 저장 후 사전순으로 정렬 보도 못한 사람을 듣도 못한 사람들에서 이분탐색으로 찾고 듣도보도못한 사람 명단에 push 듣도보.. 2021. 1. 7.
[백준 10815] 알고리즘 59일차 : 숫자 카드 www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net C++ 이분탐색 쉬운 이분탐색 응용없이 그냥 이분탐색만 하면 되는 문제 이건..실버4이기엔 쉬운 문제인 것 같다. 접근방법 상근이가 갖고 있는 숫자카드는 배열로 받아서 정렬해주고 주어지는 정수 M은 바로 받아서 이분탐색하는 것 끝 오답노트 내가 코드를 잘 못짜서 그런건지는 모르겠지만 일단 기본 코드는 시간초과 났었고 sync_with_stdio 해주고 cin tie해주니까 통과됐다.. 2021. 1. 6.

티스토리툴바