이세계개발자의 개발일지

이번 문제는 실버 4 난이도의 10773번 제로문제이다.접근법정수 K의 수가 최대 100,000 이기에 vector 나 배열을 사용하면 push & sum 과정에서 시간 복잡도가 O(n)이기에 O(n^2)가 되어 TLE가 발생하는 것을 확인할 수 있었다. 따라서 큐 혹은 스택 둘 중 하나를 사용해야 하는데, 가장 최근에 쓴 수를 지우는 동작을 반복하기 때문에 선입선출 구조의 큐보다 스택이 알맞는 것을 확인할 수 있었다. 아래는 작성한 코드이다.#include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); stack s; int N; cin >> N; for (int i = 0; i > te..

이번문제는 실버 5 난이도의 좌표 정렬하기 2이다.접근법이차원 백터를 만든 후 sort 함수를 사용하여 Y > X 좌표 순으로 정렬하였다. 아래는 작성한 코드이다.#include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector> v; for (int i = 0; i > a >> b; v.push_back({a, b}); } sort(v.begin(), v.end(), [](const vector& a, const vector& b) { if (a[1] == b[1]) return a[0]

이번 문제는 실버 4 난이도의 2839번 설탕 배달 문제이다.문제 요약N kg의 설탕을 3kg 또는 5kg 봉지에 담아서 최소 개수로 배달해야 한다.정확히 Nkg을 만들 수 없으면 -1을 출력한다. 접근법 : Greedy 5kg 봉지를 최대한 많이 쓰고, 남는 걸 3kg로 채워보자.N을 5로 나눈 몫만큼 5kg을 써보고남는 무게가 3으로 나눠떨어지는지 확인안 되면 5kg을 하나 줄이고 다시 시도 아래는 작성한 코드이다.#include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); int n, count = 0; cin >> n; while (n >= 0){ // N이 음수면 -1 출력 ..

이번 문제는 실버 5 난이도의 1676번 팩토리얼 0의 개수 문제이다. 처음 작성한 코드이다. 접근법팩토리얼을 직접 브루트포스로 계산한 후 이를 to_string 함수를 사용하여 string으로 바꾸고 뒤에서부터 '0'를 count 하는 방식으로 구현하였다.#include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; int mutiply = 1; for (int i = 1; i 1차 코드 실패 이유그냥 브루트포스를 사용하여 곱으로 팩토리얼을 만든 후 0을 count 하면 13! 에서 int 오버플로우 / 20! 에서 long long 오버플로우가 된다. 수학적 ..

이번 문제는 실버 5 난이도의 영화감독 숌 문제이다.접근법이 문제에서는 "666" 의 숫자조합이 수에 포함되어 있는 경우를 모두 찾아야 한다.따라서 필자는 정수를 string 으로 변환한 후 "666" 이 포함되어 있으면 count 한 후 N의 값과 일치한 경우의 정수를 출력하는 방식으로 코드를 작성하였다.이 과정에서 숫자간의 규칙이 있는지 확인해보았지만 특별한 규칙은 찾지 못하였고, N이 최대 10000이고, 시간제한이 2초이기에 브루트포스를 사용해도 TLE가 발생하지 않음을 확인할 수 있었다. 따라서 브루트포스를 사용하여 문제를 해결하였다. 새롭게 배운 내용C++ 에서는 string 라이브러리 속 string to_string (int) 이라는 함수를 사용하여 int를 string으로 바꿔줄 수 있다..

이번 문제는 실버 4 난이도의 solved.ac 문제이다. 접근법부터 생각해보자이 문제는 주어진 난이도 의견들 중 극단적인 값을 제거한 뒤 평균을 계산하는 문제로, 정렬 후 상위 및 하위 15%를 제외하고 나머지 값들의 평균을 반올림해 출력하는 것이 핵심이다.먼저 입력값의 개수를 기준으로 제거할 의견 수를 round(n × 0.15)로 계산한 뒤, 전체 의견을 정렬하고 양 끝에서 해당 개수만큼 제외한 값을 합산하여 평균을 구한다. 이때 입력이 0일 경우를 예외 처리하고, 평균 계산 시 실수형으로 정확하게 나눈 후 round() 함수를 사용해 반올림해야 하며, 합계 자료형은 오버플로우를 방지하기 위해 long long을 사용하는 것이 안전하다. 하지만 입력이 10^5까지이기에 int 도 문제 없이 작동하는..

이번 문제는 브론즈 1 난이도 ISBN문제이다. 접근법을 정리해보면 이러하다.입력된 문자열에서 *의 위치(idx) 찾기다른 12자리 숫자들의 가중 합을 계산해 sum에 저장하기.* 위치가 짝수라면 해당 자리의 가중치는 1, 홀수라면 3.i를 0~9까지 대입하며 (sum + i * weight + check_digit) % 10 == 0을 만족하는 값 출력 아래는 작성한 코드이다.#include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); string v; cin >> v; int index = v.find('*'); int end = (int)v[12] - '0'; index = in..

이번 문제는 실버 4 난이도의 9012번 괄호 문제이다. 문제의 접근법부터 생각해보자.문자열에서 ()을 찾아서 발견하면 ()을 문자열에서 삭제하고 다시 ()이 모두 사라질 때까지 탐색한 후 문자열의 크기가 0이라면 YES, 아니라면, NO를 출력하면 되는 문제이다. 아래는 작성한 코드이다.#include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int i = 0; i > temp; while (temp.find("()") != string::npos) { temp.erase(temp.find("()"), 2); ..

이번 문제는 실버 4 난이도의 요세푸스 문제 0이다. 문제의 접근법부터 살펴보자. 11866번(요세푸스 문제 0)은 원형으로 앉아있는 N명의 사람 중 K번째 사람을 반복적으로 제거할 때, 제거되는 순서를 구하는 문제이기에, 자료구조(리스트, 큐 등)를 이용해 사람들을 순서대로 저장한 뒤, K번째마다 해당 인덱스의 사람을 제거하며, 제거된 순서를 기록하면 된다.매번 K번째 사람을 찾을 때마다 남은 사람 수에 따라 인덱스를 갱신(모듈로 연산 활용)하고, 사람을 제거한 후에도 원형 구조처럼 인덱스를 순환시키는 것을 반복해서 N명이 모두 제거될 때까지 과정을 이어가면, 요구하는 결과를 얻을 수 있습니다. C++ vector 의 메서드 중 erase 를 사용하면 인덱스의 사람을 제거할 때, 제거된 공간이 자동으..

이번 문제는 실버 5 난이도의 7568번 덩치문제이다.문제의 접근법부터 살펴보자.입력이 X Y의 형태로 N개 주어지기 때문에, 2차원 배열을 이용해야 함을 알 수 있다.그리고 문제에서 힌트를 준 것을 잘 살펴보면, 브루트포스를 사용하여 완전탐색을 한 후 자기 자신보다 큰 값이 몇개인지를 카운트 하고 이를 바로바로 ' '로 출력하면 됨을 볼 수 있다. 시간제한이 1초 (연산 100,000,000회), N이 최대 50이며, for 반복문 3회 O(n^3) 50^3 의 연산을 2회 50^3*2 진행하니, 대략 계산해보면 50*50*50*2 최대 250,000번의 연산이 진행되는 것을 볼 수 있으며 따라서 vector 를 사용해도 TLE 가 발생하지 않는 것을 쉽게 알 수 있을 것이다. 아래는 작성한 코드이다..