1. 문제 이해 및 설계 범위 확정 : 3분~10분
2. 개략적 설계안 제시 및 동의 구하기 : 10분~15분
3. 상세 설계 : 15분~25분
4. 마무리 : 3분~5분

해야할것

• 질문하기
• 문제의 요구사항 이해
• 정답이라고 확신하지 말것
• 면접관과 소통해라
• 가능하다면 여러해법을 제시해라
• 개략적 설계에 면접관이 동의하면, 세부사항을 설명해라
• 면접관의 아이디어를 이끌어내라
• 포기하지 말라

하지 말아야 할 것

• 전형적인 면접 문제에는 대비
• 요구사항이나 가정들을 분명히 하지않은 상태에서 설계를 제시하지 마라
• 처음부터 특정 컴포넌트의 세부사항을 너무 깊이 설명하지 마라
• 진행 중에 막혔다면, 힌트를 청하기 주저하지 말라
• 의견을 일찍, 그리고 자주 구해라

2의 제곱수

데이터 볼륨단위

최소 단위는 1byte, 8bit로 구성 ASCII 문자 하나가 차지하는 메모리 크기가 1바이트

응답지연 값

• 메모리는 빠르지만 디스크는 아직도 느리다.
• 디스크 탐색(seek)은 가능한 한 피해라
• 단순한 압축 알고리즘은 빠르다.
• 데이터를 인터넷으로 전송하기 전에 가능하면 압축해라
• 데이터 센터는 보통 여러지역에 분산되어 있고, 센터들 간에 데이터를 주고받는데는 시간이 걸린다.

  가용성에 관계된 수치들

  고가용성 (High Availability)
• 오랜 시간동안 지속적으로 운영될 수 있는 능력
• 퍼센트로 표현. 100%는 시스템이 한번도 중단된적 없었음을 의미

SLA (Service Level Agreement)

• 서비스 사용자가 보편적으로 사용하는 용어
• 서비스 사업자와 고객 사에에 맺어진 합의
• 9가 많을 수록 좋다고 보면됨

면접 팁

• 근사치를 활용한 계산 : 계산 결과의 정확함을 평가하는게 아니라면 적절한 근사치를 활용해 시간 절약
• 가정을 적어둬라
• 단위를 붙여라
• 많이 출제되는 개략적 규모 추정 문제는 QPS, 최대 QPS, 저장소 요구량, 캐시 요구량, 서버 수 등을 측정하는 것이다.

복잡한 시스템을 구상하기 전, 기본적으로 다음과 같은 시스템 구조로 시작할 수 있다.

데이터 베이스

데이터베이스 종류

관계형 DB

• 자료를 테이블과 열, 칼럼으로 표현
• SQL을 사용해 데이터를 INSERT, DELETE, UPDATE, JOIN 등을 할 수 있다.

  NoSQL DB

• 키-값 저장소, 그래프 저장소, 칼럼 저장소, 문서 저장소가 대표적으로 있다.

  언제 NoSQL DB를 사용할까?

• 아주 낮은 응답 지연시간이 요구될때 (RDB에서 Join을 통해 시간이 오래걸릴 수 있음)
• 다루는 데이터가 비정형(unstructured) 이라 관계형 데이터가 아님 (이미지, 비디오, 웹페이지와 같은 경우)
• 데이터(JSON, YAML, XML 등)를 직렬화하거나 역직렬화 할 수 있기만 하면됨

• 데이터 직렬화 : 데이터를 JSON, YAML, XML과 같은 형식으로 변환

• 데이터 역직렬화 : 직렬화된 데이터를 원래의 데이터 형태로 복원하는 과정

수직적 규모 확장 vs 수평적 규모 확장

수직적 규모 확장

• 서버의 성능 향상 (더 좋은 CPU, 더 좋은 RAM)
• 한계가 있음. 무한대로 CPU, RAM을 추가할 수 없다.
• 하나의 서버로 운영되어서 자동복구(failover)/다중화(redundancy) 방안이 없다. -> 서버에 장애가 발생하면 웹사이트/앱은 완전히 중단됨

  수평적 규모 확장

• 서버의 대수를 증가

• 로드밸런서 도입

• 데이터베이스 다중화

  로드밸런서

  
• 로드밸런서의 public IP 주소로 접속

• 클라이언트는 직접 웹 서버로 접근하지 않는다.

• 서버간 통신에는 private IP 주소 이용 (private IP : 같은 네트워크에 속한 서버 사이의 통신에만 쓰일 수 있음)

• 이점

• 서버 1이 다운되어도 서버2를 사용하면 됨. 웹 사이트 전체가 다운되는 일이 방지된다.

• 부하를 나누기 위해 새로운 서버 추가 가능

데이터베이스 다중화

• 주(master)-부(slave) 관계 설정

• 주데이터 서버 : 쓰기 연산 (write operation)

