본문 바로가기

알고리즘53

[백준 11728] 배열 합치기 배열을 합치는 데, 병합정렬(Merge Sort)를 사용하였다.별로 어렵지 않은 문제였다. 문제: https://www.acmicpc.net/problem/11728 문제 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다. 출력 첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다. 예제 입력 1 2 2 3 5 2 9 예제 출력 1 2 3 5 예제 입력 2 2 1 4 7 1 예제 출력 2 1 4 7 예제 입력.. 2019. 3. 17.
[백준 1722] 순열의 순서 문제 : https://www.acmicpc.net/problem/1722 문제를 처음에 보고 너무 쉽게 생각했는지, 직접 구현한 배열의 next_permutation을 사용했다.하지만, 시간초과... next_permutation으로 문제를 풀면 Big-O 표기로 O(N!)이 나오기 때문이였다. 항상 분발하는 자세로 겸손히 공부해야겠다. ㅠㅠ 실패한 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include#include using namespace std; bool next_permutat.. 2019. 3. 17.
[백준 11723] 집합 다른 방법을 사용하여 충분히 풀 수 있지만, 비트마스크를 사용하여 풀 수 있습니다. 비트마스크란? 참고하면 좋은 글 : https://redcoder.tistory.com/11 출처 : https://www.acmicpc.net/problem/11723 문제 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.check x: S에 x가 있으면 1을, 없으면 0을 출력한다.toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)al.. 2019. 3. 16.
[백준 10974] 전체 수열 STL을 사용하지 않고 푸는 것이 목적이였기 때문에, 직접 next_premutation을 구현하였다.생각보다 까다로운 것, 다음에 기억할 수 있을까? 출처 : https://www.acmicpc.net/problem/10974 문제 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 출력 첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.예제 입력 1 3 예제 출력 1 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 1234567891011121314151617181920212223242526272829303132333435363738394041#include using .. 2019. 3. 16.
[백준 10972] 다음 수열 사실 STL을 사용하면 매우 쉽게 풀 수 있는 문제이지만, 직접 구현을 하거나 STL에 구현이 되어 있다는 것을 모르면, 귀찮아지는 문제이다.배열의 인덱스 가지고 재미있게 코딩할 수 있다는 점이 상당히 놀랍다.참고하면 좋은 글 : https://redcoder.tistory.com/7 출처: https://www.acmicpc.net/problem/10972 문제1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.1, 2, 31, 3, 22, 1, 32, 3, 13, .. 2019. 3. 16.

티스토리툴바