티스토리

세모

검색하기

블로그 홈

세모

sebbb-in.tistory.com/m

SSU CSE slowly grow up

구독자: 21

방명록 방문하기

728x90

주요 글 목록

[백준/실버1] 백준 28117번 prlong longf - c++ (dp) [백준/실버1] 백준 28117번 prlong longf - c++ (dp) 문제 모든 int가 longlong으로 바뀐 문자열이 주어진다. 가능한 원래 문자열은 모두 몇 가지인가? -> longlong을 int로 바꿀 수 있는데 만들 수 있는 문자열의 개수 문제 해설 long => A로 치환 int => B로 치환 AA -> B로 바꿀 수 있음 long의 개수 나올 수 있는 경우 경우의 수 A(1) / 0 X 1 AA (2) AA / B 2 AAA (3) BA / AB / AAA 3 AAAA (4) BAA / ABA / AAB / BB / AAAA 5 (2+3) AAAAA (5) BAAA / ABAA / AABA / AAAB BBA / BAB / ABB / AAAAA 8 (3+5) AAAAAA (6) .. 공감수 0 댓글수 0 2024. 4. 11.
[백준/실버1] 백준 2502번 떡 먹는 호랑이 - c++ ( dp) [백준/실버1] 백준 2502번 떡 먹는 호랑이 - c++ ( dp) 어렸을 때 풀었던 그냥 값을 무작정대입하는 방정식과 같은 문제다. 다른 dp문제는 점화식 세울 때 초기 값을 세우기 쉬웠는데 예) 피보나치 1 1 .. 이건 초기값이 하나밖에 주어지지 않았다. 그래서 거꾸로 가는 방식으로 채택해야하는데 이것도 초기값이 주어진게 하나밖에 없어서 쉽지 않았다. 그래서 어렸을 적 배운 방정식을 이용해보았다. 1 2 3 4 5 6 a b a+b a+2b 2a+3b 3a+5b 이렇게 나온다. 그래서 이걸 어떻게 구현해줄수 있을까... 고민하였다. 사실 저 식은 진짜 금방알아냈는데 이걸 코드로 어떻게 구현하고, 시간 초과가 되지 않을지 너무너무 고민되었다.. 스택으로 풀어야할지.. 그냥 단순하게 변수로 개수를 정.. 공감수 0 댓글수 0 2024. 4. 10.
[백준/실버4] 백준 1920번 수 찾기 -c++ 이분 탐색 / 자료구조 / 정렬 [백준/실버4] 백준 1920번 수 찾기 -c++ 이분 탐색 / 자료구조 / 정렬 하나하나 비교해가면서 풀면 100% 시간초과가 날 것이다. 해당 문제는 이분 탐색의 교과서 같은 문제 이분 탐색은 맨 오른쪽, 왼쪽 점을 잡은 뒤 mid 를 정하고 또 이걸 반복해주는 것이다. 중요한 것은 "정렬"을 해줘야 한다는 점이다. 그래야 12345 라고 쳤을 때 mid인 3보다 목표 숫자가 작으면 그 앞에 있거나 없거나 하고 크면 뒤에 있거나 없거나 하면서 비교해볼 수 있기 때문이다. 1) 직접 구현 #include using namespace std; int n,m, num; vector v; int binary_search(int a){ int r=n-1, l=0; while(r>=l){ int mid = (r.. 공감수 0 댓글수 0 2024. 4. 4.
[백준/실버3] 백준 15649 N과 M(1) - c++ (dfs/ 백트레킹) [백준/실버3] 백준 15649 N과 M(1) - c++ (dfs/ 백트레킹) N과 M 시리즈는 엄청 많아서 1을 통해 dfs랑 백트래킹을 익히는 것에 초점을 뒀다. 그리고 해당 코드를 암기해서 다른 것들에 응용하는게 수월할 것 같다. 코드 #include using namespace std; int n, m; int arr[9]; int arred[9]; void dfs(int idx){ if(idx == m){ for(int i=0; i dfs(2) -> if문 실행 > arred[2] =0; 2)(idx ==1 인 상태) arred[3] ==0 -> arr[1] =3 arred[3] =1; -> dfs(2) -> if문 실행 -> arred[3] =0; 3)(idx ==1 인 상태) arred[4].. 공감수 0 댓글수 1 2024. 3. 23.
[백준/실버4] 백준 10610번 30 - c++ (수학/그리디 알고리즘/ 문자열/ 정렬/ 정수론) 문제 해석/코드 설명 [백준/실버4] 백준 10610번 30 - c++ (수학/그리디 알고리즘/ 문자열/ 정렬/ 정수론) 문제 해석/코드 설명 중요 포인트 - N는 최대 10^5개의 숫자로 구성 - 30의 배수의 특징 1. 0이 들어가 있어야 한다. 2. 원소의 합이 3의 배수여야 한다. 코드 #include #include using namespace std; int main (){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); string num=""; //10^5까지니깐 string으로 받아줌 cin >> num; sort(num.begin(), num.end(), greater()); //내림차순 정렬 bool zero=0; long lo.. 공감수 0 댓글수 2 2024. 3. 18.
[백준/실버5] 백준 10814번 나이순 정렬 - c++ (정렬 알고리즘) 문제 해석/코드 설명 [백준/실버5] 백준 10814번 나이순 정렬 - c++ (정렬 알고리즘) 문제 해석/코드 설명 코딩테스트 타파하기 1주차 - 3번 문제 해석 1. 나이 순으로 정렬 2. 나이가 같으면 가입한 순 (값이 들어간 순서대로) 중요한 함수 sort() 기존 순서를 보장하지 않는다. stable_sort() 기존 순서를 보장한다. 문제에서 입력된 순서로 출력을 원했으니 stable_sort를 이용해줘야한다. vector v; // 에 값 넣는 법 cin >> age >> name; v.push_back(make_pair(age, name)); vector v(n); // -> 크기 지정 cin >> v[i].first >> v[i].second; 전체 코드 #include #include #include usi.. 공감수 1 댓글수 1 2024. 3. 14.
[백준/실버3] 백준 2108번 통계학 - c++ (수학/ 구현/ 정렬 알고리즘) 문제 해석/코드 설명 [백준/실버3] 백준 2108번 통계학 - c++ (수학/ 구현/ 정렬 알고리즘) 문제 해석/코드 설명 코딩테스트 타파하기 1주차 - 2번 문제 해석 산술평균 : N개의 수들의 합을 N으로 나눈 값 => 들어오는 값들을 다 더하면 된다. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 => 사이즈에서 /2를 해주면 그 인덱스가 중앙값이 된다 (주의 : 무조건 수의 개수가 홀수이기 때문에 case를 수가 짝수인지 홀수인지로 안나눠도 된다.) 최빈값 : N개의 수들 중 가장 많이 나타나는 값 => 배열을 생성해서 각 인덱스 별로 몇개가 있는지 알아둔다. 만약 maxidx가 1보다 크면 같은게 여러개니깐 '두 번째'수를 출력해줘야한다. 범위 : N개의 수들 중 최댓값과 최솟값의 .. 공감수 1 댓글수 0 2024. 3. 12.
[백준/실버5] 백준 13241번 최소공배수 - c++ / 유클리드 호제법(최대공약수, 최소공배수) 문제 해석/코드 설명 [백준/실버5] 백준 13241번 최소공배수 - c++ / 유클리드 호제법(최대공약수, 최소공배수) 코딩테스트 타파하기 1주차 - 1번 주요 키 포인트 유클리드 호제법 (최대공약수) 2개의 자연수(또는 정수) a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (이때, a>b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다. 아래의 코드를 살펴보면 int gcd(long long int a, long long int b){ if(b==0) return a; return gcd(b, a%b); } 연쇄적으로 최대공약수를 찾아가는 것을 볼 수 있다. 성질에 따라서 b를 r로 나눈 나머지를 구하고 다시 이것들을 연쇄적으로 진행해서 나머지가 0이 되었을 때 나누는 수 ((a%b)에서 b)가 a와 b.. 공감수 0 댓글수 0 2024. 3. 12.
[백준] 4049 균형잡힌 세상 실버 4 - stack https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net //균형잡힌 세상 실버4 //안좋은 코드 #include #include using namespace std; int main (){ string str; cin >> str; int a,b=0; for (int i=0; i 공감수 0 댓글수 0 2023. 7. 22.
[백준] 2839 설탕배달 실버 4 C++ https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 경우를 나눠서 풀었다 더 간단하게 푸는 방법이 있으려나? -> 그리디 알고리즘 이용하기 수가 간단한 5와 3이어서 5는 큰 영향을 끼치지 않고 3으로 인해서 -1이 될 것인지. 아니면 값이 제대로 출력 될 것인지가 결정된다고 생각했다. 경우의 수 생각하기 5로 나눴을 때 0 -> 5의 배수이므로 5로 나눠준 값을 출력해주면 된다 5로 나눴을 때 1 -> 최소 6이어야지 3*2로 2를 출력해줄 수 있다. N이.. 공감수 0 댓글수 0 2023. 7. 22.
c++ cin, cout 왜 시간초과? 시간 초과 날 일이 없는데 시간초과가 났다.. 왜 났을까? 근데 해결법을 보니깐 scanf랑 printf를 쓰면 된다고 한다 근데 또 c++을 쓰는데 그걸 쓰면 무의미해진다고 생각했다.. 그러던 중 스터디에서 코드 넣었던게 생각이 났고 그걸 쓰니깐 시간초과가 해결됐다. ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 이 코드이다. 일반적으로 #include 에서 scanf, printf, cin, cout을 다 지원하는데 std인 cin, cout은 scnaf, printf보다 속도가 느리다 그래서 그냥 시간초과가 날 수 있다. 그런데 저 코드를 넣으면 scanf, printf를 못쓰는 대신 cin, cout이 scanf,pr.. 공감수 0 댓글수 0 2023. 7. 19.
[C++ 코딩테스트 자료구조 알고리즘] 01-1 배열, 연결리스트(linked list), std::array 배열 정적 배열은 int arr[size]; 형태로 선언합니다. C에서 동적배열은 int* arr = (int*)malloc(size * sizeof(int)); 형태로 선언합니다. C++에서 동적 배열은 int* arr = new int[size]; 형태로 선언합니다. 정적 배열은 stack 메모리 영역에 할당된다. 그래서 함수를 벗어날 때 자동으로 해제 된다. 반면에 동적 배열은 힙heap 영역에 할당되며 사용자가 직접 해제하기 전까지 유지 배열은 캐시 지역성이 좋다. 옆에 있는 원소의 캐시도 함께 데려오기 때문에 나중에 연속된 원소에 매우 빠르게 접근할 수 있다. 연결리스트 (linked list) 연결된 자료구조는 노드(node)라고 하는 여러 개의 메모리 청크에 데이터를 저장 이 경우 서로 다른.. 공감수 4 댓글수 5 2023. 4. 2.
[백준]BOJ_단어 공부_ 1157번 브론즈 1 - C++ (아스키코드, string) 주어진 예제 입력을 다 입력해보지 않으면 해당 것 처럼 틀릴 수 있다.. 1157번: 단어 공부 (acmicpc.net) 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int max =0; string s; int num=0; int arrnum[26]={0}; cin>>s; for(int j=0; j 같은 값이 있는지 판별.. 공감수 1 댓글수 2 2022. 11. 3.
[백준]BOJ_실버4_9012번 괄호 - C++ 스택 STL사용 9012번: 괄호 (acmicpc.net) 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; for(int i=0; i> s; for (int i = 0; i 공감수 4 댓글수 4 2022. 10. 7.
[백준]BOJ_실버 1 _1629 곱셈_C++ 분할정복/재귀 1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net #include using namespace std; long long f(long long A, long long B, long long C){ if(B==0){ return 1;} long long X = f(A ,B/2, C); if(B%2==0) { return X*X %C; } return X%C *X%C*A%C;}// > A>>B>>C; cout 왜냐면 A를 B번 곱한 수를 구하는 것이기 때문에 매우 커질것임을 예측할 수 있다. 2. B가 0이면 A^0=1 이라서 1을 리턴.. 공감수 2 댓글수 1 2022. 10. 7.
[C++]cout<<fixed, precision() / C++소수점 자릿수 정하기 C언어를 하다보면 float로 실수를 지정하고 %.2f로 소수점 몇자리 까지 놓을 건지 지정할 수 있었습니다. 하지만 C++은 어떻게 지정을 해줘야 하는지 몰랐습니다. 백준 문제를 풀다가 C++로 요즘 풀고 있는데 그래서 이러한 궁금증을 해결해보기 위해 찾아보던 중 저 두개를 알게 되었습니다. cout 공감수 3 댓글수 6 2022. 9. 30.
[백준]BOJ_브론즈1_1546번 평균 -C++ 1546번: 평균 (acmicpc.net) 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net #include using namespace std; int main(){ int N; int arr[1000]={0}; float A[1000]={0}; float max=0; double sum=0, result=0; ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >>N; for(int i=0; i> arr[i]; if(ar.. 공감수 0 댓글수 0 2022. 9. 30.
[백준]BOJ_브론즈3_2562번 최댓값 - C++ [백준]BOJ_실버5_2751 수 정렬하기 2 - C++ /알고리즘(시간 복잡도, 정렬 sort) (tistory.com) [백준]BOJ_실버5_2751 수 정렬하기 2 - C++ /알고리즘(시간 복잡도, 정렬 sort) #include #include using namespace std; int N, Arr[1000001]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N; for(int i=0; i > Arr[i];} sort(Arr, Arr+N);.. sebbb-in.tistory.com 해당 문제와 해당 글 안에 있는 sort의 개념을 참고하시길 추천드립니다 !! 2562번: 최댓값.. 공감수 3 댓글수 0 2022. 9. 24.
[백준]BOJ_브론즈2_2920번 음계 - C/C++ 1~8 차례대로면 ascending 8~1 차례대로면 descending 섞여있으면 mixed #include int main() { int arr[10]={1,2,3,4,5,6,7,8}; int dearr[10]={8,7,6,5,4,3,2,1}; int num[10]={0}; for(int i=0; i 공감수 4 댓글수 1 2022. 9. 24.
[C++] 알고리즘 STL 정렬하기 - sort(오름차순 정렬, 내림차순 정렬) What is 'sort'? 우리가 탐색을 하거나, 정보를 찾거나 할 때 정보가 정렬되어있어야 한다. 배열에 수를 넣은 뒤 하나하나 수를 비교하면서 i의 값을 증가하거나 하는 방법으로 정렬을 시켜줄 수 있다. 하지만 그 방법은 매우 오래 걸리며, 복잡하고 귀찮다. 그럴때 손 쉽게 정렬해서 분석하기 용이하게 바꿔주는 것이 'sort'이다. sort 형태 1. sort(start,end)를 이용하면 [start,end) 범위의 인자를 오름차순(기본값,default)으로 정렬해 준다. ->[)은 반닫힘 구간이다. 아래처럼 배열이 존재하면 시작은 i를 가르키고 3까지의 값을 말하면 4를 end가 가르키게 되는 것이다. 1 2 3 4 2. sort(start,end,compare)를 이용하면 사용자가 정한 함수(.. 공감수 3 댓글수 3 2022. 9. 21.
[C++]꿀팁 1탄 _ 헤더파일 .h /#include <bits/stdc++.h> #include 해당 헤더파일에 대해 낯설게 느껴지시는 분들이 있으실 것이다. 하지만 이 헤더파일을 꽤나 효자스럽다. 우리가 자주 쓰는 #include , #include 뿐만 아니라 다양한 헤더파일을 포함하고 있는 헤더파일이라고 생각하면 된다. 그래서 여러줄 쓰지 않고 #include 한줄만 쓰면 편리하게 쓸 수 있다. #include #include 을 쓰는 것보다 #include 을 쓰는게 훨씬 느리다.. 시간 초과 나옴 공감수 2 댓글수 2 2022. 9. 21.

728x90

문의안내

티스토리
로그인
고객센터

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