• Donald Shell에 의해 삽입 정렬의 결점을 보안하기 위해 고안된 정렬방식
• 입력 배열을 부분 배열로 나눠 정렬하는 과정을 부분 배열의 개수를 바꾸며 이 과정을 여러번 거치는 방식
• 부분 배열의 개수를 정하기 위해 h를 설정
• 아래는 간격이 4인 쉘 정렬을 C++로 작성한 코드이다

  void shellsort(int arr[], int n){
    int h, i, j, val;
    h = 1;
    do {
        h = 3 * h + 1;
    } while(h < n);
    do {
        h = h / 3;
        for(i = h; i < n; i++){
            val = arr[i];
            j = i;
            while (arr[j - h] > val) {
                arr[j] = arr[j - h];
                j = j - h;
                if (j < h - 1) {
                    break;
                }
            }
            arr[j] = val;
        }
    } while(h > 1);
  }

• i, j, val 등 상수 크기 메모리를 사용하므로 제자리 정렬
• 크기가 같은 원소의 상대적 위치가 바뀌는 불안정한 정렬

✅퀵 정렬 (Quick Sort)

• 분할 정복 (divide and conquer) 방식의 정렬 알고리즘

  • 분할 정복 (divide and conquer): 해결할 수 없는 문제를 작은 문제로 분할해서 해결하는 방식

• 분할 원소 (partitioning element) 사용

• 배열의 양 끝으로부터 배열의 중심을 향해 동시 검색

  1. 좌측 -> 우측: 분할 원소보다 큰 원소를 탐색, 우측 -> 좌측: 분할 원소보다 작은 원소를 탐색 후 서로 교환
     2. 반복하다 둘이 만나게 될 경우 탐색 종료 후 그 자리에 분할 원소 대입

• 아래는 분할 원소인 partition을 구하는 것을 C++로 작성한 코드이다

  int partition(int arr[], int left, int right) {
    int part, val;
    part = left;
    val = arr[part];
    do {
        do {
            left++;
        } while (arr[left] < val);
  
        do {
            right--;
        } while (arr[right] > val);
  
        if (left < right) {
            swap(&arr[left], &arr[right]);
        }
        else {
            break;
        }
    } while(1);
    arr[part] = arr[right];
    arr[right] = val;
    return right;
  }

• 아래는 퀵 정렬을 수행하는 함수를 순환 알고리즘(재귀)을 이용해 C++로 작성한 코드이다

  void quicksort(int arr[], int left, int right) {
    int k;
    if(right > left) {
        k = partition(arr, left, right + 1);
        quicksort(arr, left, k - 1);
        quicksort(arr, k + 1, right);
    }
  }

• 오름차순 또는 내림차순으로 정렬되어 있을 때가 최악의 경우

• 1번의 quicksort 호출에 의해 분할 원소 1개가 제자리를 잡고 부분 배열이 치우쳐질 경우 최악의 시간 복잡도를 갖음

• 최악의 시간 복잡도는 O(n^2)

• 제자리 정렬이며, 크기가 같은 원소의 상대적 위치가 바뀌는 불안정한 정렬

사진 출처

📖참고자료

• 대학교 ppt 교안

📌스키마와 인스턴스

• 스키마 (Schema): 데이터베이스에 저장되는 데이터 구조와 제약 조건을 정의한 것
• 인스턴스 (Instance): 스키마에 따라 데이터베이스에 실제로 저장된 값

📌3단계 데이터베이스 구조

• 데이터베이스를 쉽게 이해하고 이욯할 수 있도록 하나의 데이터베이스를 관점에 따라 3단계로 나눔
  1. 외부 단계 (External Level): 개별 사용자 관점
     2. 개념 단계 (Conceptual Level): 조직 전체의 관점
  2. 내부 단계 (Internal Level): 물리적인 저장 장치의 관점
• 각 단계별 다른 추상화 (abstraction) 제공
• 내부에서 외부 단계로 갈수록 추상화 레벨 높아짐

외부 단계 (External Level)

• 데이터베이스를 개별 사용자의 관점에서 이해하고 표현하는 단계
• 하나의 데이터베이스에 여러 개의 외부 스키마가 존재 가능
• 외부 스키마 (External Schema)
  1. 외부 단계에서 사용자에게 필요한 데이터베이스를 정의한 것
     2. 각 사용자가 생각하는 데이터베이스의 모습(논리적 구조)으로 사용자마다 다름
     3. 서브 스키마 (Sub Schema)라고도 표현

개념 단계 (Conceptual Level)

• 데이터베이스를 조직 전체의 관점에서 이해하고 표현하는 단계
• 하나의 데이터베이스에 하나의 개념 스키마만 존재
• 개념 스키마 (Conceptual Schema)
  1. 개념 단계에서 데이터베이스 전체의 논리적 구조를 정의한 것
     2. 조직 전체의 관점에서 생각하는 데이터베이스의 모습 ex) 전체 데이터베이스에 어떤 데이터가 저장되는지, 데이터들 간에 어떤 관계가 존재하고 어떤 제약조건이 있는지, 데이터에 대한 보안 정책 및 접근 권한에 대한 정의

