목록이분 탐색 (6)
전자공학 및 알고리즘
백준 1849 - 순열(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1849 이분 탐색을 이용한 세그먼트 트리 문제입니다. 자세한 것은 코드를 참고해주세요.#define _CRT_SECURE_NO_WARNINGS#include #include #include #include #include #include #include using namespace std;int N;int Tree[100001 * 4];int remake[100001 * 4];int Rank[100001 * 4];int ans[100001 * 4];void make_tree(int node, int st, int fin){ if(st == fin) { Tree[node] = 1; return; } int left = nod..
백준 2465 - 줄 세우기(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2465 세그먼트 트리를 이용한 문제입니다. 수열이 하나 주어지고, 해당 수열에서의 키 순서가 주어질 때, 키 순서에 맞는 수열을 찾는 문제입니다. 먼저, 자신보다 키가 작거나 같은 학생을 알기 위해서 오름차순 정렬을 해줍니다. 오름차순 정렬을 해줬으면, 자신이 어디에 들어가야 할지를 뒤에서부터 확인을 해줍니다.(키 순서가 0 1 0 0 3 2 6 7 4 6 9 4 이니 4에서부터 채워줍니다.) 뒤에서 부터 채우는 이유는 앞에서 부터 채울 경우 0을 채워야 하는데, 해당 값이 정확하지 않기 때문입니다.반대로 뒤에서 부터 채울 경우, 값이 0이 아닌 것부터 채우기 때문에 어떤 값을 먼저 채워야할지 명확해지기 때문입니다. 어떤 값이 ..
백준 1450 - 냅색 문제(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net '중간에서 만나기' 를 사용하는 문제입니다. 가방에 물건을 C이하만큼 넣을 수 있습니다. 하나의 물건에서 할 수 있는 경우는 선택O / 선택X인 2가지입니다. 물건이 총 30개까지 주어지니, 전체의 경우는 2^30입니다. -> 시간초과가 생깁니다. 따라서, 문제를 풀기 위해선 '중간에서 만나기'를 사용해야합니다. 중간에서 만나기란, 전체 경우를 2가지로 나눠서 생각하는 것입니다...
백준 10816 - 숫자 카드2(C++)
문제 링크입니다. https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 간단한 이분 탐색 문제였습니다. 이분 탐색을 통해 해당 숫자가 있는지는 찾은 후, 해당 숫자가 존재한다면 똑같은 카드가 몇개인지를 찾는 문제입니다. 존재하는 것은 찾은뒤 -> for문을 통해서 몇개가 있는지 -> 시간초과가 됩니다. 따라서 중복되는 숫자가 몇개가 있는지를 이분 탐색 전에 확인해야합니다. 저는 배열 크기를 10,000,000 + 1..
백준 2842 - 집배원 한상덕(C++)
문제 링크입니다. https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net BFS와 이분 탐색을 사용해야하는 문제였습니다. N*N 배열에서 모든 편지를 전달하고 돌아올 때, 최소 피로도를 구하는 문제였습니다. 저는 N*N 배열의 값을 백터를 통해서 저장하고 정렬한 후 중복된 값을 전부 없앤 뒤, 범위를 (0 ~ 1), (0 ~ 2) 등으로 늘려가면서 이동할 수 있는 경로가 있는지를 확인했습니다. 출력 예시 - 예제 입력 3을 통해서 설..
백준 1981 - 배열에서 이동(C++)
문제 링크입니다. https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net BFS와 이분 탐색을 해야하는 문제였습니다. N*N 배열에서 (1,1) -> (N,N) 까지 도착하는데 경로 값의 최댓값과 최솟값의 차이의 최솟값을 구하는 문제입니다. 저는 N*N 배열의 값을 모두 저장한 뒤, 중복값을 없앴습니다. 그 뒤에 (0~0) -> (0~1)등으로 값을 늘려가면서 해당 범위에 있는 경로만을 통해서 갈 수 있게 만들었습니다. 문제의 ..