문제

두 수의 합 백준 3273 c++

"맞았습니다."코드

#include <bits/stdc++.h>
using namespace std;
​
int num[2000001] = {};
int N, sum;
int cnt;
​
void func(){
​
    cin >> N;
    int a = 0;
​
    for(int i = 0; i < N; i++){
        cin >> a;
        num[a]++; // 입력받은 숫자에 해당하는 인덱스에 존재한다고 1 표시
    }
​
    cin >> sum; // 목표 합 
​
    for(int i = 0; i < (sum+1)/2; i++){ // (2,3)과 (3,2) 중복 카운팅 방지.
        // i와 sum-i 라는 숫자가 존재하는지 확인. 
        if(num[i] == 1 && num[sum-i] == 1){
            cnt++;
        }
    }
​
    cout << cnt;
}
​
​
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
​
    func();
    return 0;
}

 


리뷰

쫌 헷갈렸다.

정렬 되지 않은 순서로 숫자 리스트를 받는다.

따라서 목표 합이 5일 때, (2,3) 쌍과 (3,2) 쌍을 두 번 체크하지 않도록 유의해야 한다.

애초에 배열을 200만개를 만들어 놓고, 입력받은 숫자를 인덱스로 이용했다.

즉 3, 5, 7을 받으면 배열 인덱스 3, 5, 7의 값에 1을 할당한다.

조건체크

if(num[i] == 1 && num[sum-i] == 1)

 

728x90

'알고리즘 > 백준' 카테고리의 다른 글

에디터 list, queue로 2가지로 풀어본 코드 백준 1406번 c++  (0) 2021.11.22
strfry 백준 11328 c++  (0) 2021.11.22
방 번호 백준 1475 c++  (0) 2021.11.21
알파벳 개수 백준 10808번  (0) 2021.11.21
숫자 백준 10093 c++  (0) 2021.11.20

문제

방 번호 백준 1475 c++

"맞았습니다."코드

#include <bits/stdc++.h>
using namespace std;
​
int maxnum = 1; // 최소 세트 개수는 1개다. 
int N;
int arr[10]; // 0부터 9
​
void func(){
​
    cin >> N;
​
    while(N > 0){
        int target = N%10; // 자리수 1개 분리 하기 
        arr[target]++; // 자리수 개수 카운팅 
        N /= 10;
    }
​
    for(int i=0; i<=9; i++){
        if(i==6 || i==9) continue;
        maxnum = max(maxnum, arr[i]);
    }
    // (a[6]+a[9])/2를 올림한 값이
    // 6, 9에 대한 필요한 세트의 수이므로 (a[6]+a[9]+1)/2을 계산
    maxnum = max(maxnum, (arr[6]+ arr[9]+1) / 2);
​
    cout << maxnum;
}
​
​
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
​
    func();
    return 0;
}


리뷰

최소 세트 개수는 1개다.

6과 9는 서로 대신 쓸 수 있기 때문에. 마지막에 처리를 해준다.

 

(a[6]+a[9])/2 를 올림한 수가 6, 9에 대한 필요한 세트의 수다.

6이 2개, 9가 3개 필요한 경우, 올림한 3개의 세트가 필요하다.

 

6의 개수 9의 개수 필요한 세트 수 6와 9개수에 1을 더해서 세운 식
1개 1개 1개 (1+1 +1) / 2 = 1
2개 1개 2개 (2+1 +1) / 2 = 2
2개 2개 2개 (2+2 +1) / 2 = 2
2개 3개 3개 (2+3 +1) / 2 = 3

1212669 가 input으로 들어왔다고 하자.

6, 9를 제외한 다른 수를 확인했을 때 maxnum이 2 였다.

6은 2개, 9는 1개다. 6과 9만 생각하면 2세트가 있으면 된다.

maxnum = max(maxnum, (arr[6]+ arr[9]+1) / 2);

이렇게 maxnum과 비교하면 정답은 2가 된다.

728x90

'알고리즘 > 백준' 카테고리의 다른 글

strfry 백준 11328 c++  (0) 2021.11.22
두 수의 합 백준 3273번 c++  (0) 2021.11.22
알파벳 개수 백준 10808번  (0) 2021.11.21
숫자 백준 10093 c++  (0) 2021.11.20
일곱 난쟁이 백준 2309 c++  (0) 2021.11.20

문제

