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

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/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 범위가 -2^62 ~ 2^62 라서 long long을 사용해줬다. n^2으로 하면 터지기 때문에 n으로 해결하기 위해 sort를 먼저해줬다. 제대로 한 것 같은데 이상하게 틀리다고 나왔다. 다른 사람 코드를 참조하여 보니 지역변수가 전역변수로 되니 코드가 잘 돌아갔다. 이유가 무엇일까? 123456789101112131415161718192021222324252627282930313233#include#..

정렬하는 문제이다. 하지만 범위가 N(1 ≤ N ≤ 10,000,000)라 메모리 초과에 조심해야 한다. 그리고 당연히 n^2으로 하면 시간이 터진다. vector와 multiset을 이용해봤는데 메모리 초과가 발생했다. 다른 분들꺼를 참고해보니 배열 인덱스를 사용하면 됬다. 값이 10000을 안넘기 때문에 공간은 10000개로 충분했고, 시간도 n으로 되기 때문에 충분했다. 1234567891011121314151617181920212223242526#include#include#include#includeusing namespace std; int main(void){ cin.tie(NULL); ios::sync_with_stdio(false); int n; int v[10001]; cin >> n;..

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 -..

한참 고민을 하다 점화식을 대충 짤 수 있었다. DP[i][j] = DP[i - 0][j - 1] + DP[i - 1][j - 1] + ... + DP[1][j - 1] + 1 이런 식이 나왔다. 이 문제를 풀기 위해 우선, 이차원 배열에 행과 열 자리에 무엇이 들어가는지 이해해야 한다. 쉽게 말하면, n을 k 갯수만큼의 수를 이용해 만들겠다는 것이다. DP[k만큼의 수를 이용해 만들 수][갯수(k)] 1 2 3 4 for (int i = 0; i

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..