• 부데이터 서버 : 읽기 연산 (read operation)

• 이점

• 더 나은 성능 : 쓰기,읽기 연산을 분산시켜 처리할 수 있는 쿼리가 늘어나므로 성능이 좋아진다.

• 안전성(reliability) : 데이터를 지역적으로 떨어진 여러 장소에 다중화를 시켜서 자연재해 등으로 데이터 베이스 서버 일부가 다운되어도 데이터는 보존된다.

• 가용성(availability) : 하나의 데이터베이스 서버에 장애가 발생해도 다른 서버에 있는 데이터를 가져와 계속 서비스 가능

• 대응방법

• 부서버가 한대인데 다운 : 주서버가 임시적으로 읽기연산 받음. 이후 새로운 부서버가 장애 서버를 대체

• 부서버 여러대인 경우 다운 : 다른 부서버가 읽기연산 처리. 이후 새로운 부서버가 장애 서버를 대체

• 주서버 다운 : 만약 하나의 부서버만 있다면 이게 주서버가 되면서 모든 연산 처리. 이후 새로운 부서버 추가. 부서버 데이터가 최신 상태가 아니면 복구 스크립트 추가 (다중마스터, 원형다중화를 도입하면 이런 상황 대처할 수 있음)

  캐시

  값비싼 연산결과 또는 자주 참조되는 데이터를 메모리 안에 두고, 뒤이은 요청이 보다 빨리 처리될 수 있도록 하는 저장소

• 이를 읽기 주도형 캐시 전략 이라고 한다.

• 캐시할 데이터 종류, 크기, 액세스 패턴에 맞는 캐시 전략을 선택하면 된다.

• 캐시 서버는 주로 API를 이용해 사용한다.

  주의할점

• 데이터 종류 : 캐시는 휘발성 메모리에 두어서 영속적으로 보관할 데이터는 저장하지 않는다.

• 만료 (expire) 정책 : 만료된 데이터는 캐시에서 삭제된다. 따라서 캐시 데이터 관리를 위해 만료 정책이 필요하다.

• 만료기한 짧음 : 데이터베이스를 너무 자주 읽는다.

• 만료기한 너무 김 : 원본 데이터와 차이가 날 수 있다.

• 일관성 : 저장소의 원본은 갱신하는 연산과 캐시를 갱신하는 연산이 단일 트랜잭션으로 처리되지 않을때 일관성 깨질 수 있음

• 장애대응 : 캐시 서버 한대만 두면 단일 장애 지점 (Single Poing Of Failure, SPOF)가 되어버릴 수 있다. -> 캐시 서버 분산

• 캐시 메모리

• 너무 작음 : 데이터가 너무 자주 캐시에서 밀려난다. 성능 떨어짐

• 따라서 캐시 메모리를 과할당(overprovision)하는게 좋다.

• 데이터 방출(eviction)정책 : 캐시가 꽉차면 데이터 방풀을 해야한다.

• LRU(Least Recently Used) : 마지막으로 사용된 시점이 가장 오래된 데이터를 내보내는 정책

• LFU(Least Frequently Used) : 사용 빈도가 가장 낮은 데이터를 내보내는 정책

• FIFO(First In First Out) : 가장 먼저 들어온 데이터를 가장 먼저 내보내는 정책

  콘텐츠 전송 네트워크 (CDN)

• 정적 콘텐츠 전송 시 사용하며, 지리적으로 분산 된 서버의 네트워크

• 이미지, 비디오, CSS, JavaScript 파일 등 캐시

  고려사항

• 비용 : 보통 third-party providers에 의해 운영. 따라서 자주 사용되지 않는 콘텐츠는 CDN에서 제외

• 적절한 만료 시한 설정 : time-sensitive 콘텐츠는 만료 시점을 잘 정해야한다. 너무 길면 콘텐츠의 신선도가 떨어지고, 너무 짧으면 원본 서버에 빈번히 접속함

• CDN 장애 대처 : 클라인트 측에서 CDN이 장애나면 원본 서버로부터 데이터를 가져오도록 구성할 수 있다.

• 콘텐츠 무효화

• CDN 서비스 사업자가 제공하는 API를 이용해 콘텐츠 무효화

• 콘텐츠의 다른 버전을 서비스하도록 object-versioning 이용. URL 마지막에 버전 번호를 인자로 주면됨. (ex : image.png?v=2)

  무상태(stateless) 웹 계층

  웹 계층을 수평적으로 확장하는 방법

• 상태 정보(사용자 세션 데이터와 같은)를 웹 계층에서 제거

• 상태정보를 관계형 데이터베이스나 NoSQL, Memcached/Redis 같은 캐시 시스템에 보관하고 필요할때 갖고옴

  데이터 센터

• 장애가 없는 상황에서 사용자는 가장 가까운 데이터 센터로 안내된다. 이것을 지리적 라우팅이라고 함. (geoDNS : 사용자의 위치에 따라 도메인 이름을 어떤 IP 주소로 변환할지 결정할 수 있도록 하는 DNS 서비스)

