BOJ 백준/기타 검색 결과

해당 글 22건

백준 02751 - 수 정렬하기 2

출처 : https://www.acmicpc.net/problem/ 고려사항 nlogn 만큼의 시간 복잡도를 지닌 퀵정렬, 병합정렬, 힙정렬을 구현해 보았다. 퀵정렬은 피봇을 무엇으로 정하는지에 따라 소요 시간이 차이가 난다 이 문제는 퀵정렬로 구현시 시간초과로 실패한다...하지만 알고리즘이 틀린 것은 아니며 많은 사람들에 의해 저격? 테스트 케이스( 오름차순, 내림차순으로 정렬되어 있는 수열 ) 가 있으므로 웬만하면 퀵정렬은 쓰지말라고 한다.. 힙정렬은 heapify() 함수를 n / 2 서 부터 호출하도록 하자! #include using namespace std; int n; int outPlace[1000001]; // ============== quick sort start ===========..
BOJ 백준/기타 2020. 11. 20. 19:09

백준 02750 - 수 정렬하기

출처 : https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 고려사항 n^2 의 시간 복잡도를 지닌 기본적인 버블, 선택, 삽입 정렬을 구현해보았다. 같은 n^2 임에도, 다른 특징들을 가진다. 버블정렬을 기준으로 선택 정렬은 swap 연산이 더 적고, 삽입 정렬은 일반적으로 더 빠르게 여겨지며, 최선의 경우 n 시간 복잡도를 지닌다. 버블, 삽입은 stable sort 이며, 선택 정렬은 unstable sort 이다. stable sort 는 같은 ..
BOJ 백준/기타 2020. 11. 18. 21:25

백준 01920 - 수 찾기

출처 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안 www.acmicpc.net 고려사항 이분 탐색. 모든 수를 벡터에 담아서 알고리즘 헤더에 있는 sort 함수를 사용한다. sort 함수가 퀵소트 기반으로 구현되어 있으니 정렬이 빠르게 된다! 수가 있는지를 판별할 때에는 정렬된 벡터에서 이분탐색을 실시! #include #include #include using namespace std; int search(vector &v..
BOJ 백준/기타 2020. 11. 17. 17:57

백준 15654 - N과 M (5)

출처 : https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 고려사항 next_permutation 을 활용하여 수열 구하기. 첫 next_permutation 반복문에서는 뽑을 수들을 정하고, 이들을 벡터에 담아 수열들을 구하여 정답 벡터에 삽입. 정렬하여 출력. #include #include #include using namespace std; bool cmp(int a, int b){ return a > b; } int main()..
BOJ 백준/기타 2020. 11. 16. 17:16

백준 07662 - 이중 우선순위 큐

출처 : https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 고려사항 map 활용. map은 key를 기준으로 정렬을 해준다. insert 시에 map에 존재하지 않으면 (num, 1)로 삽입, 이미 존재하면 m[num] 의 value 를 +1 해준다. delete 는 map의 사이즈가 0이 아닐 시에만 연산을 진행하고, 연산이 -1 이면, m.begin() 의 value를, 연산이 1 이면, --m.end() 의 value를 확인해보고, 1이..
BOJ 백준/기타 2020. 11. 12. 12:54

백준 02749 - 피보나치 수 3

출처 : https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 고려사항 피보나치를 푸는 대표적인 dp를 활용한 방법 외에도 여러가지를 알게 되었다. 1) 행렬이용 ( 11444번 ) 2) 피사노 주기 ( 위 문제 ) 3) 일반항 이용 ( 아직 안 풀어봄... ) n번째 피보나치 수를 구하는 문제는 일반적으로 n이 48만 넘어가도, INT_MAX를 넘어가는 큰 수이기 때문에 특정한 수 x로 나눈 나머지를 구하라라는 문제로 연결된다. 이 때, x의 나머지 연산은 피보나치 수열이 특정 주기별로 반복되어 나타나도록 하는데, 이를 피사노 ..
BOJ 백준/기타 2020. 11. 11. 14:15

백준 12015 - 가장 긴 증가하는 부분 수열 2

출처 : 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 고려사항 dp를 활용한 lis 알고리즘을 사용하면 정답은 구할 수 있다. ( 백준 11053 문제 글 15 - 23 라인 참조) 이러한 2중 for문을 수열의 길이만큼 100만번씩 돌리면 당연히 시간초과. 자신보다 작으면서, 부분 수열의 길이가 제일 긴 memo값을 찾는 for문을 이분탐색 아니면 세그먼트 트리로 구하면 시간단축가능! 그런데 더 간단한 방법을 발견 ( 구글링... ) lo..
BOJ 백준/기타 2020. 11. 10. 18:34

백준 01717 - 집합의 표현

출처 : https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 www.acmicpc.net 고려사항 유니온-파인드 알고리즘(서로소) 사용 부모 정보가 담기는 배열을 n+1개 선언 두 집합을 합칠 때에는 루트 번호가 작은것이 새로운 루트가 되도록 구현 재귀를 활용한 findNum 구현. 집합을 합칠 때마다, 매번 집합 원소들의 부모를 전부 업뎃해줄 수는 없으니, 집합의 루트였던 원소의 부모 정보를 자기 자신에서 새로운 루트로 업데이트 후, 나중에 ..
BOJ 백준/기타 2020. 11. 9. 18:13