백준/구현17

• 

  [백준 3020번 / C++ / 누적합] 개똥벌레 최근 프로젝트를 여러 진행하다보니 3개월 간 코테준비를 못하다가 이 문제를 시작으로 다시 준비하려고 한다. 처음 이 문제에 접근했을 때 이중 for 문을 사용했다. (오랜만이라 시간 복잡도 생각도 안하고 접근... ) 제한 시간은 1초인데, 시간 복잡도는 O(N*H) 이 걸린다. 1억번의 연산이 1초 정도니까 N ≤ 200,000, 2 ≤ H ≤ 500,000 200000*500000 = 1조? 이중 for문 돌리면 100퍼센트 시간 초과가 뜰거다. 그렇기 때문에 한번의 루프로 이 문제를 해결해야한다. 누적합을 사용해보자. #접근방법 석순이와 종유석은 bottom 과 top 에서부터 자란다. 먼저 번갈아가면서 길이가 입력한다고 하니 차례대로 bottom 벡터와 top 벡터에 입력받은 값을 인덱스로 보고 .. 백준/구현 2022. 6. 28.

• 

  [백준 1874번 / C++ / 스택] 스택 수열 #접근 방법 먼저, 임의의 수열을 만들기 위해 N을 입력받고 N만큼의 수를 입력받는다. 본인은 하나의 입력값을 입력할 때 바로 Stack을 활용했다. 1. 스택이 현재 비어있지 않고 top 이 입력받은 수라면 pop 하고 '-' 추가 2. number의 현재 값이 입력받은 값보다 작다면 같을때까지 스택에 (number++) push 와 '+" 추가 3. 스택이 현재 비어있지 않고 top이 입력받은 수보다 크다면 바로 "NO" 출력 후 종료 -> "반드시 오름차순을 지키도록 한다"조건때문에 top 이 입력받은 수보다 크다는 것은 해당수열을 만들수 없다는 것을 의미. 만들수 있었으면 조건 1에서 바로 pop 되어지기때문. #include #include #include #include using namesp.. 백준/구현 2022. 6. 28.

• 

  [백준 18870번 / C++] 좌표 압축 unordered_map 자료구조를 활용해서 풀었다. #접근방법 1. 처음 입력받은 v라는 벡터의 데이터값들을 re_v에 옮겨닮는다. 2. re_v를 오름차순으로 정렬한 후 첫 번째 원소부터 살펴본다. 3. 해당 원소를 key값으로 가지는 map의 값을 cnt로 저장한다. 4. cnt는 해당 원소의 시작번호다. 즉, 이전에 같은 key 값을 가지고 있다면 그 번호로 세팅해 주어야한다. 그래서 본인은 prev라는 변수를 사용하여 이전에 사용했던 값과 다른지 비교를 하고 다르다면 +1 을 한 번호로 세팅해준다. 5. 이후 v라는 벡터의 원소를 key로 가진 map 의 value값을 출력하면 된다. #include #include #include #include using namespace std; int m.. 백준/구현 2022. 3. 24.

• 

  [백준 4948번 / C++] 베르트랑 공준 대표적인 소수 2, 3, 5, 7 이 있는데 각 소수의 배수는 모두 소수가 아니다. 예를 들어, 소수 2의 배수는 4 6 8 ..... 22222222가 있는데 모두 2로 나누어 떨어지니까 소수가 아니다 소수 3의 배수는 6 9 12 ....33333333이 있는데 모두 3으로 나누어 떨어지니가 소수가 아니다. 즉, 소수를 만나면 해당 소수의 배수를 모두 소수가 아니라고 체크를 해준다. check = true; #접근방법 1. 소수인지 아닌지 판별하는 check라는 배열을 123456*2 만큼 생성한다. 2. 2부터 1234567까지 반복문을 돌리면서 소수를 만나면 해당 소수의 배수들을 check에 true로 설정 3. 이후 입력값 n을 받았을 때 n+1 부터 2*n 까지 check 배열에 false로 .. 백준/구현 2022. 3. 17.

• 

  [백준 5052번 / C++] 전화번호 목록 #접근방법 문자열을 담고 있는 벡터를 sort 해준다. 접두어는 현재 벡터 문자열 이전의 문자열이기 때문에 "v[i].find(v[i - 1])" 의 코드를 통해 체크해준다. 만약 0이라면 접두어라는 의미이며 0이 아니라면 접두어가 아니라는 뜻이다. * 0의 의미는 해당 문자열을 찾았을 때 시작 인덱스 번호를 뜻함. #include #include #include #include using namespace std; int main() { int n; cin >> n; while (n--) { int number; cin >> number; string result = "YES"; vector vs; for (int i = 0; i > s; vs... 백준/구현 2022. 3. 2.

