알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net N개만큼 문자열이 주어지고 M개만큼 문자열이 주어질 때, M개 문자열에 N개 문자열이 몇개가 들어있는지 구하는 문제입니다. N, M이 최대 10,000이기에 완전 탐색을 했다가 시간초과가 됩니다. 따라서 이분 탐색을 통해 N 속에 M이 들어있는지 확인해줘야 합니다. 자세한 것은 코드를 참고해주세요. #include #include #include ..

문제 링크입니다. https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이분탐색을 활용해야하는 문제였습니다. 두 개의 섬이 주어졌을 때, 옮길 수 있는 중량의 최댓값을 구하는 문제입니다. 저는 이분탐색의 방법으로 풀었는데, low = 0, high = 다리의 최대 중량로 만들어, mid값을 얻은 뒤, mid값보다 큰 값으로만 두 섬을 이동할 수 있냐? -> 해당 과정을 확인했습니다. mid ..

문제 링크입니다. https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net upper, lower_bound를 사용하는 문제였습니다. 배열 A와 B 중, 하나 이상을 선택해 합이 T를 만드는 부분 수열의 갯수를 구하는 문제입니다. N과 M값이 1,000이기에 이중 for문을 통해서 모든 부분 수열의 합을 구합니다. A 부분 수열과 B 부분 수열의 합을 구하는 것이기에, 배열..

문제 링크입니다. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net '중간에서 만나기' 방법을 사용하는 문제입니다. 중간에서 만나기에 대해 잘나와있는 설명입니다. 해당 블로그를 참고해주세요 -> https://restudycafe.tistory.com/523 문제에서 N의 값은 최대 40입니다. 수는 선택하거나 선택하지 않는 2가지 방법이 있습니다. 그렇다면 모든 경우의 수를 확인해보려면 2^40이 나오게 ..

문제 링크입니다. https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투포인터를 이용하는 문제였습니다. https://junseok.tistory.com/314 -> 이 문제에서 조건이 하나 추가된 문제입니다. 두 용액이 아닌, 3개의 용액을 선택해 값이 최소가 되는 것을 구하는 문제입니다. 두용액이였다면, 간단한 투포인터를 이용해 풀 수 있겠지만, 용액이 3개이기에 일반적인 방법으로 풀 수는 없었습니다. 가장 간단하게 생각할..

문제 링크입니다. https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 투 포인터를 이용하는 문제입니다. 두 개의 용액을 선택해서 최대한 0에 가까운 값을 만드는 문제입니다. 백트래킹으로도 풀 수 있겠지만, N값이 100,000이기에 시간초과가 생깁니다. 따라서 이분탐색 중 투 포인터를 통해서 풀어야됨을 알 수 있습니다. 투 포인터는 양 끝의 범위를 잡아놓고, 조건에 따라 범위를 좁혀나가는 것을 의미합니다. 해당 문..

문제 링크 입니다 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net https://junseok.tistory.com/23 이 문제의 심화 문제 입니다. 백준 12015 - 가장 긴 증가하는 부분 수열2(복습) 문제 링크입니다 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다...

문제 링크입니다 https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net https://junseok.tistory.com/73 백준 2353 - 반도체 설계(C++) 문제 링크입니다 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 junseok.tist..

문제 링크입니다 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 선을 꼬이지 않고 연결할 수 있는 최대 갯수를 구하는 방법 위와 같이 연결되어 있다고 했을 때 1. 왼쪽을 기준으로 오름차순 정렬을 한다.(문제에선 이미 되어 있음으로 생략) 2. 오른쪽 수열에서 가장 긴 증가하는 부분 수열을 찾는다. ex) 4 2 6 3 1 5 -> 2 3 5 https://junseok.tistory.com/23 와 비슷한 lower_bou..

문제 링크입니다 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 가장 긴 증가하는 부분 수열 o(n log n) 문제였습니다. 저는 lower_bound를 구현했습니다! 문제 접근 방법 1. 수열을 입력받은 뒤 오름차순으로 정렬한다. 2. vector에 arr[0]의 값을 입력한 뒤, lower_bound를 실행한다. 3. vector의 크기를 출력한다. 4. 1번~3번을 반복한다. 문제 접근 방법 - 2번 void binary_search(..

문제 링크입니다 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 K의 값이 주어졌을때, B[K]의 값을 구하는 문제입니다. N의 값이 최대 10^5이라서 이분 탐색을 하지 않는다면 시간 초과가 나는 문제였습니다. 푸는 방법이 도저히 떠오르지 않아 꾸준함님의 포스팅을 참고했습니다. https://jaimemin.tistory.com/988 백준 1300번 K번째 수 문제 링크입니다: https://www.acmicp..