내부 단계 (Internal Level)

• 데이터베이스를 저장 장치의 관점에서 이해하고 표현하는 단계
• 하나의 데이터네이스에 하나의 내부 스키마만 존재
• 내부 스키마 (Internal Schema)
  1. 저장 장치에 전체 데이터베이스가 실제로 저장되는 방법을 정의
     2. 물리적 저장 구조를 정의 ex) 레코드 구조, 필드 크기, 레코드 접근 경로 등..

📌3단계 데이터베이스 구조의 사상 또는 매핑

스키마 사이 대응 관계

• 외부/개념 사상: 외부 - 개념 스키마의 대응 관계: 응용 인터페이스 (Application Interface)
• 개념/내부 사상: 개념 - 내부 스키마의 대응 관계: 저장 인터페이스 (Storage Interface)
• 데이터베이스를 3단계 구조로 나누고 단계별로 스키마 유지, 스키마 사이 대응 관계를 정의하는 궁극적 목적 => 데이터 독립성의 실현

데이터 독립성 (Data Independency)

• 하위 스키마 변경 시 상위 스키마가 영향을 받지 않는 특성
• 논리적 데이터 독립성
  1. 개념 스키마가 변경되어도 외부 스키마 영향 X
     2. 개념 스키마 변경 시 외부/개념 사상만 정확히 수정하면 됨
• 물리적 데이터 독립성
  1. 내부 스키마가 변경되어도 개념 스키마 영향 X
     2. 내부 스키마 변경 시 개념/내부 사상만 정확히 수정하면 됨

데이터 사전 (Data Dictionary)

• 시스템 카탈로그 (System Catalog)라고도 함
• 데이터베이스에 저장되는 데이터에 관한 정보(메타 데이터: 데이터에 대한 데이터)를 유지하는 시스템 데이터베이스
• 정확하고 효율적인 데이터 이용을 위해 참고해야하는 스키마, 사상 정보, 다양한 제약조건 등을 저장
• 데이터베이스 관리 시스템이 스스로 생성 및 유지
• 일반 사용자도 접근 가능하지만 저장 내용만 검색 가능

데이터 디렉토리 (Data Directory)

• 데이터 사전에 존재하는 데이터에 실제 접근하는 데 필요한 위치 정보를 저장하는 시스템 데이터베이스
• 일반 사용자의 접근 허용 X

사용자 데이터베이스 (User Database)

• 사용자가 실제 사용하는 데이터가 저장되어있는 일반 데이터베이스

✅데이터베이스 사용자

📌데이터베이스 사용자

• 데이터베이스를 이용하기 위해 접근하는 모든 사람
• 이용 목적에 따라 데이터베이스 관리자, 최종 사용자, 응용 프로그래머로 구분

데이터베이스 관리자 (Database Administrator)

• 데이터베이스 시스템을 운영 및 관리하는 사람
• 주로 데이터 정의어, 데이터 제어어 이용

최종 사용자 (End User)

• 데이터베이스에 접근해 데이터 조작 (삽입, 삭제, 수정, 검색)
• 주로 데이터 조작어 사용

응용 프로그래머 (Application Programmer)

• 데이터 언어를 삽입해 응용 프로그램을 작성하는 사람
• 주로 데이터 조작어 사용

✅데이터 언어

📌데이터 언어

• 사용자 - 데이터베이스 관리 시스템 통신 수단
• 사용 목적에 따라 데이터 정의어, 데이터 조작어, 데이터 제어어로 구분

데이터 정의어 (Data Definition Language; DDL)

• 스키마 정의, 수정, 삭제를 위해 사용

데이터 조작어 (Data Manipulation Language; DML)

• 데이터의 삽입, 삭제, 수정, 검색 등 처리를 요구하기 위해 사용
• 절차적 데이터 조작어, 비절차적 데이터 조작어로 구분
  1. 절차적 데이터 조작어 (Procedural DML): 사용자가 어떤 데이터를 원하고 그 데이터를 얻기 위해 어떻게 처리해야하는지도 설명
     2. 비절차적 데이터 조작어 (Nonprocedural DML): 사용자가 어떤 데이터를 원하는지만 설명, 선언적 언어 (Declarative Language)라고도 함

데이터 제어어 (Data Control Language; DCL)

• 내부적으로 필요한 규칙이나 기법을 정의하기 위해 사용
• 사용 목적
  1. 무결성: 정확하고 유효한 데이터만 유지
     2. 보안: 허가된 사용자에게만 권한 부여
     3. 회복: 장애가 발생해도 데이터 일관성 유지
     4. 동시성 제어: 동시 공유 지원

✅데이터베이스 관리 시스템의 구성

📌데이터베이스 관리 시스템

• 데이터베이스 관리 및 사용자 데이터 처리 요구 수행
• 주요 구성요소
  1. 질의 처리기 (Query Processor): 사용자의 데이터 처리 요구를 해석 및 처리
     2. 저장 데이터 관리자 (Stored Data Manager): 디스크에 저장된 데이터베이스, 데이터 사전을 관리 및 접근