알파벳 개수 백준 10808번

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
​
// 백준 10808 알파벳 개수
string target;
vector<int> answer(27);
​
void func(){
​
    cin >> target;
​
    int stringSize = target.size();
​
    for(int i =0; i < stringSize; i++){ // 단어 길이만큼 검사 
        answer[target[i]-97]++;
    }
​
    for(int i =0; i < 26; i++){ // 출력 
        cout << answer[i] << ' ';
    }
}
​
​
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
​
    func();
    return 0;
}

 

리뷰

소문자 알파벳 a는 아스키코드로 97이다. z는 127이다. 

a - 97 은 0과 같다.

b - 97 은 1이다.

이것을 인덱스로 활용해서 개수를 셌다.

728x90

'알고리즘 > 백준' 카테고리의 다른 글

두 수의 합 백준 3273번 c++  (0) 2021.11.22
방 번호 백준 1475 c++  (0) 2021.11.21
숫자 백준 10093 c++  (0) 2021.11.20
일곱 난쟁이 백준 2309 c++  (0) 2021.11.20
윷놀이 백준 2490 c++  (0) 2021.11.19

목차

0x00 배열의 정의와 성질 

0x01 기능과 구현 

0x02 STL vector 

0x03 연습문제 


0x00 배열의 정의와 성질 

정의

메모리 상에 원소를 연속하게 배치한 자료구조 

 

성질 

1. O(1)에 k번째 원소를 확인/변경 가능 

2. 추가적으로 소모되는 메모리의 양(overhead)이 거의 없음 

3. Cache hit rate가 높음 

4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림  

 

참고) Cache hit rate 가 높다는 의미 

캐시 적중률이 높다 == 캐시를 참조했더니 데이터가 존재하는 확률이 높다.

캐시의 지역성에 기반하여 캐시에 존재하는 데이터의 주변 데이터도 곧 사용할 가능성이 높은 데이터다. 

배열은 메모리상에 연속한 구간에 존재하기 때문에 Cache hit rate가 높다. 


0x01 기능과 구현

조회, 수정 O(1)

인덱스로 바로 접근할 수 있으니까 O(1) 시간이 걸린다. 

맨 끝에 추가, 마지막 원소를 제거 O(1)

따로 배열을 변경할 필요 없기 때문에 O(1)이 걸린다. 

임의의 위치에 원소 추가 O(N)

평균적으로 N/2 개를 밀어야 하기 때문이다. 

책꽂이에 꽂힌 책들을 생각해보자. 중간에 책을 하나 꽂으려면, 나머지 책들을 옆으로 밀어야 한다. 

임의의 위치에 원소 제거 O(N)

이 경우도 원소를 하나 제거하고, 평균적으로  N/2 개를 밀어야 하니까 O(N)의 시간이 필요하다. 

insert 함수와 erase 함수를 직접 구현해보자

github 링크에 들어가서 코드를 받고 직접 삽입/삭제를 구현해보자. 

존재하지 않는 인덱스를 참조하지 않도록 주의해야 한다. 

배열 초기화 팁 

1. memset  실수할 여지가 많다. 0이나 -1아닌 다른 값을 넣으면 오동작한다. 

2. for  투박하지만 실수할 여지가 없어서 무난하다. 

3. algorithm헤더의 fill함수 사용을 권한다. 

실수할 여지도 별로 없고, 코드가 짧아서 가장 추천하는 방식이다. 

    int a[21];
    int b[21][21];
    
    // 1. memset
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    
    // 2. for
    for(int i = 0; i < 21; i++)
        a[i] = 0;
    for(int i = 0; i < 21; i++)
        for(int j = 0; j < 21; j++)
            b[i][j] = 0;
        
    // 3. fill
    fill(a, a+21, 0);
    for(int i = 0; i< 21; i++)
        fill(b[i], b[i]+21, 0);

0x02 STL vector 

배열과 거의 동일한 기능의 STL 
배열과 달리 크기를 자유자재로 늘이고 줄일수 있는 장점이 있다. 

공식 레퍼런스 사이트에서 확인하며 메서드 정확하게 익히도록 연습하기.
iterator는 따로 공부하는 것을 추천함

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v1(3, 5);  // {5,5,5}
    cout << v1.size() << '\n';   // 3
    v1.push_back(7);   // {5,5,5,7}
    
    vector<int> v2(2);    // {0,0}
    v2.insert(v2.begin()+1, 3);   // {0,3,0}
    
    vector<int> v3 = {1,2,3,4};
    v3.erase(v3.begin() + 2);  // {1,2,4}
    
    vector<int> v4;  // {}
    v4 = v3;   // {1,2,4}
    cout << v4[0] << v4[1] << v4[2] << '\n';  // 1 2 4
    v4.pop_back(); // {1,2}
    v4.clear();    // {}
}