• 

  [백준 1759번 / C++ ] 암호 만들기 모든 경우의 수 정렬 벡터를 정렬할 때 정렬 될 수 있는 모든 경우의 수를 물어보는 문제가 있다. 이러한 경우 해당 함수를 사용한다. 즉, A B C 를 정렬하고 싶은데 모든 경우를 정렬하면, ABC ACB BAC BCA CAB CBA 순으로 정 baebalja.tistory.com next_permutation 함수를 활용해서 쉽게 접근할 수 있다. next_permutation은 모든 경우의 수를 정렬하게 되는데 이때 bool 벡터를 생성하여 변화되는 문자들만 활용해서 문자열을 생성할 수 있다. 이때, 체크해야 할 것은 모음이 1개 이상, 자음이 2개 이상이여야 한다는 점을 주의하자. 1. 알파벳 벡터 내림차순으로 정렬 2. check 벡터 오름차순으로 정렬 ex) 두 개의 문자를 비교할 때, e d.. 백준/구현 2022. 2. 14.

• [백준 3474번 / C++] 교수가 된 현우 해당 문제는 어떻게 접근해야할지 먼저 생각을 하고 들어가자. 3! 이면 끝자리의 0의 개수가 몇개인가? 0개이다. 5! 이면 끝자리의 0의 개수가 몇개인가? 1개이다. 10! 이면 끝자리의 0의 개수가 몇개인가? 2개이다. 18! 이면 끝자리의 0의 개수가 몇개인가? 3개이다. 뭔가 규칙이 보인다. 숫자에 0이라는 수를 끝에 위치하게끔 만들수 있는 수는 10이다. 10을 만들기 위해서는 2와 5가 필요하다. 그렇기 때문에 n!에서 2와 5의 쌍을 가지고 있는 개수를 세주면 된다. 2의 경우에는 짝수이면 모두 포함되기 때문에 굳이 카운트 해 줄 필요가 없다.(워낙 많기 때문) 그렇기 때문에 5라는 숫자가 총 몇개 들어가있는지만 카운트 해주면 된다. 만약, 18! 에서 5의 개수는 18/5 를 해주면 몫이 .. 백준/구현 2022. 2. 10.

• [백준 3986번 / C++] 좋은 단어 stack을 활용한 문제이다. 아치형 곡선이 겹치지 않는다는 말이 스택의 최상단 value값과 현재 문자 값이 일치하면 지워주는것을 반복했을 때 스택에 남는 문자가 없다는 뜻이다. #include #include using namespace std; int main() { int n; cin >> n; int result = 0; for (int i = 0; i > ss; for (auto c : ss) { if (s.size() && c == s.top())s.pop(); else s.push(c); } if (s.empty())result++; } cout 백준/구현 2022. 1. 24.

• 

  [백준 4375 / C++] 1 이 문제는 다음과 같이 풀면 된다. 1 11 111 1111 ............ .............. ................ 이런식으로 이어질텐데 저 값 순서대로 입력받은 값으로 나누었을 때 나누어지면 그 길이를 출력해주면 된다. 하지만, 여기서 주의할 점은 int형의 범위를 넘어설 수 있으니 long long 의 타입으로 설정을 해주어도 문제를 해결 할 수 없다. 즉, long long 64비트에 해당하는 정수값을 넘어설 수 있다는 얘기다. 그렇기 때문에 좀 더 깔끔한 방법이 필요한데 나머지를 초기화 시켜주는 것이다. 예를 들면, n=3 일 때 (첫번째 방법 - 틀린 것) 11에서 3을 나누었을 때 나누어지지 않으니까 1을 더 추가해서 111로 만들어준 후 다시 3으로 나눈 나머지를 확.. 백준/구현 2022. 1. 19.

• [백준 9375번 / C++] 패션왕 총 4가지 (바지 안입을 때, 바지1, 바지2, 바지3) -> 총 4가지 근데 여기서 알몸이 아닌 상태여야 하기 때문에 마지막에 -1 을 해줘야한다. 여기서 map 을 활용하여 의상 종류를 키값으로 갖는 벨류값을 하나씩 증가하여 같은 종류의 의상 개수를 확인할 수 있다. #include #include #include using namespace std; int main() { int n; cin >> n; for (int i = 0; i > nn; map m; for (int j = 0; j > s1; string s2; cin >> s2; m[s2]++; } int sum = 1; for (auto x :.. 백준/구현 2022. 1. 18.