📖참고자료

• 대학교 ppt 교안
• 데이터베이스 개론 2판 김연희저자

📌파일 시스템

• 데이터를 파일로 관리하기 위해 파일을 생성, 삭제, 수정, 검색하는 기능을 제공하는 SW
• 응용 프로그램 마다 필요 데이터를 별도 파일로 관리
• 파일 시스템의 문제점

1. 같은 내용의 데이터가 여러 파일에 중복 저장 -> 데이터 중복성 >> 데이터의 일관성과 무결성(데이터의 정확성 보장 X)을 유지하기 어려움
2. 응용 프로그램이 데이터 파일에 종속적 -> 데이터 종속성 >> 사용하는 파일의 구조를 변경하면 응용 프로그램도 함께 변경해야 함
3. 데이터 파일에 대한 동시 공유, 보안, 회복기능이 부족 >> 데이터 중복 가능성 문제 >> 파일 수정 중 장애 발생 시 회복 불가

✅데이터베이스 관리 시스템의 정의

📌데이터베이스 관리 시스템 (DBMS)

정의

• 파일시스템의 문제를 해결하기 위해 제시된 SW
• 필요 데이터를 데이터베이스에 통합해 저장 및 관리
• 데이터를 가진 쪽을 서버(server), 외부에서 데이터를 요청하는 쪽을 클라이언트(client)라 칭함
• DBMS 서버가 파일을 다루며 데이터의 일관성 유지, 복구, 동시 접근 제어 등 기능을 수행
• 데이터의 중복을 줄이고 표준화해 무결성 유지

데이터베이스 관리 시스템에서의 데이터 관리

데이터베이스 관리 시스템의 주요 기능

• 정의 기능: 데이터베이스 구조를 정의하거나 수정 가능
• 조작 기능: 데이터를 삽입, 삭제, 수정, 검색하는 연산 가능
• 제어 기능: 데이터를 항상 정확하고 안전하게 유지 가능

파일 시스템과 DBMS의 비교

DBMS의 단점

• 비용이 많이 듦
  1. 운영체제와 함께 설치됨
     2. DBMS 설치로 인한 구매비용 증가
     3. 동시 접속자 허용 수에 따라 가격 증가
• 백업과 회복이 복잡함
  1. 데이터의 양이 많아 구조가 복잡함
     2. 다수의 사용자의 동시 공유로 인한 장애 발생 시 원인파악이 어려움
     3. 백업이 요구됨
• 중앙 집중 관리로 인한 취약점이 존재
  1. 모든 데이터가 데이터베이스에 통합되어 DBMS에 집중되어있음

DBMS의 기능

• 데이터 정의(Definition): 데이터의 구조를 정의하고 구조에 대한 삭제 및 변경 기능을 수행
• 데이터 조작(Manipulation): 데이터 조작 SW가 요청하는 데이터의 삽입, 수정, 삭제 작업을 지원
• 데이터 추출(Retrieval): 사용자가 조회하는 데이터 또는 응용 프로그램의 데이터 추출
• 데이터 제어(Control): 데이터베이스 사용자를 생성하고 모니터링하며 접근 제어 (백업과 회복, 동시성 제어 등 기능 지원)

DBMS의 발전 과정

• 1세대: 네트워크 DBMS, 계층 DBMS > 네트워크 DBMS: 데이터베이스를 그래프 형태로 구성 ex) IDS (Integrated Data Store) > 계층 DBMS: 데이터베이스를 트리형태로 구성 ex) IMS (Information Management System)

• 2세대: 관계형 DBMS > 관계형 DBMS: 데이터 베이스를 테이블 형태로 구성 ex) 오라클 (oracle), MySQL 등

• 3세대: 객체지향 DBMS, 객체관계 DBMS > 객체지향 DBMS: 객체를 이용해 데이터베이스 구성 ex) 오투(O2), 온투스(ONTOS), 젬스톤(GemStone) > 객체관계 DBMS: 객체형 DBMS + 관계형 DBMS

• 4세대: NoSQL, NewSQL DBMS

  1. Not only SQL
  2. 비정형이면서 방대한 데이터를 저장하기 적합함
  3. NoSQL DBMS는 비정형 데이터를 처리하는데 적합하고 확장성이 뛰어남 > 안정성과 일관성 유지를 위해 복잡한 기능을 포기했으며 데이터 구조를 미리 정해두지 않는 유연성을 가짐
  4. NewSQL DBMS는 관계 DBMS의 장점과 NoSQL의 확장성 및 유연성을 합친 DBMS -> ex) 구글 스패너 등

     📖참고자료

• MySQL로 배우는 데이터베이스 개론과 실습 저자 박우창

• 데이터베이스 개론 2판 저자 김연희

• 대학교 ppt 교안

• 가장 작은 원소부터 가장 큰 원소로 오름차순 순서대로 원소를 재배치 시키며 배열을 정렬하는 방식

