당신의 이야기에 주목할께요

www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 자료구조 중 하나인 덱을 구현하는 문제이다. 덱 라이브러리를 사용해서 풀어도 되고 직접 풀어도 된다. 나는 라이브러리를 사용했다. 라이브러리를 사용하면 쉽게 풀 수 있다. 더보기 데크는 벡터( vector) 에서 제공하는 많은 기능을 제공해준다. 하지만, 데크의 경우 벡터와는 다르게 양쪽 끝 모두에서 원소의 효율적인 추가와 삭제가 가능하다. 하지만, 벡터와는 달리 데크는 모든 원소가 메모리 상에..

www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제이다. n명 중 k번째 있는 사람을 탈락시키면서 탈락 된 순서대로 큐에 넣는 형태이다. 생각보다 꼬여서 다시 한 번 생각했다. 1) n이랑 k가 같을 때 2) n이 k보다 작을 때 를 고려해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #include using namespace std; vector yp; int cnt[5001]; ..

www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 문자열에 대한 함수를 활용하면 쉽게 풀 수 있다. substr로 시작점을 다르게 해서 문자열 그룹에 넣고 문자열 그룹을 정렬해주면 된다. 전체코드 12345678910111213141516171819202122232425#include#include#include#include#include using namespace std; string s; int main(void){ int len; vector sgroup; cin >> s; len = 0; for(char c : s) len++;..

www.acmicpc.net/problem/10824 10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net 간단하게 stoi 함수를 사용하여 끝내려고 했으나, stoi 함수는 int 형 범위까지만 가능하였다. 이 문제는 자연수 최대값이 1,000,000 이므로 두개를 함치면, 1,000,000,000,000으로 int형 범위를 넘어선다. 그래서 stoi 함수를 직접 구현해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 long long fn_stoi(string ss){ int len; long long num; len = 0; num = 0; for(char c : ss) len++; f..

www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 문자열을 입력받고 알파벳을 13번째 뒤로 미루는 문제입니다. 이 문제에서 중요한 것은 문자열에 빈 칸이 있기 때문에 빈 칸을 무시하는 cin으로 받는 것이 아니라 getline으로 받아줘야 빈 칸까지 입력이 됩니다. seunggi92.tistory.com/55 10820_문자열분석 문자열에 소문자, 대문자, 숫자, 공백의 갯수를 세는 문제입니다. 어렵지 않은 문제이지만, N 갯수만큼 입력을 받는데, N이 주어지지 않아 EOF가 와야 끝낼 수 있도록 해야 하는 것입니다. 저는 get..

문자열에 소문자, 대문자, 숫자, 공백의 갯수를 세는 문제입니다. 어렵지 않은 문제이지만, N 갯수만큼 입력을 받는데, N이 주어지지 않아 EOF가 와야 끝낼 수 있도록 해야 하는 것입니다. 저는 getline을 사용하였습니다. 더보기 getline 함수는 istream 라이브러리와 string 라이브러리에 존재한다. istream 라이브러리는 문자열 끝에 '\0'이 붙는 char *형식 , 즉 C언어 문자열을 따르는 방법이고, string 라이브러리는 c++ 의 string을 따르는 방법이다. 1 2 istream& getline(istream& is, string& str); istream& getline(istream& is, string& str, char delim); cs 인자 is : 입력스..

정렬을 하여 k번째에 뭔가 있는지 찾는 문제이다. 간단할 줄 알았으나, N이 5000000이기 때문에 기존 방법으로는 안되었다. 나는 굳이 기존 방법을 하고 시간 초과를 겪었다. sort에서 에러가 나는가 보다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #include #include using namespace std; int main(void){ int n, k; vector v; cin >> n >> k; for(int i = 0; i > num; v.push_back(num); } stable_sort(v.begin(), v.end()); cout k; for(int i = 0; i > num; v.push_back(num); } ..

www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 정렬하는 문제이다. C++에서 정렬하는 라이브러리는 algorithm을 쓰면된다. C++에서 쓰이는 정렬 알고리즘은 nlogn의 시간복잡도를 가진다고 하였는데, 정확한지는 모르겠다. 여튼 comp함수를 이용해 정렬 함수를 커스텀해 사용하는 연습을 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 bool comp(const P &a,const P &b){ ..

S사 기출 문제이다. 2차원 맵에 value 값이 있으면 그 값을 나머지 맵에 비율에 따라 분배하는 문제이다. 문제를 풀기 위해서는 1) 나선형으로 순회 2) 값 분배 과정이 필요하다. 1) 나선형으로 순회 나같은 경우에는 새로운 시작이 될 때는 무조건 하나씩 왼쪽으로 가서 시작하도록 했다. 그 다음은 (1->1->2->2->2)->(1->3->4->4->4)->(1->5->6->6->6) ... 이 되도록 하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 x = (n - 1) / 2; y = (n - 1) / 2; k = 1; cnt = (n - 1) / 2; while (cnt--) { ////left x -..

3 * n 타일에 2 * 1 타일을 얼만큼 넣을 수 있는지 푸는 문제이다. 짝수 일 때만 만들어지고 끝에 2와 4가 남았을 때 점화식이 만들어지는 것 같아서, `DP[n] = DP[n - 2] * 3 + DP[n - 4] * 2 ` 으로 했는데 원하는 값이 나오지 않았다. 다시 고민하였을 때, `DP[n] = DP[n - 2] * 3 + DP[n - 4] * 2 + DP[n - 6] * 2 + ... DP[0] * 2 + 2 ` 이런식으로 2개씩 계속 추가적으로 생산이 되는 것을 알 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include using namespace std; int main(void) { int n; int dp[31] = { 0..