매맹이의 기록

문제를 보고 A → B 이렇게 가는건 너무 경우의 수가 많지 않은가?라는 생각을 했다.하지만 반대로 B → A 의 수는 연산의 횟수가 적을 것이라고 생각할 수 있다. 그러니, 우리는 위와 같은 아이디어로 문제를 풀어나갈 수 있다. B → A 를 생각해보자.짝수라면 2로 나누기끝자리가 1이라면 1을 제외시키기1번과 2번에 속하지 않는다면 -1 출력1번과 2번을 코드로 바꾸면 아래처럼 작성할 수 있다.더 깔끔한 코드가 있을 수 있겠지만, 필자는 이렇게까지가 최선이다.while(a  b가 짝수라면 2로 나누기. (가능한 연산이 곱하기 2, 맨 끝자리에 1 추가하기 뿐이니..)if(b % 10 == 1) 이 부분이 끝자리가 1일 때 제거하는 방법. (왜 끝자리가 1이냐면, 1만 추가할 수 있으니까.) 이렇게 핵..

문제가 간단하다.설명도 엄청 간결하다. 이 문제를 해결하기 위해서 쓰인 개념은getline()이다. getline() 함수를 사용하기 위해서는 string 라이브러리를 사용해야 한다.공백의 문자열이 주어질 수도 있어서 while 문의 조건식으로 getline() 함수를 사용하자.string str;while(getline(cin,str)){ cout  이렇게 코드를 작성하면 된다.근데 입력이 없다면 종료가 되어야하는데,내가 작성한 코드는 control(^)+c 를 눌러야 종료가 된다.이런식으로 작성해서 제출한 코드가 수두룩빽빽인데,다 맞았다고 하니까 이번에도 스리슬쩍.. 내가 처음에 썼던 getline() 함수는 아래와 같다.getline(cin, str);cout 이렇게 되어버리면 공백을 포함해서..

문제 풀이 순서는 다음과 같다.1. n 입력 받기2. 합리적으로 무게 나누기 필자는 말을 잘 못하기 때문에.. 이정도로 정리하겠다. 최소 개수의 설탕 봉지가 필요한 것이기 때문에3킬로그램 짜리와 5킬로그램 짜리 중에서 우리는 "5"를 적극 활용하도록 하자. 만약 입력한 수 n이 15라면, 3킬로그램 짜리를 5개, 5킬로그램 0개 가 필요하므로 총 5개가 필요하다.하지만 5킬로그램만 사용하게 된다면 3킬로그램 짜리 0개, 5킬로그램 3개가 필요하다.그러니 5킬로그램을 필터링에 걸리도록 작성해주자. if(n%5==0){ cnt += n/5; cout  그럼 3킬로그램짜리는 어떻게 처리할까?5로 나누어 떨어지지 않을 때 3씩 빼주면서 처리해주면 된다.n -= 3;cnt++; 우리는 설탕 봉지의 개수를 출력..

문제 자체는 특정 규칙을 따르는 수열을 생성한 뒤, 주어진 구간 합을 구하는 문제이다.1,2,2,3,3,3,4,4,4,4,5,5,...i라는 수가 i번 반복된다는 규칙을 가진다. A,B 입력받고, 그에 해당하는 구간합 구하기구간합 [a,b]는 sum += ary[i] 로 쉽게 구할 수 있다.for(int i = a; i  문제에서 제약조건을  정수 A, B(1 ≤ A ≤ B ≤ 1,000) 이렇게 걸어두었기 때문에const로 NMAX를 선언하자.const int NMAX = 1001;1000으로 안 하고 왜 1001로 하나요?--> 상관은 없다. (반복문 돌릴때 등호 쓰기 싫어서) k는 현재 배열의 인덱스이다.1로 초기화했었다.for(int i = 0; i 1000){ break; ..

지난번에 풀었던 문제와 비슷하다.누적합(prefix sum)을 이용하자. 입력 받은 2차원 배열을 저장할 공간과 누적합을 저장할 dp 테이블을 미리 선언해주자.int sum[1025][1025], dp[1025][1025]; N과 M을 입력 받았다면 dp를 처리하자.for(int i=1; i> sum[i][j]; dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + sum[i][j]; }} 왜 dp를 저렇게 처리하나요?https://binaryroot.tistory.com/17 [자료구조] 구간 합구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하..

문제 풀이 순서는 아래와 같다.1. 데이터의 개수 N과 질의 개수 M 입력2. 구간 합을 구할 대상 배열 입력3. 구간 i,j 입력4. 출력 이전 글에 구간 합에 대한 내용을 정리했으니참고하길 바란다.https://binaryroot.tistory.com/17 [자료구조] 구간 합구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한binaryroot.tistory.com 글을 확인했다면, 풀이를 시작해보자.  N과 M 입력int n,m;cin >> n >> m; 배열은 100000를 넘을 수 없으니const로 미리 선언해주기const int NMAX = 100020;int a..

구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.배열 A가 있을 대 합 배열 S는 아래와 같이 정의할 수 있다.S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]    // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이다.합 배열을 미리 구해 놓으면 일정 범위의 합을 구하는 시간 복잡도가 줄어든다. 어떻게 줄어드나요?--> O(N)에서 O(1)이라는 선형 시간으로 줄어들게 됩니다 :) A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우,최악의 경우를 생각해보자.i가 0이고 j가 N인 경우일 것이고,..

문제 외에 추가적으로 더 생각해야하는 문제가 아니어서 좋았다.문제에서 주어진 내용을 따라가면 된다. 문제 풀이 순서1. 수의 개수 N 입력2. vector에 N개의 수 입력3. 중복 제거 후 정렬 or 정렬 후 중복 제거 N개의 수를 vector에 입력int n;vector v;cin >> n; for(int i = 0; i > x; v.push_back(x);} 벡터에 값을 넣을 때는 크게 두 가지의 방법이 존재한다.1. 필자처럼 push_back() 사용하기2. insert() 사용하기 언제 어떤 것을 사용할지는 상황에 따라 다르다.함수사용 목적시간 복잡도특징push_back()벡터의 끝에 값을 추가평균 O(1), 최악 O(n)동적 배열 확장 시 재할당 발생 가능insert()특정 위치에 ..

하루 종일 걸렸다.나는 너무 어렵게 풀었다. 어렵게 풀었다기 보다는 아직 이정도 난이도의 문제를 풀 정도가 아닌 것 같다.엄청난 검색과 엄청난 참고를 통해 완성한 나의 코드 분류 보고 풀지 말라고 했는데,,, 나는 또 보고 풀었다. 일단 풀이를 시작해보겠다. 자료구조 문제이고 스택을 이용하라고 했으니까그렇게 풀어보자. 탑의 개수와 높이 설정하기.int n;cin >> n;stack> s; pair가 무엇인지에 대해서는 이전 글에 설명했으니아래 링크를 달아두겠다.https://binaryroot.tistory.com/9 [백준] 10814번 : 나이순 정렬 - C/C++내가 생각한 문제 해결 순서는 아래와 같다. 1. 회원수 n 입력하기2. 회원의 나이와 이름 입력하기3. 나이순으로 출력하기 문제는 간단했..

문제 풀이 순서는 아래와 같다.1. 시험 본 과목의 수 N 입력 받기2. 배열에 넣기3. 새로운 평균을 통해 성적 구하기 점수를 1차원 배열에 넣을 건데,오늘은 계속해서 유용하게 쓰일 만한 팁을 소개하고자 한다. 바로 const 로 선언해주기const int NMAX = 1000;문제에서 과목의 개수가 1000 개가 넘어가지 않도록 지정했기 때문에const 형태로 선언해주면, 배열은 아래처럼 써줄 수 있다.int ary[NMAX]; 그냥 아래처럼 쓰면 안 되나요?int ary[1000]; 상관은 없다.내가 들었던 강의에서는나중에.. 더 어려운 문제를 풀게 되면제시한 수의 범위를 넘어서는 것을 방지하기 위해const로 선언한다고 하긴 했다. 코드 스타일은 사람마다 다르니참고만 해도 좋다. 1차원 배열에 값..