1. 정렬할 n개의 데이터가 배열 arr에 저장되어있다고 가정
2. n개의 key 중 가장 작은 것을 찾아 첫번째 key인 arr[0]과 자리바꿈
3. 남아있는 원소들 중에 가장 작은 키를 찾아 그 원소와 arr[1]의 자리를 바꿈
4. k번째 단계에서는 남아있는 (n - k + 1)개의 key 중 가장 작은 것을 찾아 arr[k - 1]과 자리바꿈
5. 위 단계를 n - 1번 반복

• k번째 단계에서는 항상 (n - k)회의 비교를 수행하므로, (n - 1) + (n - 2) + ... + 1 이므로 n(n - 1) / 2 의 시간 복잡도를 가진다. 따라서, 평균 및 최악의 시간 복잡도는 O(n^2)이 된다.
• 아래는 C++로 작성한 선택 정렬 함수이다.

void selectionsort(int arr[], int n){
    int i, j, MinIndex;
    for(i = 0; i < n - 1; i++){
        MinIndex = i;
        for(j = MinIndex + 1; j < n; j++){
            if(arr[MinIndex] > arr[j]){
                 MinIndex = j;
            }
        }
        if(MinIndex != i){
            swap(&arr[i], &arr[MinIndex]);
        }
    }
}

• i, j, MinIndex 등 상수 크기의 메모리를 사용하므로 제자리 정렬
• 안정성: 불안정한 정렬

✅버블 정렬 (Bubble Sort)

• 좌측서부터 우측으로 이동하며 인접한 두 개의 원소를 서로 비교하고 좌측의 원소가 더 크면 우측의 원소와 교환되는 방식

1. 정렬할 n개의 데이터가 배열 arr에 저장되어있다 가정
2. 한 번 완료되었을 때 n개의 원소 중 가장 큰 원소가 우측 끝인 n-1 인덱스에 존재
3. 0번째 인덱스부터 n-2번째 인덱스까지 차례로 검색 후 완료되면 2번째로 큰 원소가 n-2번째 인덱스에 존재
4. 위 단계들 반복

• 역순으로 정렬된 배열일 경우 최악의 시간복잡도를 가진다.
• 1번째 일때 n-1번 비교, 2번째일 때 n-2번 비교, k번째일때 n-k번 비교하기 때문에, (n-1) + (n-2) ... + 1 = n(n-1)/2이므로 O(n^2)의 시간복잡도를 가지게 된다.
• 아래는 C++로 작성한 버블 정렬 함수이다.

void bubblesort(int arr[], int n){
       for(int i = 0; i < n; i++){
           for(int j = 1; j < n - i; j++){
               if(arr[j - 1] > arr[j]){
                   swap(&arr[j - 1], &arr[j]);
            }
        }    
    }
}

• i, j 등 상수 크기의 메모리를 사용하므로 제자리 정렬
• 안정성: 안정된 정렬

✅삽입 정렬 (Insertion Sort)

• 앞에서부터 하나씩 순서를 맞춰나가는 방식

1. 정렬할 n개의 데이터가 배열 arr에 저장되어있다 가정
2. k번째 단계일 때, 배열 맨 처음 k-1개의 key들(0 ~ k-2 인덱스에 존재하는 원소들)은 이미 정렬되어있음.
3. k-1번째 인덱스 원소 값을 0 ~ k-2 인덱스 원소들의 값들과 비교해 적절한 위치에 삽입해 0 ~ k-1번째 인덱스의 값들이 정렬되도록 함

※ 인덱스 값이 배열 내 최소 값인 경우 arr[1]과 비교 후 멈추지 않고 다시 arr[0]과 비교되려하기 때문에 이를 막기 위해 arr[0]에는 배열의 최소 값보다도 더 작은 값을 추가로 저장하면, 실제 자료들은 1 ~ n번 인덱스에 저장됨