시간 복잡도 유념할 점

앞에서 넣고 빼는 popfront(), pushfront() 는 O(N)의 시간이 걸리는 것을 유의하자. 

insert(), erase()는 시간복잡도가 O(N)

뒤 쪽에 넣고 빼는 popback(), pushback()은 O(1)

벡터에서 = 를 사용하면 deep copy 가 발생한다. 

vector 순회하는 방법

vector<int> v1 = {1,2,3,4,5,6};

// 1. range-based for loop (since C++11)
for(int e: v1)
	cout << e << ' ';
    
// 2. not bad
for(int i = 0; i< v1.size(); i++)
	cout << v1[i] << ' ';
    
// 3. 주의! 
for(int i = 0; i <= v1.size()-1; i++)
	cout << v1[i] << ' ';

 

1. range-based for loop 범위 기반 반복문 (C++11 부터 지원된 기능임을 유의)

2. v1.size()를 인덱스의 끝으로 보는 것 

3. v1.size()는 기본적으로 unsized int를 반환함! 조심해야 함. 

만약, v1이 빈 벡터일 때, 
v1.size() -1 이 unsigned int 0에서 int1 을 빼는 식이 된다. 
그리고 unsiged int 와 int를 연산하면 unsigned int 로 자동 형변환이 된다.

 

unsigned int 0 - (int) 1은 -1이 아니라, 4294967295 가 되어버린다!! 
unsigned int  overflow가 발생하여 런타임 에러가 난다. 


0x03 배열 연습문제

 배열 문제집을 풀어보자. 

BOJ 10808번 알파벳 갯수 


다음시간에는 연결리스트를 배우고 연습문제를 풀어본다. 

공부 내용 출처 : 바킹독 알고리즘 0x03 배열 

728x90

'알고리즘 > 실전 알고리즘' 카테고리의 다른 글

0x05강 - 스택  (0) 2021.11.23
0x04강 - 연결리스트  (0) 2021.11.22
0x02강 - 기초 코드 작성 요령2  (0) 2021.11.20
0x01강 - 기초 코드 작성 요령1  (0) 2021.11.19
0x00강 - 오리엔테이션(환경세팅)  (0) 2021.11.19

문제

숫자 백준 10093

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;

// 백준 10093 숫자
long long A, B, cnt;

void func(){

    if (A > B) {
        swap(A, B);
    }
    if(A == B || B-A == 1){
        cout << 0;
    }
    else{
        cnt = abs(A-B)-1;
        cout << cnt << '\n';
        for(long long i = A+1; i < B; i++){
            cout << i << " ";
        }
    }
}

void input(){

    cin >> A >> B;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    func();

    return 0;
}

리뷰

다시 풀어봐야 할 문제다.

A와 B가 같은 경우와, A와 B가 1차이 나는 숫자인 경우를 생각 못했었다.

 

 

728x90

'알고리즘 > 백준' 카테고리의 다른 글

방 번호 백준 1475 c++  (0) 2021.11.21
알파벳 개수 백준 10808번  (0) 2021.11.21
일곱 난쟁이 백준 2309 c++  (0) 2021.11.20
윷놀이 백준 2490 c++  (0) 2021.11.19
홀수 백준 2576 c++  (0) 2021.11.19

문제

일곱 난쟁이

 

코드

#include <bits/stdc++.h>
using namespace std;
​
// 백준 2309 일곱 난쟁이
vector<int> dwarf(10);
int sum = 0;
​
void func(){
​
    vector<int> result;
    bool extFlag = false;
​
    for(int i = 0; i < 8; i++){ // 0번째 부터 8번째 까지
        sum -= dwarf[i];
​
        for(int j = i+1; j < 9; j++){ // i+1번째 부터 9 번째 까지
            sum -= dwarf[j];
​
            if(sum == 100){
​
                for(int a = 0; a < 9; a++){
                    if(a != i && a != j){
                        result.push_back(dwarf[a]);
                    }
                }
                extFlag = true;
                break;
            }else{
                sum += dwarf[j];
​
            }
        }
        sum += dwarf[i];
        if(extFlag){
            break;
        }
    }
​
    // 정렬 후 출력
    sort(result.begin(), result.end());
    for(int i = 0; i< 7; i++){
        cout << result[i] << '\n';
    }
}
​
void input(){ // 입력 받고 키의 합 누적 
    for(int i = 0; i < 9; i++){
        cin >> dwarf[i];
        sum += dwarf[i];
    }
}
​
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
​
    input();
    func();