• 데이터 센터를 이용하면 하나에 시미각한 장애가 발생하면 모든 트래픽은 장애가 없는 데이터 센터로 전송된다.

고려사항

• 트래픽 우회 : 올바른 데이터 센터로 트래픽을 보내는 효과적인 방법을 찾아야함. 지리적으로 고려하는 건 GeoDNS 이용
• 데이터 동기화(synchronization) : 한곳에 장애가 났을때 다른곳에서 동일한 데이터를 사용하기 위해서는 데이터를 여러 데이터센터에 다중화를 한다.
• 테스트와 배포 : 자동화된 배포 도구는 모든 데이터 센터에 동일한 서비스가 설치되도록 하는데 중요한 역할

메세지 큐

• 메세지의 무손실을 보장하는 비동기 통신(asynchronous communication)을 지원하는 컴포넌트이다.
• 서비스 또는 서버 간 결합이 느슨해져서 규모 확장성이 보장되어야 하는 안정적 애플리케이션을 구상하기 좋다.
• 사용예

• 사진 보정 애플리케이션 : 보정은 시간이 오래 걸리니깐 비동기적으로 처리하면 편하다.

  로그, 메트릭 그리고 자동화

• 로그 : 에러 로그를 모니터링 하면 시스템의 오류와 문제들을 보다 쉽게 찾아낼 수 있다. 로그를 단일 서비스로 모아주는 도구를 사용하면 더 편리하게 검색 해볼 수 있다. (ex : Avo)
• 메트릭 : 사업현황에 관한 유용한 정보 + 시스템의 현재 상태 파악

• 호스트 단위 메트릭 : CPU, 메모리, 디스크 I/O에 관한 메트릭

• 종합 메트릭 : 데이터베이스 계층의 성능, 캐시 계층의 성능

• 핵심 비지니스 메트릭 : 일별 능동 사용자, 수익, 재방문

• 자동화

• 지속적 통합 (Continuous Integration)을 도와주는 도구를 활용하면 개발자가 만드는 코드가 어떤 검증 절차를 자동으로 거치도록 할 수 있어 문제를 쉽게 감지

• 빌드, 테스트, 배포 등의 절차를 자동화할 수 있어서 개발 생산성 향상

  데이터베이스의 규모확장

  수직적 확장

• 기존 서버에 고성능 자원 증설

  문제점

• 데이터베이스 서버 하드웨어에는 한계가 있다.
• SPOF(Single Poing Of Failure)로 인한 위험성
• 비용이 많이 든다.

수평적 확장

샤딩

• 대규모 데이터베이스를 shard 라고 부르는 작은 단위로 분할하는 기술
• 모든 샤드는 같은 스키마를 쓰지만 샤드에 보관되는 데이터 사이에는 중복이 없다.

고려사항

• 데이터의 재샤딩해야하는 경우

• 데이터가 너무 많아져서 하나의 샤드로는 더이상 감당하기 어려울때

• 샤드 간 데이터 분포가 균등하지 못해서 어떤 샤드에 할당된 공간소모가 다른 샤들에 비해 빨리 진행될때 (샤드 소진). 샤드 키 변경하고 데이터 재배치 해야됨

• 유명인사 문제

• 특정 샤드에 질의가 집중되어 서버에 과부하가 걸리는 문제

• 케이티페리, 저스틴비버와 같은 유명인사가 전부 같은 샤드에 저장되면 과부하가 될 수 있음

• 유명인사 각각에 샤드 할당 / 더 잘게 쪼개기

• 조인과 비정규화

• 하나의 데이터베이스를 여러 샤드 서버로 쪼개면, 조인하기 어려움.

• 데이터베이스를 비정규화. 하나의 테이블에서 질의가 수행되도록 한다.

요약

• 웹 계층은 무상태 계층으로
• 모든 계층에 다중화 도입
• 가능한 한 많은 데이터를 캐시할 것
• 여러 데이터 센터를 지원할 것
• 정적 콘텐츠는 CDN을 통해 서비스 할 것
• 데이터 계층은 샤딩을 통해 그 규모를 확장할 것
• 각 계층은 독립적 서비스로 분할할 것
• 시스템을 지속적으로 모니터링하고, 자동화 도구들을 활용할 것

Defaulting to user installation because normal site-packages is not writeable

이러한 에러가 발생할 때가 있다. 일반 사이트패키지를 쓸 수 없다는 말인데 이것의 원인은 두가지가 있다.

1. 서버 환경에 여러개의 python이 설치된 경우
2. 접근 권한이 없는 경우

1번의 경우에는 인터프리터를 정확히 명시해서 install을 진행하면 된다. 나는 Python3의 버전이 여러개여서 다음과 같이 표기하였다.