• 비교 횟수가 원소들의 순서에 민감
• 이미 정렬되어 있을 경우, 최선의 경우로 시간복잡도는 O(n)을 가짐
• 역순으로 정렬되어 있을 경우는 최악의 경우로 시간복잡도는 O(n^2)을 가짐 (k번째 키 삽입 시 k번의 비교를 수행하므로 2 + 3 + ... +n = n(n+1)/2 - 1)
• 평균 시간 복잡도 또한 O(n^2)을 가짐
• 아래는 C++로 작성한 삽입 정렬 함수이다.

  void insertionsort(int arr[], int n){
       int i, j, val;
    for(i = 2; i <= n; i++){
           val = arr[i];
        j = i;
        while(arr[j - 1] > val){
              arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = val;
    }   
  }

• i, j, val 등 상수 크기 메모리를 사용하므로 제자리 정렬
• 인접한 원소 값과 비교하면서 자신의 값과 같은 값이 나올 경우 바꾸지 않으므로 안정된 정렬

📖참고자료

• 대학교 ppt 교안

• ** 데이터 (Data)** 현실세계에서 단순히 관찰하거나 측정해 수집한 사실이나 값

• ** 정보 (Information)** 의사 결정에 유용히 활용할 수 있도록 데이터를 처리한 결과물

• ** 정보 처리 (Information Processing)** 데이터에서 정보를 추출하는 과정 또는 방법

• ** 정보 시스템 (Information System)** 데이터를 수집해 저장해뒀다가 필요할 때 유용한 정보를 만들어주는 수단

데이터베이스 (Database)

• 정보 시스템 내부에서 데이터를 저장하고 있다가 필요할 때 제공하는 역할을 담당

✅ 데이터베이스의 정의와 특징

📌데이터베이스의 정의

• 특정 조직의 여러 사용자가 공유해 사용할 수 있도록 통합해서 저장한 운영데이터의 집합

• 통합데이터 (integrated data) 최소의 중복과 통제 가능한 중복만 허용한 데이터

• 공유데이터 (shared data) 특정 조직의 여러 사용자가 함께 소유 및 이용할 수 있는 데이터

• 저장데이터 (stored data) 컴퓨터가 접근할 수 있는 매체에 저장된 데이터

• 운영데이터 (operational data) 조직의 주요 기능을 수행하기 위해 지속적으로 필요한 데이터

📌데이터베이스의 특징

• 실시간 접근성 (real-time accessibility) 사용자의 데이터 요구에 실시간으로 응답

• 계속 변화 (continuous evolution) 데이터의 계속되는 삽입, 삭제, 수정을 통해 현재의 정확한 데이터를 유지

• 동시에 공유 가능 (concurrent sharing) 서로다른 데이터의 동시 사용뿐 아니라 같은 데이터의 동시 사용 또한 지원

• 내용기반 참조 (content reference) 데이터가 저장된 주소나 위치가 아닌 내용 참조

✅데이터와 데이터베이스

1. 정형 데이터 (structured data)

• 구조화된 데이터 (미리 정해진 구조에 따라 저장된 데이터)
• ex) 엑셀 스프레드시트, 관계 데이터베이스 테이블

2. 반정형 데이터 (semi-structured data)

• 구조에 따라 저장된 데이터이나 데이터 내용 안에 구조에 대한 설명이 함께 존재하는 데이터
• 구조 파악을 위한 파싱(parsing) 과정이 필요
• 보통 파일형태로 저장됨
• ex) HTML, XML, JSON문서나 웹 로그, 센서 데이터 등

3. 비정형 데이터 (unstructured data)

• 정해진 구조 없이 저장된 데이터
• ex) 소셜 데이터의 텍스트, 영상, 이미지 등과 같은 멀티미디어 데이터

📖참고자료

• 데이터베이스 개론 2판 김연희 저
• 대학교 ppt 교안

백준 9375번 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. * 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. * 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

문제 분석

수학적 지식인 조합에 대해서 생각이 제일 먼저 났고, 이를 어떻게 코드로 작성할지 고민을 많이 했다. 고민해 보니 map 자료구조를 사용하고, 어떤 의상을 입는지 저장하지 않고 몇개의 종류가 있는지만 알면 경우의 수를 쉽게 출력할 수 있다 판단하였다. 따라서, map 자료구조에서 사용하는 타입은 어디에 사용하는 의상인지 알 수 있게할 string 타입과 이 의상이 몇개가 있는지 알기 위한 int타입을 사용한다.

예를 들어서 모자 3개와 상의 2개가 있다할 경우, 모자에서는 (쓰지 않는 경우, 모자1, 모자2, 모자3) 총 4개의 경우의 수가 나오며, 상의에서는 (입지 않는 경우, 상의1, 상의2) 총 3개의 경우의 수가 존재하게 된다. 위 두 경우의 수를 곱하고 알몸일 경우의 수인 1을 빼면 결과가 나오게 된다.

제출코드

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(void) {
    int test, clothes;
    string what, where;
    cin >> test;

    for (int i = 0; i < test; i++) {
        cin >> clothes;
        map<string, int> clothing;

        for (int j = 0; j < clothes; j++) {
            cin >> what >> where;
            clothing[where]++;
        }
        int sum = 1;
        for (auto a : clothing) {
            sum *= (a.second + 1);
        }
        cout << sum - 1 << "\n";
    }
    return 0;
}

백준 17219번 2019 HEPC - MAVEN League의 "비밀번호 만들기"와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못 한다는 것이었다! 그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민이는 메모장에서 찾기 기능을 활용하지 못하고 직접 눈으로 사이트의 주소와 비밀번호를 찾았다. 메모장에 저장된 사이트의 수가 늘어나면서 경민이는 비밀번호를 찾는 일에 시간을 너무 많이 쓰게 되었다. 이를 딱하게 여긴 문석이는 경민이를 위해 메모장에서 비밀번호를 찾는 프로그램을 만들기로 결심하였다! 문석이를 도와 경민이의 메모장에서 비밀번호를 찾아주는 프로그램을 만들어보자.

입력

첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다.

두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다.

N+2번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소가 한줄에 하나씩 입력된다. 이때, 반드시 이미 저장된 사이트 주소가 입력된다.

출력

첫 번째 줄부터 M개의 줄에 걸쳐 비밀번호를 찾으려는 사이트 주소의 비밀번호를 차례대로 각 줄에 하나씩 출력한다.

문제 분석