​
    return 0;
}

 

리뷰

2개 고르는 것을 permutation을 썼다가 시간을 버렸다.

2중 for문으로 풀면 되는데! 하하..

기본 로직은 2중 for문으로 겹치지 않는 인덱스 i와 j를 구하는 것이다.

미리 구해뒀던 총합 sum에서 i와 j를 뺐을때 100이 되면, 난쟁이 7명을 제대로 찾은 것이다.

2중 for문을 탈출하기 위해 extFlag를 두었다.

728x90

'알고리즘 > 백준' 카테고리의 다른 글

알파벳 개수 백준 10808번  (0) 2021.11.21
숫자 백준 10093 c++  (0) 2021.11.20
윷놀이 백준 2490 c++  (0) 2021.11.19
홀수 백준 2576 c++  (0) 2021.11.19
주사위 세개 c++ 백준 2480  (0) 2021.11.19

이번 강의 내용은 실제 코드를 짤 때 주의해야 할 점이다. 

 

목차 

0x00 STL과 함수 인자 

0x01 표준 입출력 

0x02 코드 작성 팁 


0x00 STL과 함수 인자 

아래 함수의 출력값을 말해보자. 

첫 번째 

func 함수에 t값을 복사해서 보낸다. 

따라서 t값은 변함이 없다. 답은 0이 출력된다. 

두 번째 

배열 이름을 넘긴다는 것은 배열 주소를 넘기는 것이다. 

arr의 값을 넘기고, 0번째 값 주소에 접근해서 10을 할당했다. 

답은 10이 출력된다.  

세 번째 

구조체는 사용자 정의 자료형이다. 첫 번째 문제처럼 값이 다 복사되어 넘어간다.

따라서 답은 0이다. 

 

STL을 쌩으로 함수 인자에 넣으면, 복사해서 보낸다. deep copy

 

STL도 구조체랑 비슷하다.

함수 인자로 실어보내면 복사본을 보낸다. 따라서 원본에 영향을 주지 않고, 0이 출력된다. 

벡터 안의 값을 비교하고 싶다면?  주소 값을 보내자. 

cmp1 함수 : vector 값을 전부 복사하기 때문에 O(N) 시간복잡도가 나온다. 

cmp2 함수 : 주소만 넘기기 때문에, O(1) 이 된다. 


0x01 표준 입출력 

1. cin/cout 쓸 때 유의사항 : 입출력으로 인한 시간초과를 막기 위해서 아래 코드를 넣어주자. 

단, 이 명령을 쓰면 cout/cin과 printf/scanf를 섞어쓰면 안된다. 

ios::sync_with_stdio(0)
cin.tie(0)

 

2. 공백을 포함한 문자열을 받을 때, getline을 쓰자 

3. endl 쓰지 마세요. (궁서체)

줄바꿈이 필요하다면 개행문자를 쓰자. '\n'

 

0x02 코딩 팁

1. 코딩 테스트와 개발은 다르다. 

코테의 목표는 제한 시간 안에 정답을 받는 것이다. 

코테의 목표는 남이 알아볼 수 있는 클린 코드를 작성하는 것이 아니다. (변수명, 예외처리 를 크게 신경 쓸 필요가 없다.)

내가 헷갈리지 않는 범위 안에서 어떻게든 타이핑을 아끼자. 

 

2. [중요] 문제를 30분 고민했는데 실마리가 안잡히면?

스트레스 받지 말고 다른 사람의 코드를 보며 배워가면 된다. (스트레스 받으면 코테 준비 오래 못한다)

코테 준비는 원리를 이해하고 패턴을 익히는 것이기 때문이다. 


기초코드 작성요령2 백준 문제집

다음 시간에는 '배열'을 공부한다.  

공부 자료 출처: 바킹독 실전알고리즘 기초코드 작성요령2 

728x90

'알고리즘 > 실전 알고리즘' 카테고리의 다른 글

0x05강 - 스택  (0) 2021.11.23
0x04강 - 연결리스트  (0) 2021.11.22
0x03강 - 배열  (0) 2021.11.21
0x01강 - 기초 코드 작성 요령1  (0) 2021.11.19
0x00강 - 오리엔테이션(환경세팅)  (0) 2021.11.19

+ Recent posts