python3.9 -m pip install <패키지명>

python3 버전이 하나라면 다음과 같이 표기하면 된다.

python3 -m pip install <패키지명>

참고

과연 충돌해결 밑의 메뉴 는 어디에 있을까

워크스페이스 > 파일상태 > 충돌난 파일 오른쪽 클릭 > 충돌 해결하기

여기에서

• '내것'을 이용해 해결
• '저장소'것을 사용하여 해결

두가지가 뜰텐데, 어느것으로 병합하고 싶은지 선택하면 된다. 나는 저장소것을 선택했다.

local branch가 remote branch 보다 커밋이 앞서 있어서 발생

아래와 같은 에러메세지가 출력이 된다.

git pull 안되는 문제 해결

에러메세지가 알려준 힌트를 따른다.

git config pull.rebase false : pull 할때 rebase 하지 않고 merge 한다. git config pull.rebase true : pull 할때 rebase 한다. git config pull.ff only : fast-foward일때만 pull을 허용한다.

하지만, _Fatal: Not possible to fast-forward, aborting / fatal: 정방향이 불가능하므로, 중지합니다. _ 이러한 에러가 떠버렸다.

Not possible to fast-foward, aborting 해결

1) git pull --rebase로 해결한다. 2) 근본적인 해결 git pull 문제 해결에서 세번째 명령(git config pull.ff only)은 fast-forward만 하겠다는 것이다. 이 경우 merge가 불가능하고, merge가 필요한 경우에는 정방향으로 진행하는게 불가능하다는 에러 메세지가 뜨면서 진행을 하지 않는다. 따라서 근본적으로 해결하려면 fast-forward only 옵션을 아래 명령을 이용해 끄면된다.

git config --unset pull.ff

참고 : https://sanghye.tistory.com/43

효율성 검사가 있어서 그런가 체감상 level2보다 어렵게 느껴졌다.

다시한번 문자열에 약하다는 걸 느꼈고 덕분에 새로운 구현 방식도 알게되었다!!

1차시도

1. query를 띄어쓰기 단위로 끊어 벡터에 저장
2. info를 띄어쓰기 단위로 끊어 벡터에 저장
3. 해당 query를 모든 info를 돌면서 만족하는 info가 발생할때마다 카운트

-> 시간복잡도 O(N^2) 발생

#include <string>
#include <vector>
#include <string.h>
#include <iostream>

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;

    for(int i=0; i<query.size(); i++)
    {
        char ch[query[i].size()];
        strcpy(ch, query[i].c_str());
        char *ptr = strtok(ch, " ");
        vector <string> v;
        v.clear();
        while(ptr != NULL)
        {
            v.push_back(string(ptr));
            ptr = strtok(NULL, " ");
        }

        int cnt = 0;
        for(int j=0; j<info.size(); j++)
        {
            char c[info[j].size()];
            strcpy(c, info[j].c_str());
            char *pt = strtok(c, " ");
            vector <string> i;
            i.clear();

            while(pt != NULL)
            {
                i.push_back(string(pt));
                pt = strtok(NULL, " ");
            }

            int l = 0;
            for(int k=0; k<i.size(); k++)
            {
                if(k==4 && stoi(i[k]) >= stoi(v[v.size()-1])) {
                    cnt++; 
                }
                else {
                    if(v[k*2]=="-") {continue;}
                    if(i[k] == v[k*2]) continue;
                    else break;
                }
            }
        }
        answer.push_back(cnt);
    }
    return answer;
}

이렇게 했는데 segmentation fault가 겁나 많이 떠버림.. 이 방법을 고쳐볼까 했지만 어차피 효율성이 꽝일거라 예상 되어서 다른 방법을 찾았다.

2차시도

효율성을 줄이기 위해서는 score 정렬이 필요하다고 생각되었다. 이것외에는 방법이 떠오르지 않아 구글링을 하였다.

참고코드

구현

1. info 파싱

-를 포함한 모든 경우의 수 map에 넣어주기 2. 이분탐색을 위해 score 기준으로 각각의 map 정렬 3. query 파싱 띄어쓰기를 제외한 문자열을 모두 합해줌 4. query 문자열로 info map에서 조건의 만족하는 경우의 수를 찾음 lower_bound() 사용

코드

#include <string>
#include <vector>
#include <unordered_map>
#include <sstream>
#include <algorithm>

using namespace std;
unordered_map <string,vector<int>> um;