사이트 주소와 비밀번호를 key와 value 쌍으로 가지는 map을 사용하면 쉽게 풀 수 있을 것이라 생각했다. find 함수를 통해서 사이트 주소를 찾고, 그 사이트에 맞는 비밀번호를 출력하면 문제가 해결된다.

코드

#include <iostream>
#include <string>
#include <map>

using namespace std;

map<string, string> pass;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    string site, password, isSite;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> site >> password;
        pass.insert({ site, password });
    }

    for (int i = 0; i < m; i++) {
        cin >> isSite;
        if (pass.find(isSite) != pass.end()) {
            cout << pass.find(isSite)->second << "\n";
        }
    }
    return 0;
}

코드 정답!!

백준 1764번 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

문제 분석

듣도 못한 사람의 배열, 보도 못한 사람의 배열을 만들고 이 두 배열에서 겹치는 사람의 수와 이름을 사전순으로 출력하는 문제이다. N과 M이 50만 이하의 자연수이므로 이중 for문을 쓴다면 시간 초과가 날 것이 분명하다고 생각했다. 그래서 생각한 것이 출력 또한 사전순으로 출력하기 때문에, 입력받은 이름들을 저장한 배열들을 사전순으로 정렬하고, 이분탐색을 사용한다면 시간복잡도가 훨씬 줄어들어 시간 내에 실행이 가능하다고 생각했다.

작성 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> notListen;
vector<string> notSee;
vector<string> notSeenLis;

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

    int n, m, cnt = 0;
    string name;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> name;
        notListen.push_back(name);
    }

    for (int i = 0; i < m; i++) {
        cin >> name;
        notSee.push_back(name);
    }
    sort(notListen.begin(), notListen.end());
    sort(notSee.begin(), notSee.end());

    if (notListen.size() > notSee.size()) {
        for (int i = 0; i < m; i++) {
            if (binary_search(notListen.begin(), notListen.end(), notSee[i])) {
                notSeenLis.push_back(notSee[i]);
                cnt++;
            }
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            if (binary_search(notSee.begin(), notSee.end(), notListen[i])) {
                notSeenLis.push_back(notListen[i]);
                cnt++;
            }
        }
    }
    cout << cnt << "\n";

    for (int i = 0; i < notSeenLis.size(); i++) {
        cout << notSeenLis[i] << "\n";
    }
    return 0;
}

코드는 정답!! if-else 문으로 듣도 못한 배열의 크기와 보도 못한 배열의 크기를 나눠준 이유는 실행 시간을 더 줄여주기 위해 for문을 더 적게 돌도록함에 있어서 이렇게 작성했다.

아쉬운 점

cnt를 사용하지 않고 notSeenLis 배열의 사이즈를 출력해줘도 괜찮았을 것 같다.

백준 1620번

입력

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

문제 분석

포켓몬 이름을 물어볼 경우 포켓몬 번호가 출력되도록 하며, 번호를 물어볼 경우 포켓몬 이름을 출력하도록 만드는 문제로, (key, value)쌍을 사용하는 자료구조인 map을 사용하게 된다면 쉽게 풀 수 있다고 생각했다. key값으로는 포켓몬의 이름, value 값으로는 포켓몬 번호를 저장하면 된다. 입력이 또한 최대 10만개가 나올 수 있으므로 스트림 동기화도 꺼주면 시간 초과도 나지 않을 것이다.

코드

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

map<string, int> pokemon;
vector<string> pokemonName;

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

    int n, m;
    string name, quiz;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> name;
        pokemon.insert({ name, (i + 1) });
        pokemonName.push_back(name);
    }

    for (int i = 0; i < m; i++) {
        cin >> quiz;
        if (isdigit(quiz[0])) {
            cout << pokemonName[stoi(quiz) - 1] << "\n";
        }
        else {
            cout << pokemon.find(quiz)->second << "\n";
        }
    }
    return 0;
}

코드 정답!!

백준 11723번 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

• add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.

• remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
• check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
• toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
• all: S를 {1, 2, ..., 20} 으로 바꾼다.
• empty: S를 공집합으로 바꾼다.

입력

26 add 1 add 2 check 1 check 2 check 3 remove 2 check 1 check 2 toggle 3 check 1 check 2 check 3 check 4 all check 10 check 20 toggle 10 remove 20 check 10 check 20 empty check 1 toggle 1 check 1 toggle 1 check 1

출력

1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 0

문제 분석

위 여러 연산들을 수행하는 프로그램을 작성하는 문제로, 가장 처음 생각나는 게 벡터라서 벡터로 문제를 해결하려 했다. 더해서, 수행할 연산과 숫자를 문자열로 입력 받고, substr을 이용해서 띄어쓰기를 기준으로 앞 문자열과 뒷 문자열을 분리해 앞 문자열의 문자열을 통해서 어떤 연산을 할 것인지와 뒷 문자열을 숫자로 변환시켜 어떤 수를 연산에 이용할 것인지 나누었다. all과 empty같은 경우 띄어쓰기와 숫자 없이 문자열만 나오기 때문에 if문을 이용해서 띄어쓰기가 나오는지 나오지 않는지 구분하면 쉽게 해결 가능할 것 같다.

