728x90 이분탐색 썸네일형 리스트형 [백준알고리즘] 2631번: 줄세우기 -Python [백준알고리즘] 2631번: 줄 세우기 -Python https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 www.acmicpc.net LIS문제이다. 세워져있는 상태에서 정상적으로 줄 서있는 학생들의 수를 구해서 전체 .. 더보기 [백준알고리즘] 3020번: 개똥벌레 -Python [백준알고리즘] 3020번: 개똥벌레 -Python https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 문제 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다. 아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림) 이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 모든 장애물을 파괴한다. 위의 그림에서 4번째 구간으로 개똥벌레 www.acmicpc.net @Crocus 님의 블로그의 글을 참고했다. https://www.crocus.co... 더보기 [백준알고리즘] 1072번: 게임 -Python [백준알고리즘] 1072번: 게임 -Python https://www.acmicpc.net/problem/1072 1072번: 게임 각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다. www.acmicpc.net 이분 탐색 문제이다. 주의해야 할 점은 입력이 한 줄만 주어지는 게 아니다. 입력에 각 줄에 대하여 X와 Y가 정해져 있다 했고, 한 줄만 입력된다는 언급이 없었다. 이 부분 때문에 고생했다.. 그리고 하나 더 주의해야 할 점은 메모리에 대한 것이다. X, Y의 범위가 굉장히 넓기 때문에 연산 과정 중에서 문제가 일어나기 쉽다. 계속 실패했던 부분이 코드 부분에 있는 'y*100/x' 부분이다. 이 .. 더보기 [백준알고리즘] 1300번: K번째 수 -Python [백준알고리즘] 1300번: K번째 수 -Python https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. www.acmicpc.net 너무 어려웠다.... 아이디어가 도무지 기억이 안 나서 알고리즘 분류를 봤는데도 도저히 이분 탐색으로 할 수 있는 방법이 생각나지 않았다. 생각한 방법은 너무 시간이 오래 걸리는 것뿐이었다. 그래서 결국 여러 블로그들을 찾아봤다. 다 같은 내용인데 다 이해가 안돼서 아래의 블로그를 집중.. 더보기 [백준알고리즘] 2352번: 반도체 설계 -Python [백준알고리즘] 2352번: 반도체 설계 -Python https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 언뜻 봐서는 O(N^2)의 방식의 풀이도 통과할 줄 알았는데 시간 초과가 발생했다. 이 문제는 LIS문제이다. 가장 긴 증가하는 부분 수열을 만들어야 한다. 여기서는 직접 부분 수열을 출력하는 것이 아닌 길이만 출력하면 되기 때문에 간단한 lower .. 더보기 [백준알고리즘] 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문에서 세그먼트 트리나 이진 탐색으로 .. 더보기 이전 1 2 다음