void addCases(string *s, int score)
{
    for(int i=0; i<16; i++)
    {
        string str="";
        int num = i;
        for(int j=3; j>=0; j--)
        {
            if(num <= 0 || num%2 == 0)
            {
                str = "-" + str;
            }
            else str = s[j] + str;
            num /= 2;
        }
        um[str].push_back(score);
    }
}
vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    string s[4], str="";

    for(int i=0; i<info.size(); i++)
    {
        istringstream stt(info[i]);
        stt >> s[0] >> s[1] >> s[2] >> s[3] >> str;
        addCases(s, (int)stoi(str));
    }

    for(auto itr = um.begin(); itr!=um.end(); itr++)
    {
        sort(itr->second.begin(), itr->second.end());
    }

    for(int i=0; i<query.size(); i++)
    {
        istringstream stt(query[i]);
        stt >> s[0] >> str >> s[1] >> str >> s[2] >> str >> s[3] >> str;
        int score = (int)stoi(str);

        vector <int> v = um[s[0]+s[1]+s[2]+s[3]];
        if(v.size()!=0)
        {
            int idx = lower_bound(v.begin(), v.end(), score) - v.begin();
            answer.push_back(v.size() - idx);
        }
        else answer.push_back(0);
    }
    return answer;
}

C++ 문법

1. 문자열 나누기

크게 두가지 방식으로 나눌 수 있다. 문자열 나누는 2가지 방법

이 중 나는 무조건 istringstream 방식을 사용하기로 했다. (예외 : 문자열 구분자 2개 이상이면 strtok 사용)

istringstream 사용 방법

위의 블로그에서도 알 수 있듯이 stringstream은 공백과 '\n'을 제외하고 문자열에서 맞는 자료형의 정보를 빼낸다. 따라서 다음과 같이 아주 간편하게 문자열을 분리할 수 있다. 꼭 기억해놔야하는 문법이다.

istringstream stt(query[i]);
stt >> s[0] >> str >> s[1] >> str >> s[2] >> str >> s[3] >> str;

2. map 사용법

카카오 문제를 풀기 전까지는 Map을 그다지 많이 사용하지 않았는데 이제는 거의 매번 사용하는 것 같다.

unordered_map <string,vector<int>> um;
vector <int> v = um[s[0]+s[1]+s[2]+s[3]];

이번에 알게된 방법 (위 코드 참고)

1) 동일한 string에 대해 int값을 여러개 삽입하는데 아주 유용하다. 2) 값이 아주 많거나 효율적으로 사용해야하는 경우 unordered_map을 사용할 수 있다. unordered_map 사용법 3) map의 second 자료형이 vector인 경우에 vector에 할당가능 (이건 당연한 소리임. 근데 이걸 여지껏 안 이용했다는게 좀 충격)

그러면 왜 unordered_map이 효율적인가?

unordered_map은 해쉬테이블로 구현한 자료구조로 탐색시간복잡도는 O(1)이 된다. 반면 map은 Binary Search Tree로 탐색 시간 복잡도는 O(logn n)이다. 따라서 unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을시 월등히 좋은 성능을 보인다. 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수 있다.

문제는 다음과 같다. 단체사진 찍기

처음에 봤을땐 확률과 통계 풀듯이 뭐 N과 F사이에 0을 넣어줘야되나? 뭐 이런 생각이 들었다.

하지만 이건 사람이나 할수있는 일이고 컴퓨터로는 모든 경우의 수에 대해서 조건만 맞는지 확인해주면 된다.

구현

1. 입력받은 data를 따로 저장
2. 조합으로 얻은 string 과 data의 조건이 일치한지 확인

C++ 문법

1. 모든 조건을 찾는건 next_permutation() 을 사용하였다. next_permutation는 string에서도 잘 적용됨을 확인할 수 있다.
2. string으로 입력될때 숫자도 문자임을 주의하자. 0의 아스키코드는 48이다. int diff = nowStr[4]-48;

코드

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool isRight(int diff, int real, char sign)
{
    if(sign == '=') return diff == real;
    else if(sign == '<') return real < diff;
    else if(sign == '>') return real > diff;
}
int solution(int n, vector<string> data) {
    int answer = 0;
    string friends = "ACFJMNRT";
    do{
        bool flag = true;
        for(int i=0; i<n; i++)
        {
            string nowStr = data[i];
            char f = nowStr[0];
            char s = nowStr[2];
            char sign = nowStr[3];
            int diff = nowStr[4]-48;

            int fIdx = -1, sIdx = -1;
            for(int j=0; j<8; j++)
            {
                if(friends[j] == f) fIdx = j;
                else if(friends[j] == s) sIdx = j;
            }
            int tmpDiff = abs(fIdx-sIdx)-1;
            if(!isRight(diff, tmpDiff, sign)) {
                flag=false;
                break;
            }
        }
        if(flag) answer++;
    }while(next_permutation(friends.begin(), friends.end()));
    return answer;
}

문제는 다음과 같다. 메뉴 리뉴얼

어떻게 풀었는가?

1. next_permutation()으로 조합구함
2. map에 해당 문자열을 추가하고 문자열 등장 횟수 확인
3. 가장 많이 나온 문자열을 출력

조건