처음 작성한 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> set;

void add(int num) {
    bool isNum = false;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            break;
        }
    }
    if (!isNum) {
        set.push_back(num);
    }
}

void remove(int num) {
    bool isNum = false;
    int index;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            index = i;
            break;
        }
    }
    if (isNum) {
        set.erase(set.begin() + index);
    }
}

void check(int num) {
    bool isNum = false;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            break;
        }
    }
    if (isNum) {
        cout << 1 << "\n";
    }
    else {
        cout << 0 << "\n";
    }
}

void toggle(int num) {
    bool isNum = false;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            break;
        }
    }
    if (isNum) {
        remove(num);
    }
    else {
        add(num);
    }
}

void all() {
    set.clear();
    for (int i = 1; i <= 20; i++) {
        set.push_back(i);
    }
}

void empty() {
    set.clear();
}

int main(void) {
    int test, number;
    string str, order;

    cin >> test;
    cin.ignore();
    for (int i = 0; i < test; i++) {
        getline(cin, str);

        if (str.find(" ") != -1) {
            order = str.substr(0, str.find(" "));
            number = stoi(str.substr(str.find(" ") + 1, str.length()));
        }
        else {
            order = str;
        }

        if (order == "add") {
            add(number);
        }
        else if (order == "remove") {
            remove(number);
        }
        else if (order == "check") {
            check(number);
        }
        else if (order == "toggle") {
            toggle(number);
        }
        else if (order == "all") {
            all();
        }
        else if (order == "empty") {
            empty();
        }
    }
}

실행 했을 때 결과는 정확히 나왔었는데 시간 초과가 났다... for문에서 시간 초과가 발생했는지 생각했지만 2중 for문을 사용하지 않았기 때문에 시간복잡도가 O(n)으로 시간이 그렇게 길어질 것이라 생각하지 않았다... 설마 입출력에서 시간을 잡아먹나 싶어 C++과 C의 표준 스트림 동기화를 끄는 코드를 추가해보았다

수정한 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> set;

void add(int num) {
    bool isNum = false;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            break;
        }
    }
    if (!isNum) {
        set.push_back(num);
    }
}

void remove(int num) {
    bool isNum = false;
    int index;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            index = i;
            break;
        }
    }
    if (isNum) {
        set.erase(set.begin() + index);
    }
}

void check(int num) {
    bool isNum = false;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            break;
        }
    }
    if (isNum) {
        cout << 1 << "\n";
    }
    else {
        cout << 0 << "\n";
    }
}

void toggle(int num) {
    bool isNum = false;
    for (int i = 0; i < set.size(); i++) {
        if (num == set[i]) {
            isNum = true;
            break;
        }
    }
    if (isNum) {
        remove(num);
    }
    else {
        add(num);
    }
}

void all() {
    set.clear();
    for (int i = 1; i <= 20; i++) {
        set.push_back(i);
    }
}

void empty() {
    set.clear();
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test, number;
    string str, order;

    cin >> test;
    cin.ignore();
    for (int i = 0; i < test; i++) {
        getline(cin, str);

        if (str.find(" ") != -1) {
            order = str.substr(0, str.find(" "));
            number = stoi(str.substr(str.find(" ") + 1, str.length()));
        }
        else {
            order = str;
        }

        if (order == "add") {
            add(number);
        }
        else if (order == "remove") {
            remove(number);
        }
        else if (order == "check") {
            check(number);
        }
        else if (order == "toggle") {
            toggle(number);
        }
        else if (order == "all") {
            all();
        }
        else if (order == "empty") {
            empty();
        }
    }
}

C++과 C의 표준 스트림 동기화 때문에 입출력에서 시간을 잡아먹었던 것 같다... 코드 수정하니까 정답!! (※ 더해서, endl은 개행에 더해서 내부 버퍼도 비워주기 때문에 "\n"보다 속도가 느리기 때문에 "\n"을 사용하는 것도 속도 향상에 도움이 된다.)

백준 1012번 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

문제 분석

2차원 배열에 저장되어있는 배추 위치를 이용해 인접한 곳에 배추가 존재하는지 탐색해 문제를 해결할 수 있다 판단해서 그래프 탐색 방식인 DFS를 이용했다.

처음 제출한 코드

#include <iostream>
#include <algorithm>

using namespace std;
int n, m, k;
int ground[51][51] = { 0, };
bool visited[51][51];

int dirX[4] = { 0,0,1,-1 }; 
int dirY[4] = { 1,-1,0,0 };

void dfs(int y, int x) {
    for (int i = 0; i < 4; i++) {
        int nextX = x + dirX[i];
        int nextY = y + dirY[i];

        if (nextY < 0 || nextY >= n || nextX< 0 || nextX >= m) {
            continue;
        }
        if (ground[nextY][nextX] && !visited[nextY][nextX]) {
            visited[nextY][nextX] = true;
            dfs(nextY, nextX);
        }
    }
}

