티스토리

뚱이 킁킁 동동이

검색하기

블로그 홈

뚱이 킁킁 동동이

dntworry-behappy.tistory.com/m

zundi 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

무제 보호되어 있는 글입니다. 공감수 0 댓글수 0 2020. 4. 17.
[C++] 백준 1168번 - 요세푸스 문제 2 0. 문제 1. 아이디어 1) 1번부터 N번까지, 총 N명의 사람을 vector에 삽입하고 순서대로 K번째 사람을 탐색해가면서 vector에서 제거하고 다음 K번째 사람을 탐색하는 과정을 반복한다. 2) 이때 K번째 사람을 찾는다고 해서 index의 값을 +k 한다고 생각할 수도 있지만 그렇지 않다. 이미 앞전의 과정에서 하나의 원소를 vector에서 제거했기 때문에 결과적으론 +k-1 하면 된다! 2. 소스코드 #include #include int main() { int K, N; std::cin >> N >> K; std::vector v(N); std::vector result; for (int i = 0; i < N; i++) v[i] = i + 1; int idx = 0; while (!v.e.. 공감수 0 댓글수 0 2020. 4. 14.
[C++] 백준 11656번 - 접미사 배열 0. 문제 1. 아이디어 1) 접미사들을 vector에 넣어서 sort 함수를 이용해서 정렬한 뒤 출력한다! 2. 소스코드 #include #include #include int main() { std::vector v; std::string str; std::cin >> str; for (int i = 0; i < str.length(); i++) v.push_back(str.substr(i)); sort(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) std::cout 공감수 0 댓글수 0 2020. 3. 30.
[C++] 백준 11655번 - ROT13 0. 문제 1. 아이디어 2. 소스코드 #include #include int main() { std::string str; std::getline(std::cin, str); for (int i = 0; i = 'a' && str[i] 'z') str[i] -= 13; else str[i] += 13; } else if (str[i] >= 'A' && str[i] 'Z')str[i] -= 13; else str[i] += 13; } } std::cout 공감수 0 댓글수 0 2020. 3. 30.
[C/C++] 문자 입력 함수 정리 C 1. getchar() // int getchar(void) 내부에 존재 표준 입력 스트림에서 문자 하나를 읽어올 때 사용 키보드 버퍼(stdin)로부터 공백(' ')이나 개행문자('\n') 또한 입력을 받으니 주의해서 사용해야한다. 만일 파일 끝에 도달하거나, 읽기 오류가 발생한다면 함수는 EOF를 return 2. getc() // int getc(FILE* stream) getcar() 함수와 기능적으로 동일하게 작동한다! 3. getch(), getche() // int getch(void), int getche(void) 내부에 존재 키보드 버퍼를 사용하지 않고 바로 출력을 내보낸다 Enter 값을 인식할 때 getch()와 getche()는 '\r'로 인식한다. getche()는 getch.. 공감수 0 댓글수 0 2020. 3. 30.
[C++] 백준 11004번 - K번째 수 0. 문제 1. 아이디어 1) 단순히 sorting 한 후에 K번재 index를 참조하면 시간초과가 난다.. 2) 따라서 Quick Selection 이라는 방법을 새로 사용해야 했다! (nth_element) 2. 소스코드 #include #include #include std::vector v; int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int N, K; std::cin >> N >> K; for (int i = 0; i > input; v.push_back(input); } std::nth_element(v.begin(), v.begin() + K-1, v.end()).. 공감수 0 댓글수 0 2020. 3. 29.
Quick Selection을 이용한 k번째 숫자 탐색: O(n)의 시간 복잡도 N개의 원소 중 k번째로 작은 수를 찾아라 라는 문제를 만났을 때 가장 많이 사용하는 방법 중 하나는 컨테이너를 sorting 후에 k번째 인덱스를 참조하는 방식을 사용한다. 하지만 이렇게 정렬을 했을 경우엔 전체 시간 복잡도가 worst case O(N^2) 혹은 O(N longN)가 되어버리므로 원소의 개수가 많을 경우엔 적합하지 않다. 따라서 Quick Selection 알고리즘을 이용해서 O(N)의 시간 복잡도를 가지는 탐색을 구현할 수 있다. 이름에서도 유추할 수 있듯이 기본 idea는 Quick Sort에서 따왔다. int quick_selection(int n, int* ArrList, int k) { if (ArrList == NULL || n = mid) { std::swap(ArrLis.. 공감수 0 댓글수 0 2020. 3. 29.
[C++] map, multimap container 정리 map과 multimap container은 연관 컨테이너(associative container) 중 하나이다. 1. map, multimap container의 특징 노드 기반으로 이뤄진 균형 이진 트리 구조이다. 각 노드들은 로 이뤄진 pair 객체를 가진다. (이때 map에서는 각 노드는 고유한 key 값을 가지지만, multimap은 중복된 key 값을 허용한다) 노드가 삽입이 되면서 key 값을 기준으로 자동으로 정렬이 이뤄진다. (default는 오름차순!) 저장공간의 필요에 따라서 allocator 객체를 사용한다. 2. 생성자, 연산자, 멤버함수 더보기 map과 multimap은 멤버함수가 동일하다.. 0) 생성자 map m; - int형 key와 int형 value로 이뤄진 pair 객.. 공감수 0 댓글수 0 2020. 3. 29.
[C++] 백준 11652번 - 카드 0. 문제 1. 아이디어 1) N개의 숫자카드에 적혀 있는 정수들을 arr 배열에 저장하고 sort 함수를 사용해서 정렬한다. 2) 오름차순으로 정렬된 arr 배열에서 어떤 정수가 몇 개가 있는지를 카운트해서 pair 쌍으로 저장한다. ex) 1이라는 값이 3개가 존재한다면 tmp 배열에 으로 저장한다. 3) tmp 배열에서 second(개수)가 가장 큰 원소의 first(값)을 출력한다. 2. 소스코드 #include #include #include long long arr[100000]; std::pair tmp[100000]; int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int N; std::cin >> N; for (int i.. 공감수 0 댓글수 0 2020. 3. 29.
[C++] 백준 10989번 - 수 정렬하기 3 0. 문제 1. 아이디어 1) counting sort 를 이용한다! 2. 소스코드 #include #include int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); int N, arr[10001]; std::cin >> N; memset(arr, 0, sizeof(arr)); for (int i = 0; i > input; arr[input]++; } for (int i = 1; i 공감수 0 댓글수 0 2020. 3. 29.
[C++] 백준 10825번 - 국영수 0. 문제 1. 아이디어 1) 기존 정렬 문제에서 정렬 기준의 개수만 늘어났을 뿐이다. 2. 소스코드 #include #include #include #include using namespace std; bool compare(tuple t1, tuple t2) { if (get(t1) != get(t2)) return get(t1) > get(t2); else { if (get(t1) != get(t2)) return get(t1) get(t2); else return get(t1) < get(t2); } } } int main() { ios_base::sync_with_stdio(0); cin.t.. 공감수 0 댓글수 0 2020. 3. 28.
[C++] 백준 10814번 - 나이순 정렬 0. 문제 1. 아이디어 1) pair 클래스에 이름과 나이를 담아서 벡터에 저장한다! 2) 하지만 기존 sort 함수를 사용하면 '이름'까지도 정렬 기준으로 사용되니까 비교함수를 만들어준다. 2. 소스코드 #include #include #include #include bool NewSort(std::pair p1, std::pair p2) { return p1.first > N; std::vector v; for (int i = 0; i > age >> name; v.push_back(std::make_pair(age, name)); }.. 공감수 0 댓글수 0 2020. 3. 28.
[C++] 백준 11651번 - 좌표 정렬하기 2 0. 문제 1. 아이디어 2. 소스코드 #include #include #include int main() { int N; std::cin >> N; std::vector v; for (int i = 0; i > x >> y; v.push_back(std::make_pair(y, x)); } sort(v.begin(), v.end()); for (int i = 0; i < N; i++) std::cout 공감수 0 댓글수 0 2020. 3. 28.
[C++] pair 클래스에 대해서 (+ tuple) pair 클래스란 두 객체를 하나의 객체로 취급할 수 있게 묶어주는 역할! 생김새는 template struct pair; 와 같은데 헤더파일에 존재하며 두 객체 중 첫번째 T1을 first, 두번째 T2를 second로 구분할 수 있다. 멤버함수 1) pair p; : 2개의 int형 변수를 가지는 pair 쌍 'p'를 생성한다. 2) make_pair(3, 4); 3과 4를 가지는 pair쌍을 생성한다. 3) pair.fisrt, pair.second : 각각 1번째 객체, 2번째 객체를 반환한다. 4) get(p), get(p) : 각각 p의 1번째 객체, 2번째 객체를 반환한다. (사실 잘 쓰지 않는다) 또한 기본적으로 pair 클래스의 대소비교는 1. first(1번째 인자) , 2. secon.. 공감수 0 댓글수 0 2020. 3. 28.
[C++] 백준 11650번 - 좌표 정렬하기 0. 문제 1. 아이디어 1) pair클래스를 저장하는 벡터를 생성하여 정렬한다. (sort 함수 사용) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include #include int main() { std::vector v; int N; std::cin >> N; for (int i = 0; i > x >> y; v.push_back(std::make_pair(x, y)); } sort(v.begin(), v.end()); for (int i = 0; i 공감수 0 댓글수 0 2020. 3. 28.
[C++] 백준 2751번 - 수 정렬하기 2 0. 문제 1. 아이디어 1) 위는 합병정렬(Merge Sort), 아래는 퀵정렬(Quick Sort)로 구현했다. (퀵소트는 백준에서 시간초과가 뜬다.. pivot값을 잘 설정해주면 될 듯하다) 2. 소스코드 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include #include int arr[1000000]; int tmp[1000000]; void merge(int st, int ed) // Merge Sort! { int mid = (st + ed) / 2; int idx = st;.. 공감수 0 댓글수 0 2020. 3. 28.
[C++] 백준 11052번 - 카드 구매하기 0. 문제 1. 아이디어 1) 해당 문제에서 dp는 N개를 사기 위한 최대 금액값! 2) 처음 생각했을 땐 dp[N]은 dp[N-1] + P1이라고 생각했지만 테스트케이스에서 볼 수 있듯이 그러지 않은 경우가 있었다. 예를 들어 카드 4개를 사려고 구매하려고 할 때 2개 포함된 카드팩 2개를 사는게 더 금액의 값이 큰 경우가 있다! 3) 그래서 해당 경우까지 모두 고려해주기 위해서 반복문을 사용했다. (물론 시간을 고려했다) (이때, 순열이 아니라 조합으로 봐야한다!) 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include int main() { int N, price[1001], dp[1001]; std::cin >> N; f.. 공감수 0 댓글수 0 2020. 3. 27.
[C++] 백준 2011번 - 암호코드 0. 문제 1. 아이디어 일단 이 문제에서는 고려해줘야할 점들이 생각보다 많았다. 우선 문제에서 dp는 숫자의 개수별로 만들 수 있는 경우의 수라고 정했다! 그리고 만약 N-1번째 숫자와 N번째 숫자가 암호의 범위(1~26) 사이에 있다면 dp[N] = dp[N-1] + dp[N-2] 이고 범위 밖이라면 dp[N] = dp[N-1] 이라는 걸 알아냈다. (왜냐면 저번 문제에서 사용한 아이디어처럼, dp[N-1]에서 그냥 N번째 숫자 하나만 독립적으로 뒤에 붙여주는 경우 그리고 dp[N-2]에다가 N-1번째와 N번째 숫자가 이루는 두자리수 암호를 붙여주는 경우로 나눌 수 있기 때문이다.) 하지만 해석할 수 없는 암호의 경우엔 0을 출력하라고 했다. 해석할 수 없는 암호란, 범위의 숫자로써 판단할 수 없는 .. 공감수 0 댓글수 0 2020. 3. 26.
[C++] 백준 2225번 - 합분해 0. 문제 1. 아이디어 예를 들어 (3, 3) 즉 0부터 3까지의 정수 중에서 3개를 더해 3을 만드는 경우의 수는 아래와 같다. 1. 숫자 0을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 3로 하는 경우의 수 2. 숫자 1을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 2로 하는 경우의 수 3. 숫자 2을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 1로 하는 경우의 수 4. 숫자 3을 제일 먼저 더하고, 연속해서 나오는 2개의 숫자들의 합을 0로 하는 경우의 수 top-down 방식으로 이렇게 쭉쭉 내려가다보면 어느 순간 ( ??, 1 ) 이라는 경우를 만난다. 이때 ( ??, 1 )은 1가지 숫자를 더해서 ??을 만들어야 하니 반드시 1이 된다. (또한 같은.. 공감수 1 댓글수 1 2020. 3. 25.
[C++] 백준 9461번 - 파도반 수열 0. 문제 1. 아이디어 1) 순서대로 그림을 따라서 그려보니까, P(5) 이후의 삼각형들은 모두 시계방향으로 도는 규칙을 가지고 있다. 따라서 점화식을 세웠을 때 P(N) = P(N -1) + P(N - 5) 라는 사실을 발견! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include int main() { int T; long long dp[101]; std::cin >> T; dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2; for (int r = 0; r > N; for (int i = 6; i 공감수 0 댓글수 0 2020. 3. 25.
[C++] 백준 2133번 - 타일 채우기 0. 문제 1. 아이디어 1) 직사각형 타일을 채울 수 있게 기본 단위를 새로 설정한다. (3×2 -> 3개, 3×4 -> 2개) 2) 단위 타일이 짝수로만 이뤄져 있으니까 3×N 에서 N이 홀수라면 타일을 채울 수 없다. 3) 2, 4, 6, ···로 이어지는 N에서 DP의 값은 이전 DP의 값에 xDP[2]를 하면 된다! (왜냐면, 길이가 2씩 늘어나므로 2의 길이를 가진 단위 타일을 붙여준다고 생각하면 된다) (핵심) 하지만 이때, 더해지는 2개의 큰 타일덩어리들이 겹쳐지는 부분에서는 길이가 2인 타일이 4인 타일로 바뀔 수 있는 경우도 카운트 해줘야 한다!! ex) dp[8] = dp[6] + dp[2] 가 dp[4] + dp[4]로 바뀔 수도 있다. 이 때, 앞의 덩어리 오른쪽 2와 뒷덩어리 왼.. 공감수 0 댓글수 0 2020. 3. 24.
[C++] 백준 1699번 - 제곱수의 합 0. 문제 1. 아이디어 1) 야호!!! 2) 해당 문제에서 내가 사용할 dp[i]의 컨셉은 i의 구성하는 최소항들의 개수이다! 그렇다면 그 이후의 수들은 이전 dp값들을 잘 이용한다면 쉽게 최소 제곱수들의 합으로 나타낼 수 있다. ex) dp[80] = dp[64] + dp[16], dp[96] = dp[80] + dp[16] 3) (핵심) 예를 들어 32의 경우와 같이 해당 숫자 이하의 가장 큰 제곱수가 반드시 포함되어야만 하는 건 아니다. ex) 32 = 16 + 16 (O), 25 + 4 + 2 + 1 (X) 그래서 가장 가까이에 있는 제곱수부터 1까지의 케이스를 확인하며 최솟값을 찾으면 된다! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2.. 공감수 0 댓글수 0 2020. 3. 23.
[C++] 백준 2579번 - 계단 오르기 0. 문제 1. 아이디어 1) 하.. 2) 우선 마지막 계단을 반드시 밟을 수 있게 점화식을 세웠을 때 밟는다 밟지 않는다 밟는다 밟는다 ???? 밟는다 밟지 않는다 밟는다 위와 같은 두가지 경우가 성립한다! 일단 지금 세운 점화식을 이용해서 dp의 값들을 구하기 위해선 최소 3개의 값들이 필요하며 dp[0], dp[1], d[2]는 손쉽게 구할 수 있다. (따라서 반복문은 i = 3부터) 3) max 함수를 통해 위에서 세운 두가지 경우 중 더 큰 값을 가지는 경우를 선택하면 된다! 4) 각 점화식에 필요한 부분 이전은, 어떤 계단들을 밟던지 아무 상관이 없다. 따라서 그냥 최댓값을 저장해둔 dp값을 이용하기만 하면 된다!! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15.. 공감수 0 댓글수 0 2020. 3. 23.
[C++] 백준 1912번 - 연속합 0. 문제 1. 아이디어 1) dp[i]에는 i번째 원소가 가지는 최대 연속합이다!!! 2) 연속합이 음수가 되지 않는 선에서는 계속해서 더해도 상관이 없다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include int arr[100000]; int dp[100000]; int main() { int N; std::cin >> N; for (int i = 0; i > arr[i]; int result = dp[0] = arr[0]; for (int i = 1; i 공감수 0 댓글수 0 2020. 3. 23.
[C++] 백준 11054번 - 가장 긴 바이토닉 부분 수열 0. 문제 1. 아이디어 1) i번째 원소를 기준으로, (왼쪽) arr[0] ~ arr[i]는 증가수열, (오른쪽) arr[i] ~ arr[N-1]은 감소수열 2) 따라서 각각의 원소가 가질 수 있는 증가수열과 감소수열의 길이를 합했을 때 가장 큰 길이를 구한다! 3) 이때, 주의할 건 감소수열의 길이를 구할 때 반!드!시! i번째 원소를 포함하는 길이여야 한다는 것! 4) 그래서 나는 역으로, arr[N-1] ~ arr[i]까지의 증가수열의 길이를 구하기로 했다. 2. 소스코드 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 37 38 #include #include int .. 공감수 0 댓글수 0 2020. 3. 22.
[C++] 백준 11722번 - 가장 긴 감소하는 부분 수열 0. 문제 1. 아이디어 1) 앞의 문제들과 동일한 아이디어! 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int main() { int N, length=0,arr[1000], dp[1000]; std::cin >> N; for (int i = 0; i > arr[i]; for (int i = 0; i 공감수 0 댓글수 0 2020. 3. 22.
[C++] 백준 11055번 - 가장 큰 증가 부분 수열 0. 문제 1. 아이디어 1) n번째 원소의 dp값 = n-1번까지의 원소들 중 자신보다 작은 값 중에 가장 큰 dp의 값 + 자신의 값 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int main() { int N, result = 0, arr[1000], dp[1000]; std::cin >> N; for (int i = 0; i > arr[i]; // arr에 수열의 값들 입력 for (int i = 0; i 공감수 0 댓글수 0 2020. 3. 22.
[C++] 백준 11053번 - 가장 긴 증가하는 부분 수열 0. 문제 1. 아이디어 1) bottom-up 방식으로 문제를 풀이한다. 2) N번째 열까지 구할 수 있는 증가하는 가장 긴 부분 수열의 길이는 0번부터 N-1 번열 중 자신보다 작은 원소가 구했던 가장 긴 부분 수열의 길이 +1(본인의 길이)이 된다. 이때, N-1번 열까지 구했던 길이는 dp에 메모이제이션한다. 2. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include int main() { int N, max = 0, value[1000], dp[1000]; std::cin >> N; for (int i = 0; i > value[i]; for (int i = 0; i min) min = dp[j]; dp[i.. 공감수 0 댓글수 0 2020. 3. 15.
[C++] 백준 2156번 - 포도주 시식 0. 문제 1. 아이디어 1) top-down 방식으로 풀기로 했다! 2) 지금 포도주 잔을 마시기 전에, 1. 이전 잔을 마시지 않았다 2. 연속해서 1잔 마셨을 때 3. 연속해서 2잔 마셨을 때 경우를 구분하고, 함수의 매개변수로 받는다. 2. 소스코드 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 #include #include int N, value[10000], dp[10000][3]; //value 배열은 포도주의 양을 저장 //dp 배열은 DP방식으로 문제를 풀기 위해 이전까지의 값들을 저장 int drink(int idx, int c) { if (idx == N) retu.. 공감수 0 댓글수 0 2020. 3. 15.
[C++] 백준 9465번 - 스티커 0. 문제 1. 아이디어 1) 열을 기준으로 하나씩 늘려나가며 각 경우의 수에 대한 최댓값을 기록해둔다. 2) N번째 열에 선택될 수 있는 점수는, 1. N-1번째 열에서 스티커가 떼어지지 않았을 때, 2. N-1번째 열에서 위 스티커가 떼어졌을 때, 3. N-1번째 열에서 아래 스티커가 떼어졌을 때. 총 3가지의 경우로 나누어서 생각할 수 있다. 3) 그렇게 시작해서 1번째 열까지 범위를 넓혀오면 정답을 찾을 수 있다. 2. 소스코드 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 37 38 39 40 #include #include const int MAX = 100000;.. 공감수 0 댓글수 0 2020. 3. 14.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.