본문 바로가기

Coding/BaekJoon

B_11478 #include #include using namespace std; int main(void) { string S; set answer; cin >> S; for (int i = 0; i < S.length(); ++i) { string temp = ""; for (int j = i; j < S.length(); ++j) { temp += S[j]; answer.insert(temp); } } cout 더보기
B_1620 #include #include #include #include #include using namespace std; map dictionary; static bool comp(pair &a, pair &b) { return a.second second; } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; for (int i = 1; i > temp; dictionary.insert({temp, i}); } vector dicVec(dictionary.begi.. 더보기
B_7785 set/hash/map set은 연관 컨테이너로, key-value의 구조를 가지는 자료구조이다. 연관 컨테이너는 주로, - 특정 키가 연관 컨테이너에 존재하는지 유무를 알려주는 기능 - 만일 존재한다면, 이에 대응되는 값을 알려주는 기능 이 대표적인데, C++의 경우 위 두 가지 작업을 모두 처리할 수 있는 '연관 컨테이너'를 제공한다. 전자인 존재유무는 Set/Multiset이 이를 담당하며, 후자인 대응 값 탐색은 Map/Multimap이 담당한다. set의 특징은 원소의 추가-삭제 작업의 시간 복잡도가 O(logN)으로 굉장히 빠르다는 점이다. 또한, set은 중복된 원소를 허용하지 않으며, 정렬된 상태를 유지한다는 점이 장점이다. 이러한 특성과 더불어, 자체적으로 'find' 메소드를 제공, 컨.. 더보기
B_10989 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제가 주어졌을 때, 이전 문제(수 정렬하기 2)의 결과가 시간 초과였다. (Sort를 사용해도 괜찮았겠지만, 뭔가 배운 내용을 응용하고 싶었다.) 해서, 자연스럽게 모든 테스트케이스에서 nlogn의 시간을 보장하는 mergeSort를 이용하여 풀고자 했지만 메모리 초과가 나왔다. 합병 정렬의 공간 복잡도는 n이다. 그렇다면 n보다 작은 공간 복잡도를 만든느 방법이 필요하다. [에러가 발생한 C++ 코드] #incl.. 더보기
B_24313 https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net #include #define fn(a1, a0, n) a1 *n + a0 #define gn(n) n using namespace std; int main() { int a1, a0, n, c; cin >> a1 >> a0; cin >> n; cin >> c; if (fn(a1, a0, n) 더보기
B_24267 https://www.acmicpc.net/problem/24267 24267번: 알고리즘 수업 - 알고리즘의 수행 시간 6 오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시 www.acmicpc.net 2가지 방법으로 수행시간을 측정할 수 있다. 1. 수열의 합으로 생각 수열 합 계산을 통해, HTML 삽입 미리보기할 수 없는 소스 의 값을 얻을 수 있다. 이 값을 유심히 살펴본 결과, nC3, n개의 숫자 중 3개를 선택하는 경우의 수와 동일하다. 위 수열의 결과와 조합을 이용한 결과는 다음과 같다. #include using namespace std;.. 더보기
B_10814 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net #include #include #include #include #include #include using namespace std; typedef tuple T; bool cmp(T &v1, T &v2) { if (get(v1) == get(v2)) return get(v1) .. 더보기
B_18870 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net #include #include #include using namespace std; bool cmp(vector &v1, vector &v2) { return v1[1] > N; vector pos; vector pos_compressed; for (int i = 0; i < N;.. 더보기

티스토리툴바