int main(void) {
    int test, p1, p2;
    cin >> test;

    for (int i = 0; i < test; i++) {
        int cnt = 0;
        cin >> m >> n >> k;
        for (int j = 0; j < k; j++) {
            cin >> p1 >> p2;
            ground[p2][p1] = 1;
        }

        for (int l = 0; l < n; l++) {
            for (int h = 0; h < m; h++) {
                if (ground[l][h] == 1 && !visited[l][h]) {
                    dfs(l, h);
                    cnt++;
                }
            }
        }
        cout << cnt << "\n";
    }
}

틀렸다고 뜬다... 왜 틀렸을까 고민해 보니 test를 여러번 했다 가정했을 때, 전역으로 설정한 visited와 ground 2차원 배열을 다시 쓸 텐데 다시 쓸 때 초기화를 시켜주지 않았었다...😅 아래는 visited와 ground를 fill 함수를 이용해서 다시 사용할 때 초기화를 시켜주고 사용하도록 구현한 코드이다.

수정한 코드

#include <iostream>
#include <algorithm>

using namespace std;
int n, m, k;
int ground[51][51] = { 0, };
bool visited[51][51];

int dirX[4] = { 0,0,1,-1 }; 
int dirY[4] = { 1,-1,0,0 }; 

void dfs(int y, int x) {
    for (int i = 0; i < 4; i++) {
        int nextX = x + dirX[i];
        int nextY = y + dirY[i];

        if (nextY < 0 || nextY >= n || nextX< 0 || nextX >= m) {
            continue;
        }
        if (ground[nextY][nextX] && !visited[nextY][nextX]) {
            visited[nextY][nextX] = true;
            dfs(nextY, nextX);
        }
    }
}

int main(void) {
    int test, p1, p2;
    cin >> test;

    for (int i = 0; i < test; i++) {
        int cnt = 0;
        cin >> m >> n >> k;
        for (int j = 0; j < k; j++) {
            cin >> p1 >> p2;
            ground[p2][p1] = 1;
        }

        for (int l = 0; l < n; l++) {
            for (int h = 0; h < m; h++) {
                if (ground[l][h] == 1 && !visited[l][h]) {
                    dfs(l, h);
                    cnt++;
                }
            }
        }
        cout << cnt << "\n";

        for (int l = 0; l < n; l++) {
            fill(ground[l], ground[l] + m, 0);
            fill(visited[l], visited[l] + m, false);
        }
    }
}

2차원 배열들을 초기화 시켜주는 코드를 추가하니 정답!

헷갈렸던 부분

2차원 배열에서는 첫 번째 인덱스가 보편적으로 행을 의미하며, 두 번째 인덱스가 열을 의미하기 때문에 y좌표를 첫 번째 인덱스에 할당하고, x좌표를 두 번째 인덱스에 할당한다.

백준 2606: 바이러스

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

문제 분석

바이러스가 걸린 컴퓨터와 연결된 컴퓨터는 바이러스에 걸리게 되며, 1번 컴퓨터에 의해 바이러스가 걸리는 컴퓨터의 수를 출력하는 문제이다. 여러 갈래로 컴퓨터들이 연결되어 있으므로 그래프 관련 문제라 생각했고, 1번 컴퓨터에 의해 바이러스가 걸린 컴퓨터 수를 출력하는 문제이므로 DFS 방식, BFS 방식 모두 사용 가능하다 판단해서 인접 행렬을 이용한 그래프와 재귀를 이용한 DFS 방식을 사용했다.

처음 작성한 코드

#include <iostream>

using namespace std;

int computer[101][101] = { 0, };
bool virus[101];
int com, edges, cnt = 0;

void dfs(int v) {
    virus[v] = true;

    for (int i = 0; i < com; i++) {
        if (!virus[i] && computer[v][i] == 1) {
            dfs(i);
            cnt++;
        }
    }
}

int main(void) {
    int c1, c2;
    cin >> com >> edges;

    for (int i = 0; i < edges; i++) {
        cin >> c1 >> c2;
        computer[c1][c2] = 1;
        computer[c2][c1] = 1;
    }

    dfs(1);
    cout << cnt;
}

위 코드가 틀린 이유를 계속 찾다가 dfs 함수 내부 for문의 조건식이 이상하다는 것을 알았다. 예를 들어서, com이 7로 입력되었을 경우, 컴퓨터1 ~ 컴퓨터7까지 존재하는 것인데 나는 컴퓨터0 ~ 컴퓨터6까지 반복문을 돌리고 있었던 것이다...

아래는 수정한 코드이다

수정한 코드

#include <iostream>

using namespace std;

int computer[101][101] = { 0, };
bool virus[101];
int com, edges, cnt = 0;

void dfs(int v) {
    virus[v] = true;

    for (int i = 1; i <= com; i++) {
        if (!virus[i] && computer[v][i] == 1) {
            dfs(i);
            cnt++;
        }
    }
}

int main(void) {
    int c1, c2;
    cin >> com >> edges;

    for (int i = 0; i < edges; i++) {
        cin >> c1 >> c2;
        computer[c1][c2] = 1;
        computer[c2][c1] = 1;
    }

    dfs(1);
    cout << cnt;
}