728x90 이분 썸네일형 리스트형 [백준알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 -Python [백준알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 -Python https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 www.acmicpc.net 문제가 굉장히 길다 ㅎㅎ;; 쭉 아래로 내려서.. 더보기 [백준알고리즘] 2512번: 예산 -Python [백준알고리즘] 2512번: 예산 -Python https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. www.acmicpc.net 상한액보다 많은 예산을 요구하면 상한액까지만 지급하고 상한액보다 낮은 예산을 요구하면 모두 지급하면 된다. 이 총액이 주어진 총 예산보다 낮거나 같은 최대의 상한액을 구하면 된다. 이분 탐색으로 풀어주었다. 다양한.. 더보기 [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 1을 풀었던 방식으로는 해결하지 못한다. 수열 A의 원소의 개수도 늘어났고, A를 이루는 원소의 범위도 넓어졌다. O(N^2)의 방법인 이중 for문으로는 시간 안에 통과하지 못한다는 것을 알 수 있다. 질문 게시판에서 이중 for문을 돌릴 때 안쪽 for문에서 세그먼트 트리나 이진 탐색으로 .. 더보기 [백준알고리즘] 1707번: 이분 그래프 -Python [백준알고리즘] 1707번: 이분 그래프 -Python https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어 www.acmicpc.net 20200424 아래에 새로 푼 코드를 첨부했다. 기존의 코드는 객체를 생성하.. 더보기 [백준알고리즘] 2805번: 나무 자르기 -Python [백준알고리즘] 2805번: 나무 자르기 -Python https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 20200418 아래에 새로 푼 코드를 추가했다. 이분 탐색 문제이다. 이전에.. 더보기 이전 1 다음