개발자 퉁이리

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 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 매개 변수 탐색 ⊙ 문제 접근 과정 우선 문제를 보고, 무지성으로 N에 3을 넣은 2차원 배열 A를 만들어줬다. 그리고 바로 i와 j를 곱한 값을 A[i][j]에 넣어 2차원 배열 A를 완성시켰다. 2차원 배열 A의 값들을 1차원 배열 B에 넣고 정렬하여 B[k-1]를 출력해주었다. 그랬더니 출력..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 정렬 이분 탐색 두 포인터 ⊙ 문제 접근 과정 투 포인터 알고리즘을 사용해 풀었다. 초기 비교 값을 한계치보다 훨씬 높게 설정해주고 비교하면서 더 작은 값을 결괏값에 넣어주면서 포인터를 이동시켜갔다. 마지막에는 두 값을 출력해주면 끝!! 코드를 보면 쉽게 이해가 될 것 같다!! 이해가 안 되시는 분은 댓..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 두 포인터 ⊙ 문제 접근 과정 반복문을 2중 이상으로 사용하면 시간 초과가 뜬다. 하나만을 이용해 풀어야한다. 그 방법 중 하나로 투 포인터 알고리즘이 있다. 투 포인터 start, end -> index값 생성 index를 이용해 절댓값을 사용해준다. 반복 ⊙ 문제 풀이 #include #include #include ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 매개 변수 탐색 ⊙ 문제 접근 과정 이분 탐색 알고리즘으로 풀었다. 코드를 짜는 데는 시간이 얼마 걸리지 않았지만 여러 자잘한 애러를 잡아내는데 시간이 더 소요된 문제다. 시간 복잡도는 O(N^2)이다. 더 줄이고 싶었지만 아이디어가 생각이 안 났다. max_element를 사용했기 때문에 0을 입..

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 가장 긴 증가하는 부분 수열: O(n log n) ⊙ 문제 접근 과정 https://tooo1.tistory.com/131 코드와 문제 접근 과정 동일 ⊙ 문제 풀이 #include #include #include using namespace std; int a; vector arr; int ma..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 가장 긴 증가하는 부분 수열: O(n log n) ⊙ 문제 접근 과정 LIS 문제이다. 시간 복잡도 O(N log N)으로 풀었다. LIS가 무엇인지, O(N^2)의 풀이법을 보고 싶다면 tooo1.tistory.com/121 크기 값을 입력 받는다. 벡터 값을 입력받는데 조건문을 활용하여 입력받는다. O(N log N)으로 풀 수 있게 한..

www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 ⊙ 문제 접근 과정 내가 생각하는 이진 탐색에서 가장 중요한 포인트는 기준이다. index로 기준 잡고 탐색할지, value를 기준으로 탐색할지 문제를 본 뒤 결정해야 한다. 이번 문제는 value를 기준으로 이진 탐색을 해야 한다. 기준을 잡았으면 시작 값과 끝 값을 정해주는 것도 굉장히 중요하다. 이 문제에서 시작 값은 0, 끝 값..

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 이분 탐색 매개 변수 탐색 ⊙ 문제 접근 과정 문제 요약: 공유기를 설치할 건데 가능한 멀리 설치하고 싶다. (같은 좌표는 없다) 여러 풀이방법이 있지만 이진 탐색 알고리즘을 사용하여 문제에 접근했다. 이진 탐색을 이용하여 문제를 풀 때 index가 아닌 거리로 두고 풀어야 한다. (거리기준) n(집..

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 자료 구조 이분 탐색 해시를 사용한 집합과 맵 ⊙ 문제 접근 과정 vector를 활용해 값을 입력받고 제일 먼저 해야 할 건 정렬이다. sort로 정렬을 해주고 algoritm 헤더에 있는 Lower bound와 Upper bound 알고리즘을 사용하면 된다. 참고로 sort도 algoritm 헤더에 있다. 그냥 제출..

www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 정렬 이분 탐색 ⊙ 문제 접근 과정 코드는 tooo1.tistory.com/122과 거의 똑같다. [백준(BOJ)] 1920번 : 수 찾기 - C++[CPP] www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 ..