1. 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함한다.
2. 2명 이상의 코스요리가 없을 경우에는 해당 개수의 코스요리는 출력하지 않는다.
3. 가장 많이 주문된 메뉴 구성이 여러개라면, 모두 배열에 담아 return 한다.
4. 오름차순으로 정렬해서 return 한다.

구현

1. 해당 손님이 시킨 단품메뉴의 개수만큼 vector를 할당한다. (len)
2. 구해야하는 코스요리의 개수(cnt)만큼 vector에 true를 할당한다.
3. 이 vector에 대해서 next_permutation을 반복한다. -> 조합구하기
4. 조합을 구해 true인 문자를 모아 문자열로 만들고 map 사용
   • 이미 있는 문자열 -> m[tmp]++;
   • 없는 문자열 -> m.insert({tmp,1});
5. 가장 많이 나온 문자열을 answer에 추가한다.

1~5 반복하면됨

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
map <string,int> m;

vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    for(int i=0; i<course.size(); i++)
    {
        int cnt = course[i];
        for(int j=0; j<orders.size(); j++)
        {
            int len = orders[j].length();
            if(len < cnt) continue;
            sort(orders[j].begin(), orders[j].end());
            vector <bool> v(len-cnt, false);
            v.insert(v.end(), cnt, true);

            do{
                string tmp = "";
                for(int k=0; k<len; k++)
                {
                    if(v[k]){
                        tmp += orders[j][k];
                    }
                }
                if(m.find(tmp) == m.end()){
                    m.insert({tmp,1});
                }
                else{
                    m[tmp]++;
                }
            }while(next_permutation(v.begin(), v.end()));
        }
        int maxCnt = 0;
        for(auto itr=m.begin(); itr!=m.end(); itr++)
        {
            if(maxCnt < itr->second) maxCnt = itr->second;
        }
        if(maxCnt==1) continue;
        for(auto itr=m.begin(); itr!=m.end(); itr++)
        {
            if(maxCnt == itr->second)
            {
                answer.push_back(itr->first);
            }
        }
        m.clear();
    }
    sort(answer.begin(), answer.end());
    return answer;
}

문제는 다음과 같습니다. 자물쇠와 열쇠

조건

1. key의 크기 M은 lock의 크기 N 이하이다.
2. key는 이동과 회전이 가능하다. (90,180,270도 모두 가능)
3. key의 돌기부분(1)과 자물쇠의 홈 부분(0)이 일치해야 한다.
4. 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있다.

조건이 참 많은 구현문제입니다. key의 이동과 회전에 대해서 어떻게 짜야할지 감이 안 잡혀 다음의 티스토리를 참고했습니다. 참고

구현과정

1. 배열을 N+2(M-1)로 만듭니다. key가 이동이 가능하기 때문에 lock에 일부만 걸쳐있을 수 있습니다. 따라서 열쇠가 이동가능한 영역은 N+2(M-1) X N+2(M-1) 가 됩니다. => *solution() 참고**
2. 1에서 구한 배열에 lock 부분 할당하기 확장된 배열의 중앙에 lock을 할당합니다. lock이 아닌부분 -> 2 lock인 부분 -> 0/1 lock의 시작좌표 : (0,0) -> (M-1, M-1) lock의 종료좌표 : (N,N) -> (배열크기-M, 배열크기-M) => make_MAP() 참고
3. key, lock을 비교
   • key (0), lock (0) -> 틀림
   • key (1), lock (1) -> 틀림
   • key (1), lock (0) -> 맞음 => isUnlock() 참고
4. key의 이동 key는 N+M-1 만큼 오른쪽, 아래로 움직일 수 있음 => move_key() 참고
5. key의 회전 시계방향으로 90도 회전하면 (y,x) <- (M-1-x,y) => rotate_key() 참고

코드

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

using namespace std;

vector<vector<int>> MAP;
int N, M, Size, sum;

void make_MAP(vector<vector<int>> lock)
{
    int y = 0, x = 0;
    for(int i=M-1; i<Size-M+1; i++, y++)
    {
        for(int j=M-1; j<Size-M+1; j++, x++)
        {
            if(lock[y][x]==0) {MAP[i][j] = 0; sum++;}
            else MAP[i][j] = 1;
        }
        x=0;
    }
}
int isUnlock(int y, int x, vector<vector<int>> key)
{
    int idx_x = 0, idx_y = 0;
    int cnt = 0;
    for(int i=y; i<y+M; i++, idx_y++)
    {
        for(int j=x; j<x+M; j++, idx_x++)
        {
            if(key[idx_y][idx_x]==0 && MAP[i][j]==0) return -1;
            if(key[idx_y][idx_x]==1 && MAP[i][j]==1) return -1;
            if(key[idx_y][idx_x]==1 && MAP[i][j]==0) cnt++;
        }
        idx_x=0;
    }

    return cnt;
}
void rotate_key(vector<vector<int>> &key)
{
    vector<vector<int>> tmp = key;
    for(int i=0; i<M; i++)
    {
        for(int j=0; j<M; j++)
        {
            tmp[i][j] = key[M-1-j][i];
        }
    }
    key = tmp;
}
bool move_key(vector<vector<int>> key)
{
    for(int i=0; i<4; i++)
    {
        //시작칸수
        for(int j=0; j<M+N-1; j++)
        {
            for(int k=0; k<M+N-1; k++)
            {
                if(isUnlock(j,k,key)==sum)
                {
                    return true;
                }
            }
        }
        rotate_key(key);
    }
    return false;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    M = key.size();
    N = lock.size();
    Size = N+(M-1)*2;
    MAP.resize(Size, vector<int>(Size,2));

    make_MAP(lock);
    if(!move_key(key)) answer = false;
    return answer;
}

