전체 글

[정올] 도서관

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1508&sca=3020 JUNGOL www.jungol.co.kr 그리디로 해결할 수 있습니다. 우선 문제부터 간단하게 요약하면, 도서관에 학생들이 오는 시간과 가는시간이 주어집니다. 이 때, 한 명 이상의 학생이 머물렀던 가장 긴 시간과, 학생이 한 명도 머물지 않았던 가장 긴 시간을 공백으로 구분하여 출력해야 합니다. 그리디를 사용하기 위해서 시작시간을 기준으로 정렬합니다. 그리고 나서 순서대로 보면서 이전 학생과 비교해봅니다. 만약 이전 학생이 떠나는 시간보다 다음 학생의 도착 시간이 빠르다면, 구간이 이어집니다. 구간의 끝값을 다시 계산해 주어야 하는데, 시작시간이 느려도 이전 학생이 더 늦..

[정올] 냉장고

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3050 JUNGOL www.jungol.co.kr 그리디 알고리즘을 사용하는 문제입니다. 문제부터 간단하게 요약하면, 화학 물질들은 각각 보관 온도 범위를 가집니다. 이 때, 냉장고들은 각각 하나의 온도만을 유지할 수 있습니다. 이 때, 화학 물질들을 모두 보관하기 위한 냉장고의 최소 갯수를 구해야 합니다. 그리디 알고리즘을 사용해야 합니다. 그리디 알고리즘도 정렬을 해야 합니다. y 즉 화학물질 보관의 최대 온도 기준으로 정렬을 시킵니다. 그리고 간단한 예시를 봅시다. 4 -15 5 -10 36 10 73 27 44 정렬을 시키면 위와 같은 상황이 됩니다. 왜 뒤의 온도로 정렬하면 그리디..

[백준] 크게 만들기

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net stack을 이용하는 문제입니다. 문제부터 간단하게 요약하면, N자리 숫자가 주어지는데, 이 숫자중에서 K개를 지워서 만들 수 있는 가장 큰 수를 출력해야 하는 문제입니다. 간단하게 예시를 통해 알고리즘을 생각해보면, 1924를 보면 stack에 하나씩 넣는데, 1보다 큰 9가 들어오면, 1을 pop시키는 형태로 구현을 하면 된다는 생각이 듭니다. 조금 더 디테일 하게는 더 큰 숫자를 집어넣기 전에 stack을 pop하는데, pop은 그 숫자보다 작은 애들을 모두 pop해주..

[백준] 좋은 친구

https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 슬라이딩 윈도우를 이용하는 문제입니다. 문제부터 간단하게 요약하면, 성적 순으로 학생들의 이름이 주어지면, 좋은 친구의 쌍 수를 구해야 하는 문제입니다. 여기에서 좋은 친구라는 것은 등수 차이가 K를 넘지 않고, 이름의 길이가 같아야 합니다. 이름 길이가 2글자에서 20글자 사이이기 때문에, 이름 길이를 이용한 array를 만들어 두고, window를 움직이면서 계산을 해주면 ..

[백준] 용돈 관리

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이진탐색을 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 현우가 용돈을 사용하는데 계획적으로 사용합니다. 그래서, N일 동안의 지출 계획이 있고, 정확하게 M번만 K원씩 인출하여 사용하려 합니다. 이 때, K의 최솟값을 구해야 합니다. 문제를 한번 읽어보는 것을 추천합니다. 통장에서 인출해야 하는 금액 K는 N일간의 지출 계획중 가장 큰 값 보다는 크거나 같아야 하고, N일간의 지출을 모두 더..

[백준] 표절

https://www.acmicpc.net/problem/2428 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 이진탐색을 이용하는 문제입니다. 문제부터 간단하게 요약하면, 파일의 유사도 검사를 해야하는데, 검사할 파일이 너무 많기에 각각의 두 파일을 모두 검사를 하게 되면, 너무 오래걸립니다. 그래서 두 파일이 있을 때, 두 파일의 크기가 [작은파일의 크기 >= 0.9*큰파일의 크기] 인 쌍들에 대해서만 검시를 하려 한다고 합니다. 이 때..

[백준] Social Distancing

https://www.acmicpc.net/problem/18877 18877번: Social Distancing The first line of input contains $N$ and $M$. The next $M$ lines each describe an interval in terms of two integers $a$ and $b$, where $0 \leq a \leq b \leq 10^{18}$. No two intervals overlap or touch at their endpoints. A cow standing on the endpoint of a www.acmicpc.net 이분탐색을 이용하는 문제입니다. 문제부터 간단하게 요약하면, 잔디의 구간들이 M개 있는데, 이 구간에 N마리의..

[백준] 폭탄제조

https://www.acmicpc.net/problem/2977 2977번: 폭탄제조 효진이는 돈이 매우 많은 대학생이다. 어느 날, 효진이가 열심히 공부한 과목의 교수가 F학점을 주겠다고 '농담'을 했다. 하지만 효진이는 화가 나서 폭탄을 마구 만들어내 효진이가 소유한 개인 www.acmicpc.net binary search를 이용하는 문제입니다. 우선 문제부터 간단하게 요약하면, 1개의 폭탄을 만들기 위해선, N개의 부품 종류가 필요합니다. N개의 줄에 각 줄마다 각각 폭탄 1개에 필요한 부품의 수, 이미 있는 부품의 수, 소형 패키지의 부품수, 소형 패키지의 가격, 대형 패키지에 있는 부품수, 대형 패키지의 가격이 주어질 때, M달러를 이용하여 폭탄을 최대한 만든다면, 몇개 만들수 있는지 구해야..