Algorithm/Binary Search
-
백준 2352 - 반도체 설계Algorithm/Binary Search 2024. 2. 29. 09:24
2352번: 반도체 설계 (acmicpc.net) 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 문제의 핵심은 꼬이는 경우 없이 제일 긴 리스트를 만들어내는 것이다. 제일 긴 리스트를 만들어야 한다는 것에서 '긴 부분 증가수열'을 만들어야하는 것을 알 수 있다. 그렇다면 긴 부분 증가수열(LIS)는 무엇일까? 긴 부분 증가 수열이란? 예를 들어, 10 20 10 30 40 20 으로 수열이 나열되어 있다고 하면, 긴 부분 증가수열은 10 20 30 40이 되고 길이는 4가 된다. 이러한 ..
-
유형정리(이분탐색) - 백준 2805Algorithm/Binary Search 2023. 4. 4. 13:38
2805번: 나무 자르기 (acmicpc.net) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 ..
-
유형정리(이분탐색) - 백준 19637Algorithm/Binary Search 2023. 4. 3. 16:17
19637번: IF문 좀 대신 써줘 (acmicpc.net) 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 문제 게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다. 예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 ..
-
유형정리(이분탐색) - 백준 2417Algorithm/Binary Search 2023. 4. 2. 19:21
2417번: 정수 제곱근 (acmicpc.net) 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 n이 주어진다. (0 ≤ n < 263) 출력 첫째 줄에 q^2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력한다. 예제 입력 1 복사 122333444455555 예제 출력 1 복사 11060446 문제를 안보고 선택을 했는데, 막상 문제를 보니 너무 간단하다. 문제 설명은 딱히 할 게 없어서 바로 풀이로 들어가겠다. ※ 알고리즘 1. n을 입력받는다. 2. 처음 값을 0, 마지막 값을 n으로 초기화한다. 3. 이분탐색 알고리즘을 작..
-
유형정리(이분탐색) - 백준 10815Algorithm/Binary Search 2023. 4. 1. 20:13
10815번: 숫자 카드 (acmicpc.net) 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있..
-
유형정리(이분탐색) - 백준 1789Algorithm/Binary Search 2023. 4. 1. 19:22
1789번: 수들의 합 (acmicpc.net) 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 예제 입력 1 복사 200 예제 출력 1 복사 19 문제는 위와 같이 굉장히 간단하다. N개를 무한 루프 속에서 계속해서 더해가다가 지정된 S를 넘는 경우 멈춰주면 된다. 이 때 조심할 점이 S>N이 되는 마지막 지점에서 해당 값이 루프에서 나온 값에 포함되어 있으므로 마지막에 print에서 -1을 시켜주어야..