c++ 문법

• 2차원 배열 -> vector <vector<int>> v (크기를 모를때 int arr[][] 보다 좋은 듯)
• vector 크기 지정 및 값 할당

1. 선언시 할당 vector<int> vec(5,1)
2. 재할당 or 선언 이후 할당 vec.resize(10,2)

[resize 주의할점] resize하며 더 커지는 경우에만 값이 들어간다. 더 작아지는 경우에는 크기만 작아지고 값이 할당되지는 않는다.

이 코드에서는

  MAP.resize(Size, vector<int>(Size,2));

이렇게 사용하였다. 2차원 vector를 size만큼 지정하고 vector (size,2)의 값을 할당한다는 의미 즉 모든 값을 2로 할당

스터디원에게 누적합이라는 힌트를 얻고 BOJ 21318 위 문제를 통해 누적합 감을 잡고 다시 개똥벌레를 풀어보았지만,,,,, 모든 높이를 점검해보는 방법(결국에 이방법으로 풀음)밖에 생각이 안나서 구글링을 해보았다...🤓

참고코드 upper_bound / lower_bound를 사용해서 해결했다!!

C++의 이분탐색

c++에서는 이진탐색으로 원소를 탐색하는 lower_bound / upper_bound를 사용한다.

배열 또는 리스트가 정렬되어있어야한다

이 조건이 성립되어야 사용가능하다.

이진탐색을 사용하기 위한 조건과 같다는 점을 알 수 있다.

또한 이진탐색의 원리를 갖고있기 때문에 O(logN) 시간복잡도를 갖습니다.

lower_bound

• 이 함수는 찾고자 하는 key값과 크거나 같은 원소의 위치를 구하는 것 입니다.
• 같은 원소가 여러개 있어도 유일한 해를 찾을 수 있습니다.
• 사용방법

  template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
  

lower_bound(v.first(), v.end(), 4);
이런식으로 사용합니다.



### upper_bound
- key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
- 같은 원소가 여러개 있어도 유일한 해를 찾을 수 있습니다.
- 사용방법

template <class ForwardIterator, class T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

upper_bound(v.first(), v.end(), 4);
이런식으로 사용합니다.

1. 순차탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

#include <bits/stdc++.h>

using namespace std;

// 순차 탐색 소스코드 구현
int sequantialSearch(int n, string target, vector<string> arr) {
    // 각 원소를 하나씩 확인하며
    for (int i = 0; i < n; i++) {
        // 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if (arr[i] == target) {
            return i + 1; // 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)
        }
    }
    return -1; // 원소를 찾지 못한 경우 -1 반환
}

int n; // 원소의 개수
string target; // 찾고자 하는 문자열
vector<string> arr;

int main(void) {
    cout << "생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요." << '\n';
    cin >> n >> target;

    cout << "앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다." << '\n';
    for (int i = 0; i < n; i++) {
        string x;
        cin >> x;
        arr.push_back(x);
    }

    // 순차 탐색 수행 결과 출력
    cout << sequantialSearch(n, target, arr) << '\n';
}

순차탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점이 특징이다.

따라서 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 순차탐색의 최악의 경우 시간 복잡도는 O(N)이다.

2. 이진탐색

이진탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

• 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.

• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.

• 위치를 나타내는 변수 3개 : 시작점, 끝점, 중간점

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다

전체 데이터의 개수는 16개지만, 이진 탐색을 이용해 총 4번의 탐색으로 원소를 찾을 수 있었다.

이진탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간복잡도가 O(logN)이다.

절반씩 데이터를 줄어들도록 만든다는 점은 다른 퀵정렬과 공통점이 있다.

재귀함수 이용

#include <bits/stdc++.h>

using namespace std;

// 이진 탐색 소스코드 구현(재귀 함수)
int binarySearch(vector<int>& arr, int target, int start, int end) {
    if (start > end) return -1;
    int mid = (start + end) / 2;
    // 찾은 경우 중간점 인덱스 반환
    if (arr[mid] == target) return mid;
    // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
    // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else return binarySearch(arr, target, mid + 1, end);
}

int n, target;
vector<int> arr;

int main(void) {
    // n(원소의 개수)와 target(찾고자 하는 값)을 입력받기 
    cin >> n >> target;
    // 전체 원소 입력받기 
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    // 이진 탐색 수행 결과 출력 
    int result = binarySearch(arr, target, 0, n - 1);
    if (result == -1) {
        cout << "원소가 존재하지 않습니다." << '\n';
    }
    else {
        cout << result + 1 << '\n';
    }
}

반복문 이용

#include <bits/stdc++.h>

using namespace std;

// 이진 탐색 소스코드 구현(반복문)
int binarySearch(vector<int>& arr, int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;
        // 찾은 경우 중간점 인덱스 반환
        if (arr[mid] == target) return mid;
        // 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        else if (arr[mid] > target) end = mid - 1;
        // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else start = mid + 1; 
    }
    return -1;
}

int n, target;
vector<int> arr;

int main(void) {
    // n(원소의 개수)와 target(찾고자 하는 값)을 입력 받기 
    cin >> n >> target;
    // 전체 원소 입력 받기 
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    // 이진 탐색 수행 결과 출력 
    int result = binarySearch(arr, target, 0, n - 1);
    if (result == -1) {
        cout << "원소가 존재하지 않습니다." << '\n';
    }
    else {
        cout << result + 1 << '\n';
    }
}

코딩 테스트에서의 이진탐색

이진탐색 코드는 가급적이면 외우는 걸 권장한다.

이진탐색의 원리는 다른 알고리즘에서도 폭넓게 적용되는 원리와 유사하기 때문에 매우 중요하다.

또, 높은 난이도의 문제에서는 이진 탐색 알고리즘이 다른 알고리즘과 함께 사용되기도 한다.

더불어 코딩테스트의 이진탐색문제는 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많다.

따라서 2000만을 넘어가면 이진 탐색으로 문제에 접근해보길 권한다.

처리해야 할 데이터의 개수나 값이 1000만 단위 이상으로 넘어가면 이진탐색과 같이 O(logN)의 속도를 내야하는 알고리즘을 떠올려야 문제가 풀린다!!

트리 자료구조

이진 탐색은 전제 조건이 데이터 정렬이다.

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다.

따라서 데이터베이스에서의 탐색은 이진 탐색과는 조금 다르지만, 이진 탐색과 유사한 방법을 이용해 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠르다.

특징

• 트리는 부모노드와 자식노드의 관계로 표현한다.
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드를 단말 노드라고 한다.
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다.

그렇다면 이런 트리 구조를 이용하면 정확히 어떤 방식으로 항상 이진 탐색이 가능할 걸까?

이진 탐색 트리

이진탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.

특징

• 부모 노드보다 왼쪽 자식 노드가 작다.

• 부모 노드보다 오른쪽 자식 노드가 크다.

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

참고자료 : 이것이 코딩테스트다 (저자 : 나동빈)

자료구조는 컴퓨터 과학에서 자료의 효율적인 접근 및 수정을 할 수 있도록 컴퓨터에 자료를 조직, 관리, 저장하는 방법이다. 더 정확히 말해, 자료구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다.

https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

2. 분류

• 단순구조(Simple Structure)

  자료값을 사용하기 위해서 True/False, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형

• 선형구조(Linear Structure)

  자료를 구성하는 데이터를 순차적으로 나열시킨 형태

  자료들간의 관계가 1:1인 자료

• 비선형구조(Nonlinear Structure)

  하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것을 의미

  계층구조나 망구조를 갖는 자료구조로서 트리(Tree)와 그래프(Graph)가 있다.

• 파일구조(File Structure)

  서로 관련있는 필드(Field)로 구성된 레코드(record) 집합인 파일에 대한 자료구조로 보조 기억장치에 데이터가 실제로 기록되는 형태

  메모리에 한번에 올릴 수 없는 대용량을 다룬다.

  순차적 파일구조(sequential file structure), 색인 파일구조(indexed sequential file structure), 직접파일(direct file) 등이 있다.

3. 추가

• 추상적 자료형

  자료 자체의 형태, 그 자료의 연산을 수학적으로만 정의한 것.

  Ex ) 스택 -> 추상적 자료형에서는 pop, push, empty, size 연산 정도를 정의할 수 있다. 하지만 스택이 내부적으로 배열인지 연결리스트로 구현되는지와 같은 세부적인 형태는 추상적 자료형에서 다루지 않음

  • 예) 집합, 리스트, 스택, 큐, 트리

  • 자료구조와 차이점

    조금이라도 구현방법이 있다면 자료구조 !!

    스택, 큐 -> 추상적 자료형

    콜 스택, 배열, 연결리스트 -> 자료구조

    추상적 자료형과 자료구조가 같은 이름을 갖는 경우가 많아서 헷갈릴수도 ...

  따라서 자료구조는 추상적 자료형이 정의한 연산들을 구현한 구현체이다.