solution

main 함수에서 while 문을 돌면서 이분탐색을 수행한다. 이분탐색을 통해 얻은 최적의 운영시간을 이용하여 마지막 아이가 타러 들어가는 놀이기구 번호를 구해준다. -> 이 부분에서 결과괎을 어떻게 사용하는지에 대해 블로그를 참고 (https://baebalja.tistory.com/m/158)

시간복잡도 O(log(놀이기구 하나의 운행 시간 * 인원 수의 최대 값))

check 함수

해당 운행시간으로 놀이기구를 운전 할 때, 탑승할 수 있는 인원수를 계산

bool check(long long mid) {
    ll cnt = q;
    for (int i = 0; i < v.size(); i++) {
        cnt += mid / v[i];
    }
    return cnt >= n;
}

전체 코드

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

vector<int> v; // 놀이기구의 운행시간을 저장하는 벡터
vector<int> result1; // 결과 벡터 1
vector<int> result2; // 결과 벡터 2
typedef long long ll; // long long 자료형의 별칭 설정

ll l, h, n, q; // 이분탐색의 범위와 입력 변수 선언

// 주어진 운행시간(mid)으로 놀이기구를 탈 수 있는지 확인하는 함수
bool check(long long mid) {
    ll cnt = q; // cnt 변수에 초기 운행 횟수 할당
    for (int i = 0; i < v.size(); i++) { // 모든 놀이기구에 대해 반복
        cnt += mid / v[i]; // 주어진 시간 동안 각 놀이기구의 운행 횟수 더하기
    }
    return cnt >= n; // 놀이기구 운행 횟수가 요구된 인원 수 이상인지 확인
}

int main() {
    l = 1; // 이분탐색의 시작 범위
    h = 60000000000; // 이분탐색의 끝 범위 (놀이기구 하나의 운행시간 * 인원수의 최대값)
    cin >> n; // 인원 수 입력
    cin >> q; // 놀이기구 수 입력
    for (int i = 0; i < q; i++) { // 모든 놀이기구의 운행시간 입력
        int a;
        cin >> a;
        v.push_back(a); // 놀이기구의 운행시간 벡터에 추가
    }
    if (n <= q) { // 인원 수가 놀이기구 수와 같거나 작은 경우
        cout << n; // 인원 수 출력 후 프로그램 종료
        return 0;
    }
    ll time = 0; // 최적 운행시간 초기화
    while (l <= h) { // 이분탐색 수행
        long long mid = (l + h) / 2; // 중간 값 설정
        if (check(mid)) { // 운행시간이 충분한 경우
            h = mid - 1; // 더 작은 운행시간을 탐색하기 위해 범위 갱신
            time = mid; // 현재 운행시간 저장
        } else {
            l = mid + 1; // 운행시간이 부족한 경우, 더 큰 운행시간을 탐색하기 위해 범위 갱신
        }
    }
    ll ch = q; // 이전 운행 횟수로 초기화
    for (int i = 0; i < q; i++) { // time-1초에 타러간 아이들의 수 계산
        ch += (time - 1) / v[i];
    }
    for (int i = 0; i < q; i++) { // time초에 타러가는 아이들의 수 갱신
        if (time % v[i] == 0) ch++;
        if (ch == n) { // 마지막 아이가 타러 들어가는 놀이기구 번호 출력
            cout << i + 1 << "\n";
            break;
        }
    }
}

솔루션

왼쪽 기준 오름차순으로 정렬했을때, 오른쪽 값이 이전보다 커야된다는 점에서 LIS임을 캐치 할 수 있었다. 정렬 후 오른쪽 기준의 최장 증가 부분 수열을 구한 후, 전봇대의 개수에서 빼주면 최소한으로 제거할 수 있는 전선의 개수를 구할 수 있다. 가장 긴 증가하는 부분 수열 문제와 코드가 아주 유사하다.

전체코드

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

using namespace std;

int n, dp[105];
vector<pair<int, int>> v;

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }

    fill(dp, dp + n, 1);
    sort(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[i].second > v[j].second && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (res < dp[i]) res = dp[i];
    }
    cout << n - res;

    return 0;
}

LIS (Longest Increasing Subsequence)

주어진 '수열' 에서 일부 원소를 뽑아내어 새로만든 수열이 '부분 수열' 이 수열이 '오름차순' 인 수열이 '증가하는 부분 수열' 이 된다. 만들 수 있는 오름차순 수열 중, '가장 긴' 수열이 LIS가 된다.

가장 긴 증가하는 부분수열 시리즈의 코드와 거의 유사하나, 가장 증가하는 부분 수열의 길이 + 수열을 출력해야한다.

수열을 저장하고 출력하는 부분의 코드가 추가되었다.

LIS 코드

arr배열을 탐색하며 증가 수열이 가능한 경우 dp배열을 갱신시켜준다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
            dp[i] = dp[j] + 1;
        }
    }
}

수열 저장

최장길이인 temp값을 --시켜주면서 해당되는 값을 벡터에 저장

int temp = res;
for (int i = n - 1; i >= 0; i--) {
    if (temp == 0) break;
    if (dp[i] == temp) {
        v.push_back(arr[i]);
        temp--;
    }
}

후 벡터를 뒤에서 부터 출력해 주었습니다.

전체코드

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

using namespace std;

int n, arr[1005], dp[1005];
vector<int> v;

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

    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    fill(dp, dp + n, 1);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > res) res = dp[i];
    }
    int temp = res;
    for (int i = n - 1; i >= 0; i--) {
        if (temp == 0) break;
        if (dp[i] == temp) {
            v.push_back(arr[i]);
            temp--;
        }
    }

    cout << res << "\n";
    for (int i = v.size() - 1; i >= 0; i--) cout << v[i] << " ";

    return 0;
}

Binary Search / 이분탐색

오름차순의 값 left ~ right 사이의 중간위치 mid를 구하여 array[mid]의 값과 타겟을 비교한다. -> 타겟이 mid의 값보다 작다면 : right = mid -> 타겟이 mid의 값보다 크다면 : left = mid + 1; 시간복잡도 O(logN)

이분탐색인 이유

입력 조건 : 방의 개수 N (1 ≤ N ≤ 123,456) HMaxHP 의 값을 1부터 최대값까지 계산하면 시간초과가 난다.

left, right 값 설정하는 과정에서 HMaxHP의 최댓값이 아주 크다는 사실을 알게되었다. left를 1로, right를 1e12 로 설정해주었더니 right의 값이 부족해서 틀렸습니다를 겪었다. right값을 9e18 로 설정하여 여유있게 통과할 수 있었다.

10억이상이면 이분탐색을 쓰라는 글을 본 적이 있었던 것 같기도..

tuple

방의 상태, 몬스터의 공격력, 몬스터의 생명력 을 저장하는 tuple을 가진 vector배열을 사용했다.

typedef tuple<int, int, int> t;
vector<t> v;

check 함수

해당 hp로 용사의 생존 가능을 검사하는 함수

bool check(long long HP) {
    long long atk = m, hp = HP; // 공격력, 생명력

    for (int i = 0; i < n; i++) {
        int state, ma, mh; // 방의 상태, 몬스터의 공격력, 몬스터의 생명력
        tie(state, ma, mh) = v[i];

        if (state == 1) { // 몬스터
            long long t; // 쓰러트리기까지의 횟수
            if (mh % atk == 0)
                t = mh / atk - 1;
            else
                t = mh / atk;
            hp -= ma * t;

            if (hp <= 0) return false; // 생존 불가능
        } else { // 포션
            atk += ma; // 공격력 증가
            hp = min(HP, hp + mh); // 생명력 회복
        }
    }

    return true; 
}

전체코드

#include <algorithm>
#include <iostream>

using namespace std;

typedef tuple<int, int, int> t;

int n, m;
vector<t> v;
long long res;

bool check(long long HP) {
    long long atk = m, hp = HP;

    for (int i = 0; i < n; i++) {
        int state, ma, mh;
        tie(state, ma, mh) = v[i];

        if (state == 1) {
            long long t;

            if (mh % atk == 0)
                t = mh / atk - 1;
            else
                t = mh / atk;

            hp -= ma * t;
            if (hp <= 0) return false;
        } else {
            atk += ma;
            hp = min(HP, hp + mh);
        }
    }

    return true;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c});
    }

    long long left = 1, right = 1e18;
    while (left <= right) {
        long long mid = (left + right) / 2;

        if (check(mid)) {
            right = mid - 1;
            res = mid;
        } else {
            left = mid + 1;
        }
    }
    cout << res;

    return 0;
}

일단 나는 2월 2일 마감인데 1월 31일 저녁에 알게되었다..

프론트엔드를 모집하는 기업은 40개정도였는데 다음과 같은 순위로 기업을 추렸다.

1. 자율 출퇴근제
2. 점심 식대 지원
3. 개발직의 규모 및 유명세

M사, R사, A사 으로 선택했다. 무경력주제에 너무 과분한 기업만 골랐다.

이력서, 자기소개서, 포트폴리오

이력서는 홈페이지에서 제공해주는 이력서 양식을 그대로 활용했다. 학점이랑 전공과목 성적을 기제하는데 민망했다.. 어쩌겠냐만은 하하

자기소개서는 아래와 같은 내용으로 작성하였다.

지원 동기 본인의 강점 기술적 역량

포트폴리오는 다른분의 지원후기를 참고하여 노션 포트폴리오를 하나 만들어서 이력서에 첨부했다. 최대한 나를 표현하고자 노력했다.

소개 수상경력 및 대외활동 기술스택 프로젝트 설명 목표

코테

지원한 3기업 모두 코테 점수를 봤다. 해커랭크에서 6시간동안 5문제를 푸는 방식이었다. 나는 2시간 안넘기고 5문제를 다 해결할 수 있었다!! 문제는 전부 영어였는데 크롬 자동 번역 + 눈치로 풀었다.

서류

서류 및 면접이 7일16일동안 완료되는 일정이었다. 9일12일이 설연휴라 피말라가며 기다렸다. 감사하게도 두 기업에서 면접 연락을 주셨다.

A사 : **서류 불합격** 7일 ict 홈페이지에 들어가서 불합격 사실을 알게 되었다. 첫 결과부터 서류떨이라 마음이 좋지 못했다..

M사 : **서류 합격** 8일 저녁 이메일로 연락이 왔다! 원피스보다가 깜짝 놀라서 뒤집어졌다. 바들바들 떨면서 면접 날짜를 지정했다.

R사 : **서류 합격** 13일 점심 문자로 연락을 받았다! 비대면 30분 면접을 진행한다고 했다. 면접 시간대가 모두 극 아침이었다 ㅜㅜ

면접

M사 본사에서 40분가량 진행되었고, 2:1 면접이었다. 면접 시간 전, 대기하는동안 면접키트도 받았다. (물, 핸드크림 등등) 이 기업의 면접 후기를 검색했을때 인성면접을 본 후기가 많아서 인성면접을 준비해갔는데 기술질문만 받았다.

제출한 포트폴리오를 기반으로 아주 자세한 질문들을 주셨다! 면접분위기는 아주 좋았어서 기분좋게 면접보고 나왔다. 35분가량은 질문을 받고, 10분가량은 내가 질문을 하는 시간을 가졌다.

마지막으로 입사한다면 어느 파트에서 일하고 싶은지도 여쭈어주셨다. 면접 보는내내 꼭 붙고싶다는 생각을 오만번정도 했다.

면접 키워드 타입스크립트, 컴포넌트 재사용, 알고리즘, 클라이언트 최적화, SSR, SSG

*R사 * 이른 아침 비대면으로 30분가량 진행되었다. 1:1 면접이었다. 자기소개와 가장 내세울 프로젝트의 소개 후 질문들을 받았다. 전체적으로 내 이력서(수상경력, 대외활동)만 보고 질문해주시는 느낌이었다. 음,,, 그리고 학점이 낮은 이유를 질문해주셨다. (조금 공격적인 질문일 수 있는데~ 로 시작해주셔서 마음의 준비를 할 수 있었다.)

25분 질문받고, 5분정도 내가 질문하는 시간을 가졌는데, 학점 낮은 나를 왜 서류통과 시켰는지 질문드렸다. (이후 면접에서는 안그래야겠다) 내 스택이 기업과 fit하고 코테 만점을 좋게 보셨다고 하셨다.

아침이기도하고 버벅거린 부분들이 있어 아쉬운 면접이었다..

면접 키워드 실시간 통신, 소켓, 이미지 최적화, 컴포넌트 재사용

결과

R사 : **면접 불합격** 16일 점심즈음 ict 홈페이지에서 불합격 사실을 확인할 수 있었다. 면접보는내내 최종합은 어렵겠다는 생각을 하기는했지만,, 심장이 뚝 떨어지는 느낌이었다 ㅜㅜ

M사 : **면접 합격** 16일 저녁, 면접 전형이 끝난 시간 이후에 홈페이지에서 면접 합격을 확인할 수 있었다!!!!!! M사 하나남은 상황이었는데 마지막에 합격 뜨자마자 숨 한번 쉬고 다시 확인했다!!!!!!

19일에 기업 확정 버튼이 생기자마자 M사로 확정했다.

회고

내 첫 인턴을 유명하기도하고 프론트로써 많이 성장할 수 있는 M사에서 일하게 되었다니 진짜 꿈만같다!!!!!!!!!!!!

4학년 1학기를 알찬 인턴생활로 채워보도록 노력하겠다.

열심히 해볼게요 아자아자!!

미니게임천국

미니게임천국 컨셉의 웹 게임 프로젝트 2023.02 ~ 2023.06

회고 42칭구들과 시작한 웹게임 프로젝트 ! 제대로된 협업이 처음이었고, 프론트가 나 혼자라서 힘들었다.. 후반에는 준서님께서 리뷰를 해주셨는데 많이 도움이 되었다. 여러 사정으로 백엔드와의 개발을 마무리하지는 못했다. 아쉽지만 적당히 마무리 하게 되었다. 음 그리고,, 이 때 커밋을 자주 안 하는 아주 나쁜 습관을 가지고 있었는데 이후로는 커밋을 잘 분리해서 올리도록 고쳤다아.

무엇을 얻었나요

• 타입스크립트를 사용 할 수 있게 됨
• 코드 분리의 중요성을 알게 됨
• 리뷰의 중요성을 알게 됨
• 원없이 그림을 그릴 수 있었음

강의가 듣고 싶어서

캠퍼스 맵 및 강의실 길 안내 서비스 2023.03 ~ 2023.06

회고 3학년 1학기 소프트웨어프로젝트 수업 개발이 처음인 친구들을 데리고 깃부터 알려주었다. 내 할 일도 하면서 남의 코드도 봐주고, 백엔드 쪽도 신경써야해서 여러모로 정신 없었다. 내가 1주일 빨리 개발해서, 팀원들이 참고할 샘플을 만든다는 생각으로 진행했다. 다른 팀원이 제대로 하고있는건지 계속 직접 확인해야했고, 컨플릭트도 전부 내가 풀어줬다... 쓰다보니 정신병 걸릴 것 같다.

아쉬운 점은 이런 길찾기 알고리즘을 전부 프론트에서 계산했다는 점. 폴더 구조가 굉장히 별로라는 점. 외에도 자잘한 문제가 많았지만 허허허

무엇을 얻었나요

• 인 내 심
• recoil 사용
• 셀레니움으로 크롤링 하기

ft_transcendence

Ping-Pong 웹 게임 2023.10 ~ 2023.11 2024.01 ~ 리팩터링 진행중

회고 42seoul 6서클 마지막 과제 내가 지금까지 만든 것 중에 젤 기엽게 만듦 42서울 귀여운 트센 top5에 들지 않을까요 ?

서버비를 줄이는 방법에 대해서도 고민했던 것 같다. 쉬운 방법보다 좋은 방법을 추구하도록 노력했다.

겨울 방학동안 팀원들과 리팩터링하고, 새로운 기능 추가해서 제대로 배포 할 예정 !

무엇을 얻었나요

• next.js 사용
• next에서 제공하는 next-auth, middleware 등 사용
• socket.io 사용
• eventEmitter 사용

SSUspot

위치 기반 사진 SNS 2023.10 ~ 2023.12

회고 3학년 2학기 캡스톤 프로젝트 1 만족스럽지는 않지만 어느정도 잘 마무리 했다고 생각한다. 다들 다른 활동 하느라 모두 참여율이 낮았다. 나 또한 트센 하느라 열심히 참여하지 못 하여 아쉽다.. 위치 및 메타데이터를 더 이용하였으면 좋았을 것 같다.

무엇을 얻었나요

• aws 배포
• 모바일 버젼 개발

와~ 1년 열심히 했다 ~ 좀 더 좋은 구조와 좋은 코드에 대해 공부해야겠다.

내가 무엇을 했고, 어떤 것을 배웠는지 정리 할 필요가 있어 적어보았다. 자소서는 참 어렵다아

이제까지 웹 프로젝트를 회고했으니 아래로 42팀플 회고를 시작하겠다. 트센은 위에 썼으니까 제외한다.

minishell

터미널 쉘 프로그램 bash 구현 2022.12 ~ 2023.01 (3주)

회고 42seoul 3서클 과제 ls >> a.txt | grep ae → a.txt에 저장 & 출력 없음 이런 실제 bash를 구현하는 과제였다 진짜 막막했었다. 쉘 걍 터미널 아님 ? -> 이랬었다고 나는 파싱부, 이소현은 실행부를 맡아서 했다. (사실 잡일부임. 입력 토큰별로 관리하고 환경변수 관리하고 시그널 처리하고 명령어 구현하고) 이소현이 자주 아팠음!!! 아래 본인 사진 첨부

아 금융권에서 미니셸같은 프로젝트 좋아한다는 소문이 있던데 금융권은 저에게 집중해주시길 바랍니다 감사합니다~

무엇을 얻었나요

• 프로세스의 개념
• 리다이렉션 및 파이프의 개념
• 프로세스간의 시그널 처리
• lldb, vscode 디버거 사용법
• Git 사용법

cub_3D

RayCasting을 이용한 3D게임 구현 2023.02 (2일컷)

회고 42seoul 4서클 과제 밤새서 후딱 끝내자! -> 2일컷 남예지 장현진 송승훈과 빠르게 샤샤샥 끝내버렸어요.

무엇을 얻었나요

• 레이캐스팅
• 벡터
• mlx 사용

ft_irc

실시간 채팅 서비스 서버 구현 2023.07 ~ 2023.08 (3주)

회고 42seoul 5서클 과제 조효진 교수님의 네트워크 프로그래밍 수업에서 배운 소켓 api가 큰 도움이 되었다. 그래서 내가 첫 단 커넥션 파트를 맡았다. 약 5분정도 지나면 클라이언트의 연결이 끊기는 현상이 있었는데 Pong 명령어를 만들어주고 네트워크 prefix를 적용해줬더니 해결되었었다 우하하.

무엇을 얻었나요

• 네트워크 계층에 대한 이해
• 블로킹과 논블로킹, 동기와 비동기

와 이제 42과제 팀플까지 모두 끝나버렸다~ 2023년에 팀플을 참 많이 했네요. 42서울의 팀프로젝트 4개중에 3개를 같이한 이소현과 송승훈에게 수고의 말씀돌립니다~

• 서브젝트 한글 번역본 https://github.com/42seoul-translation/subject_ko/blob/master/philosophers/philosophers.ko.md

서론

1. 이번학기에 쓰레드 배우면서 뮤텍스랑 세마포어를 보니 반가워서
2. 보너스에 대한 지문이 별로 없어서
3. 다른 분들도 보너스를 하시길 바라며 !

Dining philosopher problem

과제 해결을 위해 꼭 알아야하는 내용들!

• Thread

  프로세스 내에서 작업을 실행하는 주체 두개 이상의 쓰레드를 가진 프로세스 = 멀티 쓰레드 프로세스 (multi-threaded process) 프로세스는 메모리 공간을 할당받아 실행되나, 쓰레드는 한 프로세스 안에서 실행되며 쓰레드끼리 같은 힙 공간을 공유함

• Deadlock (교착상태)

  멀티 쓰레드 프로세스에서 동일한 자원을 여러곳에서 동시에 접근 할 때, 두개의 쓰레드가 서로의 락 해제를 무한정 기다리는 상황 Deadlock 발생 조건 4가지중, 하나라도 충족하지 않으면 데드락이 발생하지 않음! -> 우리는 deadlock을 해결하기위해 mutext와 semaphore를 이용할 것.

• Mutex & Semaphore

  뮤텍스의 접근을 lock, unlock으로 관리 => 하나의 쓰레드만 접근 Semaphore는 접근할 수 있는 수를 지정하여 여러 쓰레드의 접근이 가능 멘데토리 : mutext 이용, 보너스 : semaphore 이용

• Context Switching (컨텍스트 스위칭)

  여러개의 프로세스가 실행되고 있을 때, 기존에 실행되던 프로세스를 중단하고 다른 프로세스를 실행하는 것. 프로세스를 예시로 들었지만, 실제로 Context가 포괄하는 범위는 넓어용 왜 필요해요 ? : 철학자 쓰레드가 200명정도 된다고 가정했을때, 컨텍스트 스위칭을 발생시켜주어 시간 지연을 최소화합니다. 안 해주면 시간이 밀려서 원래 죽지않아야 할 철학자도 죽습니다.

Mandatory

로직

1. 입력 파싱
2. 철학자들이 각각의 쓰레드에서 활동하게 함
3. 메인 쓰레드에서 철학자들의 종료 조건을 검사

0. 구조

입력 인자를 저장하는 구조체와 각 철학자들이 하나씩 가지고있는 구조체 각각의 철학자들은 모두 입력 구조체의 인자들을 참조 할 수 있음.

typedef struct s_arg
{
    int                philo_num; // 철학자 수
    int                life_time; // 철학자 생명 시간
    int                eat_time; // 식사 소요 시간
    int                sleep_time; // 수면 소요 시간
    int                eat_num; // 식사 횟수
    /* pthread_mutex_t     무더기들 중략 */
    int                monitor; // 종료 flag
}    t_arg;

typedef struct s_philo
{
    int            id; // 철학자 넘버
    int            eat_count; // 철학자 식사 횟수
    int            left; // 왼쪽 포크 넘버
    int            right; // 오른쪽 포크 넘버
    long        last_eat; // 마지막 식사 시간
    long        last_time; // 쓰레드의 시작시간 (작명센스 ㅈㅅ)
    pthread_t    thread; // 쓰레드 ID
    t_arg        *arg; // 입력 인자 값
}    t_philo;

1. 파싱

별 거 없이 argv를 변환하여 넣어준다. 철학자의 식사횟수가 입력으로 들어오는 경우와 들어오지 않는 경우를 분리해주어야한다. 평가를 다녀보니 처리를 따로 해주지않아 쓰레기값이 들어오는 경우들이 있더라

int    init_argv(t_arg *arg, int argc, char **argv)
{
    arg->philo_num = ft_atoi(argv[1]);
    arg->life_time = ft_atoi(argv[2]);
    arg->eat_time = ft_atoi(argv[3]);
    arg->sleep_time = ft_atoi(argv[4]);
    arg->monitor = 0;
    if (arg->philo_num <= 0 || arg->life_time < 0 || \
        arg->eat_time < 0 || arg->sleep_time < 0)
        return (1);
    if (argc == 6)
    {
        arg->eat_num = ft_atoi(argv[5]);
        if (arg->eat_num <= 0)
            return (1);
    }
    else
        arg->eat_num = 0;
    return (0);
}

마찬가지로 각각의 철학자들도 초기화 해주어야한다. 설명이 필요없을 것 같아 줄인다.

int    init_philo(t_philo **philo, t_arg *arg)
{
    int        i;

    i = 0;
    *philo = malloc(sizeof(t_philo) * arg->philo_num);
    if (!philo)
        return (1);
    while (i < arg->philo_num)
    {
        (*philo)[i].id = i + 1;
        (*philo)[i].eat_count = 0;
        (*philo)[i].left = i;
        (*philo)[i].right = (i + 1) % arg->philo_num;
        (*philo)[i].last_eat = 0;
        (*philo)[i].last_time = 0;
        (*philo)[i].arg = arg;
        i++;
    }
    return (0);
}

2. 뮤텍스

내가 선언한 뮤텍스들

pthread_mutex_t    *fork;
pthread_mutex_t    print;
pthread_mutex_t    mutex_monitor;
pthread_mutex_t    mutex_eat_cnt;
pthread_mutex_t    mutex_last_eat;

아래로는 사용할 뮤텍스 함수들

//뮤텍스 생성 함수, 성공하면 0 리턴
int pthread_mutex_init(pthread_mutex_t * mutex, const pthread_mutex_attr *attr);
// mutex : 뮤텍스 객체
// attr : 뮤텍스 속성, 객체의 주소, NULL (우리는 NULL)

// 뮤텍스 잠금, 잠금해제 함수, 성공하면 0 리턴
int pthread_mutex_lock(pthread_mutex_t *mutex); //사용중
int pthread_mutex_unlock(pthread_mutex_t *mutex); //사용 가능 상태
// mutex : 뮤텍스 객체

//뮤텍스 해제 함수, 성공하면 0 리턴
int pthread_mutex_destroy(pthread_mutex_t *mutex);
// mutex : 뮤텍스 객체

그래서 어떻게 쓰냐고요? 우선 먼저 뮤텍스를 생성해주자. 귀찮으니 포크 뮤텍스 할당하는것만 올린다

arg->fork = malloc(sizeof(pthread_mutex_t) * arg->philo_num);
    if (!arg->fork)
        return (1);
    while (i < arg->philo_num)
    {
        if (pthread_mutex_init(&(arg->fork[i]), NULL) == -1)
            return (1);
        i++;
    }

이 뮤텍스를 어디에 쓰느냐? 동시에 접근 할 것 같은 변수 앞뒤로 써주면 된다. 한번에 한 쓰레드만 변수에 접근 권한을 주어 데드락을 막는것이다.

3. 쓰레드

사용하는 함수

#include <pthread.h>

// 쓰레드 생성 함수
int  pthread_create(pthread_t  *  thread, pthread_attr_t *attr, void * (*start_routine)(void *), void * arg);
// thread : thread ID (thread의 주소)
// attr : thread의 속성을 저장하는 구조체 (NULL로 셋팅)
// start_routine : thread와 함께 호출되는 함수 포인터 (thread가 실행하는 함수)
// arg : start_routine에 전달되는 매개변수 (없으면 NULL)

// 쓰레드의 종료를 기다리는 함수, 성공시 0 리턴
int pthread_join(pthread_t th, void **thread_return);
// thread : thread ID
// retval : thread가 종료하면서 반환하는 값에 접근할 수 있는 더블 포인터

main process는 thread의 종료를 기다려주지않고 종료되기때문에, 메인 프로세스에서 thread의 종료를 pthread_join를 이용하여 기다려 줄 것이다.

while (i < arg->philo_num)
    {
        pthread_mutex_lock(&philo->arg->mutex_last_eat);
        philo[i].last_eat = get_time();
        pthread_mutex_unlock(&philo->arg->mutex_last_eat);
        philo[i].last_time = get_time();
        if (pthread_create(&(philo[i].thread), NULL, thread_f, &philo[i]))
            return (1);
        i++;
    }

나는 이런식으로 쓰레드를 생성할 수 있게 해주었다. 지금보니 참 거지같은 코드다. 실제로 200명 이상 돌리면 시작시간이 밀리는 경우가 발생한다. 뮤텍스 하나를 더 사용하여 동시에 시작할 수 있도록 해줄 걸 그랬다.

4. 먹고 자고 생각하는 철학자들

진짜 개그지같은 코드지만. 철학자 쓰레드의 함수다.

void    *thread_f(void *data)
{
    t_philo        *philo;

    philo = data;
    if (philo->id % 2 == 0)
        usleep(100);
    while (!checking(philo->arg)) // 죽었는지 살았는지 체크
    {
        if (get_fork(philo)) //포크 잡다 죽었으면 종료
            break ;
        if (checking(philo->arg))
        {
            pthread_mutex_unlock(&(philo->arg->fork[philo->left]));
            pthread_mutex_unlock(&(philo->arg->fork[philo->right]));
            break ;
        }
        philo_eating(philo); // 식사
        if (checking(philo->arg)) // 다 먹었는데 누구 죽었음 종료
            break ;
        philo_printf(philo, philo->id, "is sleeping");
        ft_usleep(philo->arg->sleep_time);
        if (checking(philo->arg)) // 자고 일났는데 누구 죽었음 종료
            break ;
        philo_printf(philo, philo->id, "is thinking");
    }
    return (0);
}

과하다. 근데 데이터 레이스를 잡다보니 이렇게 되었다 머 어쩌겠어요 아래는 포크 잡는 함수. 1명일때 예외처리 해놓은 부분때문에 작성함

int    get_fork(t_philo *philo)
{
    if (philo->arg->philo_num == 1) //한명일 때 예외처리
    {
        pthread_mutex_lock(&(philo->arg->fork[philo->left]));
        philo_printf(philo, philo->id, "has taken a fork");
        pthread_mutex_unlock(&(philo->arg->fork[philo->left]));
        return (1);
    }
    pthread_mutex_lock(&(philo->arg->fork[philo->left]));
    philo_printf(philo, philo->id, "has taken a fork");
    pthread_mutex_lock(&(philo->arg->fork[philo->right]));
    philo_printf(philo, philo->id, "has taken a fork");
    return (0);
}

오잉 잠깐. 여기서 philo_eating함수 보기전에 우리는 데이터 레이스에 대해 알아야해요

5. 데이터 레이스

여러 쓰레드/프로세스가 공유자원에 동시에 접근하려 할 때 일어납니다. 우리 같은 경우, 두 철학자가 동시에 포크에 접근하는 경우나, 모니터링 함수와 철학자 쓰레드에서 동시에 last_eat 변수에 접근하는 경우를 예시로 들 수 있어요.

어떻게 막아용 ??

어떡하긴여 뮤텍스로 잘 막아줘야조 ^^ 이팅 함수로 예시를 들어보겠습니다

void    philo_eating(t_philo *philo)
{
    philo_printf(philo, philo->id, "is eating");
    pthread_mutex_lock(&philo->arg->mutex_last_eat);
    philo->last_eat = get_time();
    pthread_mutex_unlock(&philo->arg->mutex_last_eat);
    ft_usleep(philo->arg->eat_time);
    pthread_mutex_lock(&philo->arg->mutex_eat_cnt);
    philo->eat_count++;
    pthread_mutex_unlock(&philo->arg->mutex_eat_cnt);
    pthread_mutex_unlock(&(philo->arg->fork[philo->left]));
    pthread_mutex_unlock(&(philo->arg->fork[philo->right]));
}

여기서 어떤 부분이냐

pthread_mutex_lock(&philo->arg->mutex_last_eat);
philo->last_eat = get_time();
pthread_mutex_unlock(&philo->arg->mutex_last_eat);

last_eat에 write하기전에, 앞 뒤를 뮤텍스로 막아준 것이 보이는가? 왜냐하면 나는 이 last_eat변수를 모니터링 함수에서 철학자가 죽었는지 확인 할 때 사용한다. 동시에 접근하는 상황을 막기위해 만들어 주었다.

최근에 필로 평가가면 데이터레이스 검사를 안 해보셨거나 잘못 검사하신 분들이 많다. cflag에 -g -fsanitize=thread 옵션을 추가하여 함께 컴파일 해보길 바란다. 왜냐면 딱 봐도 데이터 레이스 날 것 같은데 어 안났는데용? 사람들이 있따 ^^,,, 제대로 컴파일 안 했으먼서!! 아무튼 꼭 해라 그리고 데이터 레이스가 어디서 발생했는지 상세히 알려주니 에러를 읽어보면 쉽게 고칠 수 있다.

6. 시간

우리가 사용할 구조체

# include <sys/time.h>

struct timeval
{
    long tv_sec;       // 초
    long tv_usec;      // 마이크로초
}

나는 모든 시간을 long 으로 바꾸어 가지게 해주었다. 종종 timeval구조체를 들고다니시기도 하더라. 머 똑같다.

long    get_time(void)
{
    struct timeval    time;
    long            result;

    gettimeofday(&time, NULL);
    result = ((size_t)time.tv_sec * 1000) + ((size_t)time.tv_usec / 1000);
    return (result);
}

중요한 부분이다. 나는 ft_usleep 함수를 만들어 usleep()을 100usec씩 나누어서 해주었다 왜일까요 ?

void    ft_usleep(long sleep_time)
{
    long    start;

    start = get_time();
    while (start + (sleep_time * 1) > get_time())
        usleep(100);
}

시작 전 컨텍스트 스위칭에 대해 언급하였다. 그 사유니까 다시 올라가서 읽으면 된다. 이 부분은 현진님께서 가르쳐주셨당 최고의 개발자~

7. 모니터링 함수

다 왔다 진짜 마지막!! 메인 함수에서 죽은 철학자들이 없는지 검사해주는 함수이다. 모니터링 함수는 (https://techdebt.tistory.com/32) 블로그를 참조했다. 그치만 저는 데이터레이스를 막기위해 더 더러운 함수가 되었어용

void    monitoring(t_philo *philo, t_arg *arg)
{
    int        i;
    long    now_time;

    while (!checking(arg))
    {
        if (arg->eat_num != 0 && check_eat_cnt(philo, arg) == arg->eat_num)
        {
            change_monitor(arg);
            break ;
        }
        i = 0;
        while (i < arg->philo_num)
        {
            now_time = get_time();
            if ((now_time - last_eat(&philo[i])) > arg->life_time)
            {
                philo_printf(&philo[i], philo[i].id, "died");
                change_monitor(arg);
                break ;
            }
            i++;
        }
        usleep(10);
    }
}

여기서 checking(arg)함수만 잠깐 살펴보면,,

int    checking(t_arg *arg)
{
    pthread_mutex_lock(&arg->mutex_monitor);
    if (arg->monitor == 1)
    {
        pthread_mutex_unlock(&arg->mutex_monitor);
        return (1);
    }
    else
    {
        pthread_mutex_unlock(&arg->mutex_monitor);
        return (0);
    }
}

머 데이터 레이스를 막으려고 모두 함수화 한 부분이다. 내 모든 뮤텍스들은 이렇게 일 하고있다. 개인의 코드마다 데이터 레이스 나는 부분은 다르니, 컴파일 해보시며 뮤텍스를 적절히 넣기를 바랍니다.

멘데토리는 이게 끝이다. 그치만 여기에 지치지마시고 보너스도 하셨음 좋겠다. 왜냐면 ㄹㅇ 학교에서 배운다. 보너스도 읽어줘라 왜냐면 내 보너스 뿌듯함 ㅇㅇ

Bonus

보너스 진짜 생각보다 안 어려움 그런데 멘데로티에서 가져올 코드는 거의 없습니다. 새로운 세미 과제를 하나 더 클리어 한다는 느낌으로 시작해야함 ^^ 하하하 가지마세요 ㅜ

시작하기전에 잠시만여

멘데토리에서는 철학자를 thread로 만들어주고 mutex를 이용하여 데드락을 막았다. 보너스에서는 철학자가 각각의 process여야하고, semaphore를 이용하여 데드락을 막아 줄 것이다.

0. 구조

typedef struct s_philo
{
    int                philo_num;
    int                life_time;
    int                eat_time;
    int                sleep_time;
    int                eat_num;
    /* sem_t        세마포어들 생략 */
    int                id;
    int                eat_count;
    long            start_time;
    pthread_t        thread;
    struct timeval    time;
}    t_philo;

이 구조체 하나면 됨. 와~

1. 파싱

int    init_argv(t_philo *philo, int argc, char **argv)

위에서 쓴 init 함수만 그대로 가져다 쓸 수 있다. 나머진 다 다르다. 울지마세용 ㅜㅜ

2. 세마포어

제가 선언한 세마포어들입니다. 얘는 다 세마포어 포인터입니다. 개수가 몇개든

sem_t            *fork;
sem_t            *print;
sem_t            *die;

아래로 세마포어 함수

# include <semaphore.h>

// 세마포어 생성 함수
sem_t *sem_open(const char *name, int oflag, mode_t mode, unsigned int value);
// name : 세마포어 이름
// oflag : 세마포어 특징 (O_RDWR, O_RDONLY, O_CREAT, O_EXCL)
// mode : 권한 정보 (chmod 777 그거)
// value : 세마포어 초기값 (ex. 포크가 5개 필요하면 5)

// 세마포어에 접근하고, 반납하는 함수, 성공하면 0 리턴
int sem_wait(sem_t *sem); // 접근 제한
int sem_post(sem_t *sem); // 반납
// sem : 세마포어 포인터

int sem_unlink(const char *name); // 세마포어 제거
int sem_close(sem_t *sem);v // 세마포어 종류

헷갈리면 코드를 보며 이해해보자.

void    init_sem(t_philo *philo)
{
    sem_unlink("sem_fork"); // 겹치는 이름이 있을수 있으니 삭제
    sem_unlink("sem_print");
    sem_unlink("sem_die");
    philo->fork = sem_open("sem_fork", O_CREAT, 0644, philo->philo_num);
    philo->print = sem_open("sem_print", O_CREAT, 0644, 1);
    philo->die = sem_open("sem_die", O_CREAT, 0644, 1);
}

open의 인자를 한번 더 설명하자면, "sem_fork" 이름, O_CREAT 옵션, 접근권한 0644, philo->philo_num 개수만큼 변수값 설정. O_CREAT옵션은 해당 이름의 객체가 존재하지 않을 경우, 새로운 객체를 생성하는 옵션이다. 포크는 철학자 수 만큼 필요하니 philo_num으로 설정해주었다.

이제 이 세마포어를 어떻게 쓰는지 알아보자.

int    get_fork(t_philo *philo)
{
    if (philo->philo_num == 1)
    {
        sem_wait(philo->fork);
        philo_printf(philo, philo->id, "has taken a fork");
        sem_wait(philo->fork);
        return (1);
    }
    sem_wait(philo->fork);
    philo_printf(philo, philo->id, "has taken a fork");
    sem_wait(philo->fork);
    philo_printf(philo, philo->id, "has taken a fork");
    return (0);
}

보면 알겠지만 멘데토리의 포크 함수와 똑같다. 다만 pthread_mutex_lock -> sem_wait 의 차이

사실뮤텍스와 세마포어의 가장 큰 차이는 repeat부분에서 나온다. 그 전에, fork()에 대해 알아보자.

3.fork()

이거 철학자들이 집는 포크 아니다. 자식 프로세스를 생성하는 함수에용

#include <unistd.h>

pid_t fork(void);
// 부모 프로세스의 리턴값 : 자식 프로세스의 pid
// 자식 프로세스의 리턴값 : 0

minishell 해결한사람에게는 껌이겠고, 아닌 사람은 미칠 것이다. 본인은 미니셸을 해결한 후 필로 보너스를 했기에 ^^ 간단히 설명하자면, 철학자 수 만큼 자식 프로세스를 생성 할 것이다.

자식 프로세스는 fork되는 순간, 부모 프로세스의 모든 정보를 복사한 독립적인 메모리 영역이 생성된다. 이후 각각의 프로세스는 독립적으로 실행된다.

int    make_child(t_philo *philo)
{
    pid_t    *pid;
    int        i;

    i = -1;
    pid = (pid_t *)malloc(philo->philo_num * sizeof(pid_t));
    if (!pid)
        return (1);
    philo->start_time = get_time();
    while (++i < philo->philo_num)
    {
        pid[i] = fork(); // 자식 프로세스 생성
        if (pid[i] < 0) // 에러 처리
            return (1);
        if (pid[i] == 0) // 자식이면
        {
            philo->id = i; //철학자 넘버 지정
            break ;
        }
    }
    if (pid[philo->id] == 0 && !child(philo)) //자식이면 자식 함수 실, norm맞춘다구 이모양!
        return (1);
    else
        parents(philo, pid); //부모 함수 실행
    free(pid);
    return (0);
}

대충 감이오나여?

이제 부모 프로세스가 실행하는 함수와 자식 프로세스가 실행하는 함수의 구현부를 볼 것.

int    child(t_philo *philo)
{
    philo->id += 1; // 0부터 시작해서 +1
    philo->eat_count = 0; //횟수 초기화
    gettimeofday(&philo->time, NULL); 
    if (pthread_create(&(philo->thread), NULL, monitoring, philo)) // 모니터링 쓰레드 생성
        return (1);
    repeat(philo); // 먹고 자고 생각하고 반복하는 함수
    exit(0);
    return (0);
}

이거 좀 정신 나갈 것 같죠 여기서 부터 다른점!!!!!!!! 이렇게 생성된 자식 프로세스 = 한명의 철학자 이 모든 철학자 프로세스의 함수에서 반복적인 활동을 함 그럼 이 철학자들이 죽었는지 체크하는 역할은 누가하냐? 쓰레드가 함.

정리 : 자식 프로세스 하나 = 철학자 한명, 철학자 한명 당 모니터링 쓰레드 하나

철학자가 200명이면 메인프로세스 포함 201개, 쓰레드 200개가 생성됨 ㅋㅋㅋ 느려요 진짜 느림. 그치만 200명 안 죽고 돌아갑니다 우하하!!

그럼 철학자 한명이라도 죽으면 어떻게 동작하느냐? 이제 볼거임

void    parents(t_philo *philo, pid_t *pid)
{
    int    status;
    int    i;

    i = 0;
    while (i < philo->philo_num)
    {
        waitpid(-1, &status, 0); // 자식 프로세스 기다림
        if (status != 0) // 오류나면
        {
            i = 0;
            while (i < philo->philo_num)
            {
                kill(pid[i], SIGKILL); // 전부 다주겨
                i++;
            }
        }
        i++;
    }
}

화긴? 중요한 부분은 waitpid(-1, &status, 0); 입니다. 임의의 자식의 종료를 기다림. 정상 종료된 철학자들의 수 (i)가 철학자 수 만큼 될 때까지 기다림.

그럼 오류는 언제 나느냐? 철학자가 한명이라도 죽었을때. 오잉 그건 어떻게 아나요? 모니터링 쓰레드에서 알아보아요

4. repeat 함수

모든 철학자 프로세스가 실행하는 함수.

void    repeat(t_philo *philo)
{
    if (philo->id % 2 == 0)
        usleep(200);
    while (1)
    {
        if (get_fork(philo))
            break ;
        philo_eating(philo);
        if (philo->eat_num != 0 && philo->eat_count == philo->eat_num)
            exit (0);
        philo_printf(philo, philo->id, "is sleeping");
        ft_usleep(philo->sleep_time);
        philo_printf(philo, philo->id, "is thinking");
    }
}

멘데토리보다 훨씬 간단하다. 저기보면 exit(0)보이시나요? 밥 다 먹었으면 정상종료 (0) 하겠다는 뜻입니다. 그럼 비정상종료는 어떻게 하느냐?

5. 모니터링 쓰레드

훨씬 함수가 간단하고 많이 줄었다. 따로 더 구현할 함수도 없다.

void    *monitoring(void *data)
{
    t_philo        *philo;
    long        now_time;
    long        last_time;

    philo = data;
    while (1)
    {
        now_time = get_time();
        sem_wait(philo->die);
        last_time = ((size_t)philo->time.tv_sec * 1000) + \
        ((size_t)philo->time.tv_usec / 1000);
        if (now_time - last_time > philo->life_time)
        {
            philo_printf(philo, philo->id, "died");
            exit(1);
        }
        sem_post(philo->die);
        usleep(100);
    }
}

exit(1)로 비정상 종료 가 되면, 위에 있는 부모 프로세스에서 kill을 이용하여 모든 자식 프로세스를 강제종료한다. 와~ 끗. 간단하죠 ?

진심 보너스 별거 없음 마음만 먹으면 하루만에 뚝딱!! 가능하다구!!

하 근데 오ㅐ케 기냐 멘데토리는 정리하지 말걸 아무튼 제 점수 보고가세요 안녕

priority_queue의 compare 구조체를 만들 수 있는 사람에게는 어렵지 않은 문제였을것. 백준 회의실 배정문제와 유사하다고 생각되었음.

본인은 compare 구조체를 하나만 쓰기위해 compare 안에서 전역변수를 참조하도록 코드를 짰는데, 그렇게 하면 오류가 생긴다,, 고 한다.

그래서 로직을 변경해서 우선순위 큐 2개를 씀

1. 실행순서가 기준인 priority_queue ->pq
2. 우선순위가 기준인 priority_queue ->pq2

priority_queue compare 구조체

struct CompareVector {
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[1] == b[1])
            return a[0] > b[0];
        else
            return a[1] > b[1];
    }
};

struct CompareVector2{
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[0] == b[0])
            return a[1] > b[1];
        else
            return a[0] > b[0];
    }
};

반복

1. pq 에서 현재 시간을 기준으로 실행할 수 있는 프로그램을 꺼내서 pq2 에 push
2. pq2 에 원소가 있다면 top을 꺼내서 갱신 2-1. 이때 현재시간보다 실행시간이 빠르다면 지연 시간 갱신
3. pq2 가 비어있다면 현재시간에 실행시킬 수 있는 프로그램이 없는 것. pq의 top을 꺼내서 현재시간 갱신
4. 종료후 현재 시간을 answer에 갱신! 끗!

code

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

using namespace std;

struct CompareVector {
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[1] == b[1])
            return a[0] > b[0];
        else
            return a[1] > b[1];
    }
};

struct CompareVector2{
    bool operator()(const vector<long long>& a, const vector<long long>& b){
        if (a[0] == b[0])
            return a[1] > b[1];
        else
            return a[0] > b[0];
    }
};

priority_queue<vector<long long>, vector<vector<long long>>, CompareVector> pq;
priority_queue<vector<long long>, vector<vector<long long>>, CompareVector2> pq2;

vector<long long> solution(vector<vector<int>> program) {
    vector<long long> answer;

    for(int i=0; i<11; i++)
        answer.push_back(0);

    for (int i=0; i<program.size(); i++)
    {
        vector<long long> temp;
        temp.push_back(program[i][0]);
        temp.push_back(program[i][1]);
        temp.push_back(program[i][2]);
        pq.push(temp);

        temp = pq.top();
    }

    long long nowtime = 0;

    while (!pq.empty() || !pq2.empty())
    {
        vector <long long> v;

        while (!pq.empty())
        {
            v = pq.top();
            if (v[1] > nowtime)
                break;
            pq2.push(v);
            pq.pop();
        }

        if (pq2.empty())
        {
            v = pq.top();
            nowtime = v[1] + v[2];
            pq.pop();
        }
        else
        {
            v = pq2.top();
            if (nowtime > v[1])
            {
                answer[v[0]] += (nowtime - v[1]);
                nowtime += v[2];
            }
            else
                nowtime += v[2];
            pq2.pop();
        }
    }

    answer[0] = nowtime;

    return answer;
}

어댑터 패턴은 코드를 재사용하기위해 구조를 변경하는 패턴입니다. (구조 패턴중 가장 간단합니다 ^__^)

어댑터

어댑터 패턴은 다른 말로 래퍼 패턴(wrapper pattern)이라고 합니다. 래퍼는 감싸다는 의미로, 기존의 클래스를 새로운 클래스로 감싸는 기법 입니다. 래퍼 처리로 기존의 기능은 유지하면서 변경된 추가 코드를 삽입합니다.

래퍼 처리된 객체를 어댑터라고 합니다.

직접 사진찍은건데 좀 짜그라졌네요.

• 어댑터 : 변환을 처리하는 객체
• 어댑티 : 변환을 받아 사용하는 객체

어댑터 종류

어댑터는 다른 객체의 구조를 내가 원하는 인터페이스 방식으로 개선합니다. 구조를 개선하는 방법은 클래스의 상속을 이용하는 방법과 구성을 이용하는 방법 2가지 입니다.

• 클래스 어댑터 : 상속
• 객체 어댑터 : 구성

클래스 어댑터

클래스 어댑터는 클래스의 상속 특성을 이용하며, 클래스 어댑터를 사용하기 위해서는 다중 상속이 필요합니다.

다중 상속이란 하나의 클래스가 2개 이상의 클래스에서 상속되는것을 말 합니다. 클래스 어댑터는 2개의 클래스를 받아 기존 클래스의 메서드를 다른 메서드로 대체하는 방법입니다.

근데.. 그거 아십니까 최신 프로그래밍 언어는 다중 상속을 지원하지 않습니다. php와 java또한 단일상속만 지원합니다. 다중 상속에서는 클래스 메서드의 충돌이 발생합니다.

아무래도 최신 언어로 다중상속을 이용하여 클래스 어댑터를 표현하기는 어렵겠습니다.

그러나 클래스 어댑터는 별도의 어댑티를 만들지 않으며, 하나의 클래스로 어댑티 객체를 처리할 수 있다는 장접이 있습니다.

객체 어댑터

객체 어댑터는 객체의 의존성을 이용해 문제를 해결합니다. 객체 어댑터는 기존 타깃인 객체의 인터페이스에 영향을 받으며, 타깃의 인터페이스가 복잡할수록 많은 작업이 필요합니다.

객체 어댑터는 내부적으로 객체를 재구성합니다. 구성을 위해 기존 객체는 복합 객체로 변환됩니다.

어댑터는 인터페이스를 변경합니다. 하지만 어댑터는 인터페이스로 캡술화 됐기 때문에 클라이언트에서 변화를 눈치채지 못한채 그대로 사용할 수 있습니다. 어댑터 패턴은 객체의 호환성을 개선하기 위한 기능들로 새롭게 합성합니다.

객체를 구성으로 결합하면 느슨한 연결 방식으로, 보다 많은 유연성을 확보할 수 있다는 장점이 있습니다. 그리고 구성은 프로그램 실행 도중에도 객체를 변경할 수 있습니다.

예제

⛏️ 기존 코드

<php 
//원본소스 
class Math
{
    //입력한 값이 2배 증가합니다.
    // 입력값과 반환값은 float형입니다.
    public function twoTime (float $num): float
    {
        echo "실수 2배 적용합니다. In"
        return $num*2;
    }
    //입력한 값이 절반으로 감소합니다.
    // 입력값과 반환값은 float형입니다.
    public function halfTime(float $num): float
    {
    echo "실수 1/2배 적용합니다. In";
    return $num/2;
    }
}

곱셈을 계산하는 메서드 입니다. 매개변수 인자로 실수값을 받습니다.

만약 인자값이 정수로 변경된다고 가정하면, 더이상 이 Math 클래스를 사용할 수 없습니다. 우리는 어댑터 패턴으로 이 문제를 해결할거에요.

⛏️ 어댑터 제작

<?php
// 어댑터 인터페이스
interface Adapter
{
    public function twice0f(int $num):int; 
    public function half0f(int $num):int;
}

인터페이스에서 입력한 값을 보정합니다. 정수 타입으로 지정한 후, 알맞는 구체 클래스를 만듭니다. +) 인터페이스 변경을 담당하는 클래스를 플러그블 어댑터라고 합니다.

⛏️ 구현 코드

<?php
//새롭게 구현된 코드
class Objects implements Adapter
{
    private $_adapter;

    function _construct()
    {
    //기존 클래스의 객체를 생성합니다.
    $this->_adapter = new math;
    }

    public function twice0f (int $num):int
    {
        echo "정수 2배 적용합니다. n";
        //캐스팅을 통해 실수로 변환하여 전달합니다.
        $_num = $this->_adapter->twoTime( (float)$num );
        //캐스팅을 통해 정수로 변환하여 반환합니다.
        return (int)$_num;
    }

    public function half0f(int $num): int
    {
        echo "정수 1/2배 적용합니다. \n";

        //캐스팅을 통해 실수로 변환하여 전달합니다.
        $num = $this->_adapter->halfTime( (float)$num );
        //캐스팅을 통해 정수로 변환하여 반환합니다.
        return (int)$_num;
    }
}

작성한 어댑터는 기존의 Math 클래스를 상속받지 않습니다. 그 대신 객체의 생성자에서 기존 Math 클래스의 객체를 생성합니다. 어댑터는 생성자에서 새로운 객체를 생성, 포함함으로 복합객체 입니다.

입력된 정숫값을 실숫값으로 캐스팅하고, 기존 Math클래스의 메서드를 호출합니다. 결과값도 캐스팅해서 정수값으로 변경한 후 반환됩니다.

⛏️ 클라이언트 코드

‹?php 
include "Math.php";
include "Adapter.php";
include "Object.php";

sobi = new Objects;

//어댑터를 이용하여 두 배 계산합니다.
echo $obj->twice0f(5);
echo "\n";

//어댑터를 이용하여 절반을 계산합니다.
echo $obj-›half0f(4);

이제 실행해볼까요.

일단 지금은 책에 있는 예제인데 자고 일어나서 테스트해보고 제가 한 예제로 바꿀게요 ><

이처럼 어댑터 패턴을 이용하면 클래스와 메서드를 수정하지 않고, 원하는 형태로 변경 할 수 있습니다.

어댑터 패턴은 한국에서 사용되는 220V 가전제품을 
일본에서 110V에 연결하기 위해 
변환 어댑터와 같은 컨버터를 사용하는 것으로 비유할 수 있습니다.

실습하실 분들을 위해,, 예제 코드를 올려드립니다. 제가 다 쳤습니다. 사실 아니고 아이폰 짱짱맨이 텍스트 읽어줘서 수정 조금만 했습니다. 증말 최고.

구조패턴은 객체와 클래스를 확장시키는 방법입니다.

확장

클래스는 하나의 책임. 역할로 설계됩니다. 하지만 하나의 책임으로는 전체의 기능을 구현 할 수 없습니다.

단일 책임의 원칙은 클래스의 행동을 분리하는 설계원칙입니다. 여러개로 분리된 책임과 행동은 서로 관계를 맺고 주어진 문제를 해결합니다.

객체지향 개발은 클래스를 결합하여 더 큰 객체로 확장 합니다.구조패턴은 큰 구조의 객체를 형성하고관리하는 방법에 대해 설명합니다. 객체를 확장하기위해 클래스의 상속과 합성을 사용합니다.

상속

상속은 객체지향 초창기시절부터 나온 개념입니다. 초기에는 객체를 확장하기위해 상속을 이용했습니다.

상속은 객체지향 고유의 특징입니다. 상속은 정적인 결합을 통해 객체를 확장합니다. 하지만 정적인 상속 결합은 대형 프로그램개발의 유연한 작업엔 한계가 있습니다.

합성

상속 결합의 단점을 보완하기 위한 기법으로 객체 합성을 사용합니다. 합성이란, 하나의 객체가 다른객체에 포함하는 것을 말합니다.

합성은 객체의 강한 의존 관계를 줄이고 유연한 객체 구조로 변결할 수 있으며, 실행 중에도 객체를 확장 할 수 있습니다.

합성을 이용한 객체 확장은, 자원을 보다 효율적으로 사용할 수 있게 합니다.

구조패턴은 상속보다 합성을 통해 다양한 객체 확장 방법을 제안합니다.

🔧 구조패턴의 종류

• 어댑터 패턴 인터페이스를 추상화하여 서로 다른 인터페이스를 통일화합니다. 상속을 통한 어댑터와 합성을 통한 어댑터로 구분합니다.

• 브리지 패턴 개념과 추상을 구분하여 처리합니다. 또한 객테의 독립으로 확장과 변형이 가능합니다.

• 복합체 패턴 객체의 구조를 이용하여 객체를 확장합니다. 복합 객체는 트리 구조의 특징을 갖고 있습니다.

• 장식자 패턴 객체의 기능을 동적으로 추가합니다. 확장 시 객체에 새로운 책임을 부과할 수 있습니다. 재귀저거 합성 방법을 응용하여 객체를 확장합니다.

• 파사드 패턴 복잡한 객체의 구조와 접근을 간단하게 표현하는 방법입니다.

• 플라이웨이트 패턴 플라이웨이트 패턴은 객체를 공유합니다. 객체 공유를 통해 자원의 효율성과 공유된 객체의 일관성을 보장합니다.

• 프록시 패턴 객체의 접근을 제한할 수 있습니다. 객체를 액세스 할 때 추가적인 책임을 부여하는 역할을 수행합니다.

길이 너무 길어져 구조 패턴에 대한 내용과 종류까지만으로 글을 끊습니다. 이 중 몇가지 패턴을 뽑아 정리하려합니다.

"쉽게 배워 바로 써먹는 디자인 패턴"을 읽고~ 오늘은 디자인 패턴이 무엇인지 알아볼게요!

☹️ 디자인책이 아닙니다.

디자인 패턴의 주체는 디자인이 아니라 패턴 이 주체입니다. 어? 그렇다면 디자인패턴과 패턴 은 무엇일까요.

♻️ 디자인 패턴과 패턴

디자인 패턴 이란 소프트웨어 디자인 과정에서 자주 발생하는 문제들에 대한 전형적인 해결책입니다.

패턴은 표준화 된 라이브러리처럼 ctrl x, ctrl v 가능한게 아니에요. 패턴은 코드 조각이 아니라 특정 문제를 해결하는 개념 입니다.

특정 문제를 해결하는 개념은 알고리즘 아닌가요?

아니에요. 비슷해보이지만 달라요!!!!!! 간단히 말하자면 알고리즘은 절차 라면, 패턴은 설계 도면 같은거에요. 응용 가능한 도면.

다시 정리하자면 패턴은 재사용성을 가지는 객체지향 소프트웨어의 요소입니다.

🛠️ 패턴의 분류

패턴은 의도와 목적에 따라 분류가 나뉘어요.

코드의 재사용성과 유연성을 증가시키는 객체 생성 메커니즘을 공유하는 생성 패턴

객체와 클래스를 확장시키는 방법인 구조 패턴

객체간의 효율적인 행동 처리와 분리를 위한 행동 패턴이 있습니다.

⚠️ 주의

패턴을 배웠다고 막 가져다 쓰면 안돼요

“망치만 있으면 모든 것이 못처럼 보인다.”

뭔 말이냐면 꼴깝떨지 말라는 말입니다.

패턴에 대해 배웠다고 더 간단한 일에 굳이 패턴을 사용하여 코드를 복잡하게하는 바보같은짓 하지 말라는 거에요

디자인 패턴과 성능은 별개에요.

디자인 패턴은 코드의 가독성과 유지보수를 위해 객체의 메서드를 분리합니다. 분리로 인하여 호출도 자주 발생하겠죠??

함수 호출과 객체간 호출은 적을수록 성능이 좋답니다 그러니까 너무 많이 사용하지말고 적절히 사용해야 한다는 뜻이에요.

마무리

디자인 패턴이 무엇인지 알아보았어요. 이제 다음부터는 생성, 구조, 행동 패턴에 대해 알아보고 코드를 구현해볼거에요.

참고로 이 책은 PHP로 쓰였습니다. 듣기만하던 php를 책으로 먼저 실습할 줄 몰랐는데,, 아무튼 열심히 해볼게요.

리팩토링이나 클린코드부터 읽어야하는거 아니에요?

클린 코드는 가독성을 위해, 리팩토링은 코드의 유지보수를 위해 읽는다고 생각합니다.

그렇기때문에 클린코드를 뛰어넘고, 패턴에 대해 공부한 후, 리팩토링을 공부하는게 도움되는 순서일 것이라고 판단했습니다.

뭐 읽어서 나쁜건 없지만~ 바쁘다 바빠 현대사회에서 적당한 생략과 선택은 가능하지 않은가요?

나름의 변명같기도 하네요. 제 생각은 그렇다,, 입니다~ 책을 선택한 이상, 이 책을 열심히 읽고 공부해야겠죠? 마무리하고 공부하러 가겠습니다. 화이팅! O(｀・∀・´)○

• 서브젝트 한글 번역본 https://github.com/42seoul-translation/subject_ko/blob/master/push_swap/push_swap.ko.md

서론

작성하는 이유는

1. push_swap을 그리디로 풀이한 글이 별로 없어서
2. 내 코드 자랑할라고
3. 블랙홀 빠지기 전, 42글 하나는 올리려고,,,

처음에는 그냥 머지소트로 작업하려 했으나,, 100점이 안 나온다더라고요? 다른분들은 거의 투 피벗 퀵소트나 모래시계 알고리즘을 사용하셨습니다. 다 하는거 싫어서 주위에 여쭈어봤더니 "그리디"로 하신분이 계셨습니다. 저의 푸시스왑 선생님의 설명을 참고해서 해결하게 되었습니다.

그리디

Greedy 알고리즘은 "순간순간 최적의 선택"을 합니다. 매 순간 최적의 경우를 선택하기 때문에 그 과정 자체가 최적화입니다. 다른 알고리즘을 이용한 경우, 명령어들을 모두 다른 리스트에 담았다가 최적화를 시켜주시던데. 그리디는 그럴 필요 없습니다. 개쩔조?

로직

목차만 작성해보고 뒤에 천천히 설명해볼게요.

1. argv 읽어서 deque에 init 하고, 정렬된 배열하나 만들어서 data를 인덱스로 교체
2. 스택 a에 원소 3개가 남을때까지 b에 push하고, 스택 a 정렬하기 (3개 하드코딩)
3. Greedy 시작. 스택 b가 빌 때 까지 스택 b의 모든 원소들이 스택a의 올바른 위치에 이동할 때,필요하 ㄴ연산 횟수를 모두 계산하여 가장 작은 값을 가진 원소 하나만 b에서 a로 push
4. 스택 b가 비었으면, 스택 a에서 0을 찾아서 0이 front가 되도록 만들어 줌

끝 입니다. 간단하지요?

0. 구조 & 명령어

양방향 연결리스트로 구현하였습니다. 그래서 이름도 deque 입니다. 구조체는 이렇게 2개 썼어요.

deque의 이름에 맞게 명령어들을 구현에 주었습니다. 서브젝트에 제시된 명령어에 deque command를 그대로 사용했습니다.

1. 파싱

이 부분은 개인이 구현하기 나름이라고 생각합니다. 저는 이렇게 했다..

1. argv 읽어서 스택 a에 push_back
2. 동시에 int 형 arr배열에 저장
3. arr배열 정렬해서 스택 a의 data값을 정렬된 배열의 인덱스로 교체

제 핵심은 "인덱스 값으로 교체"하는 것 입니다.

이렇게 해도 됨?

ㅇㅇ 이 서브젝트는 들어온 인자를 정렬하는 "명령어를 출력"하는게 목표이기 때문에, 들어온 인자를 재사용하지 않음!!

인자가 ./push_swap 5 9 7 2 1 이렇게 들어왔다면 이제 2 4 3 1 0 으로 바꾸어주는 것.

이렇게 하면 뭐가 좋은가요!

1. 마지막에 정렬 할 때 가장 작은 값은 무조건 0이라서 편함
2. 분할 파트에서 보면 pivot 정할때 편함

이 부분을 평가에서 칭찬받아서 기분이 좋았어요

2. 분할

다른 분들이 투 피벗 퀵소트를 많이 하신다고들 하시던데, 그 부분을 참고하여 분할합니다.

저의 선생님께서 참고하신 글이 https://techdebt.tistory.com/26 이 글 이라고 하셨어요. 어.. 저의 두번째 선생님입니다. 도움을 많이 받았습니다. 어,, 근데 제가 설명하려는 말들이 다 여기에 있네요.

1. pivot 2개를 설정해서 3분할
2. 스택 a에는 pivot2보다 큰 원소만 남아있음.
3. 스택 a에 3개만 남겨놓고 전부 b로 push
4. 스택 a에 남은 3개 하드코딩

까지가 그리디 직전까지의 준비입니다.

여기서 왜 3분할을 해준후에 다 넘겨주나면, 3분할 해서 큰 집합의 순서대로 정렬하기 위함입니다. 이 부분은 직접 실행해보시거나, 두번째 선생님의 유튜브를 보시면 알 수 있습니다. 분할을 해주는 과정이 이후에 정렬을 하게 될 때, rb와 rrb를 적게 해주는 요인이 됩니다.

3. 그리디

전체적인 정리는,, 스택 b가 빌때까지 반복 b->a로 이동할 때, 가장 적은 명령을 이용하는 원소를 찾아서 push해주는 것

이 때 중요한게, a는 0이 가장 위가 아닐 뿐, 항상 정렬된 상태여야합니다.

그래서 우리는 b에서 a로 push 할 때, 앞 원소보다 크고 뒷 원소보다는 작은 위치에 정확히 push 할거에요.

예시를 들자면

a : 13 20 4 10 12

a스택이 이렇다고 합시다. 지금 4가 중간에 있지만, 4 10 13 15 20 순으로 정렬되어있죠?

b : 14 7

여기서 경우를 따져볼게요.

- 14를 push하는 경우

a : 20 4 10 12 13 b : 14 7

이 상태로 만들어서 push를 해야겠죠

a : 14 20 4 10 12 13 b : 7

이 상태가 됩니다. a에서는 ra1번, b에서 0번, 총 명령어 사용 횟수 1번입니다.

- 7을 push 하는 경우

a : 10 12 13 20 4 b : 7 14

이 상태로 만들어서 push를 해주면

a : 7 10 12 13 20 4 b : 14

이 상태가 되는거고, a에서는 rra 2번, b에서 ra 1번 총 명령어 사용 횟수 3번입니다.

그렇다면 14를 push할때가 7을 push할 때 보다 1번 < 3번으로 더 적어서, 14를 push 하게 됩니다.

이 과정을 스택 b가 빌 때 까지 계속 반복.

상세 함수들에 대해 설명을 해볼게요.

find_best

스택b의 front부터 back까지, 이 원소가 a로 이동하려면 명령어를 얼마나 써야하는지 계산함. 이거 할 때, 스택사이즈 반을 넘어가면 rb하는 것 보다 rrb하는게 더 이득이잖아요. 그래서 그 부분은 이제 + 랑 - 로 분류를 해주었습니다.

스택 b에 있는 원소가 스택 a에 들어갈 때, 알맞은 자리를 찾는 함수입니다.

뭐,, 상당히 더럽고 마음에 안들어요. 그치만 이 부분에 대한 코드를 찾기가 어려워서 제 더러운 코드를 올립니다. 제가 front->prev=NULL, back->next=NULL로 설정했기 때문에, NULL을 역참조 하지 않도록하다보니 더러워졌습니다. 어쩔수 없었어요 블랙홀 1열이었다구요

before_push 어쩌고

push 상태로 스택a랑 스택b를 변경 스택 a와 b를 같은 방향으로 동시에 돌려주는게 _all 각각 돌려주는건 _single

last_sort

스택b는 비어있고, 스택a는 정렬된 상태이지만, 0이 중간 어딘가에 있을거임. 0이 가장 상단에 위치하도록 rotate함.

정리 및 회고

100개 5점 기준 700개 통과!

500개 5점 기준 5500개 통과!

뿌듯한 사람입니다. 그치만 시간이 촉박했던만큼, 더 가독성 좋고, 줄일만한거 더 줄인 코드를 포기했음이 아쉽습니다.

푸시스왑 선생님 승훈님과 푸시스왑을 케이크처럼 퍼먹는 방법을 올려주신.. 선생님의 인트라 네임을 알고싶어요 감사합니다!!! 그리고 새벽에 같이 에러 잡아주신 조주님이랑 첫 평가자로 와주셔서 많은 것을 가르쳐주고 칭찬해주신 썬박님 감사합니다

근데 이렇게 냅다 이름 적어도 괜찮은건가요? 감사하다고 말 하기 부끄러우니까 허공에 외치는거죠 ㅇㅇ

푸시스왑 끗

LIS (Longest Increasing Subsequence)

주어진 '수열' 에서 일부 원소를 뽑아내어 새로만든 수열이 '부분 수열' 이 수열이 '오름차순' 인 수열이 '증가하는 부분 수열' 이 된다. 만들 수 있는 오름차순 수열 중, '가장 긴' 수열이 LIS가 된다.

Before Solution

DP VS Binary Search

블로그를 기제하는 이유중 핵심은 "Binary Search". 즉, 이분탐색 때문이다. LIS 유형은 DP로도 풀 수 있고, Binary Search로도 풀 수 있다.

이 전에 가장 증가하는 긴 부분 수열 문제(https://www.acmicpc.net/problem/11053)를 풀 때, DP로 풀었어서, 이 문제도 똑같이 풀었으나 "시간초과"가 난다.

*이유는 DP로 풀면 O(N^2)이지만, 이분 탐색으로 풀면 O(NlogN)만큼 걸리기 때문 *

+)DP풀이는 상당히 간단함. dp배열 만들어서 이중for문 돌리면 됨

Solution

'a배열의 원소'와 'lis배열의 마지막 원소'를 비교 O(N) -> 더 크다면 lis배열의 마지막에 추가. -> 작다면 Binary Search를 이용하여 자리 탐색 O(logN)

그림으로 보면 훨씬 이해하기 편하다.

첨언하자면 큰 값이면 뒤에 추가하고, 큰 값 보다 작은 값이면 적절한 자리를 찾아서 넣어준다. 증가하는 부분수열 {1,3,9}와 {1,3,5}가 있을때, 두 수열의 길이는 3으로 동일하다. 하지만 "가장 긴" 증가하는 부분 수열을 만들려면, 가장 뒤 원소가 최솟값인게 유리 할 것이다. 그러니까 뒤에 원소가 7일때 {1,3,9} 뒤에는 7을 못 붙이는데 {1,3,5}뒤에는 7을 붙일 수 있다는 뜻. 이해가 안 간다면 직접 손으로 계산해보길 바란다.

int j = 0;
    lis[0] = a[0];
    for (int i=0; i<n; i++){
        if (lis[j] < a[i]){
            lis[j+1] = a[i];
            j++;
        }
        else{
            int idx = binarysearch(0, j, a[i]);
            lis[idx] = a[i];
        }
    }

Binary Search

정렬되어 있는 배열 left ~ right 사이의 중간위치 mid를 구하여 array[mid]의 값과 타겟을 비교한다. -> 타겟이 mid의 값보다 작다면 : right = mid -> 타겟이 mid의 값보다 크다면 : left = mid + 1; 시간복잡도가 O(logN)

lis배열은 정렬되어있는 배열이기때문에 이분탐색으로 적절한 위치를 찾을 수 있다. 이분 탐색에 대해 이해가 안간다면 따로 알아보자.

int binarysearch(int left, int right, int target){
    int mid;
    while (left < right){
        mid = (left + right)/2;

        if (lis[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }

    return right;
}

이게 끝이다. 생각보다 간단함!

전체코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,a[1000005]={0,},lis[1000005]={0,};

int binarysearch(int left, int right, int target){
    int mid;
    while (left < right){
        mid = (left + right)/2;

        if (lis[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }

    return right;
}

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

    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];

    int j = 0;
    lis[0] = a[0];
    for (int i=0; i<n; i++){
        if (lis[j] < a[i]){
            lis[j+1] = a[i];
            j++;
        }
        else{
            int idx = binarysearch(0, j, a[i]);
            lis[idx] = a[i];
        }
    }

    cout<<j+1;

    return 0;
}

dp로 풀면 시간초과납니다.

BFS 응용

bfs로 바로 풀 수 있다. 다만 조건식이 조금 복잡하여 올리고자 한다.

구조체

typedef struct {
    int x;
    int y;
    int blk; ///벽을 뚫을 수 있는 횟수
} pos;

큐에 좌표값과 벽을 뚫었는지 안 뚫었는지의 여부를 저장해야하는데, pair을 두번 쓰기 싫어서 구조체를 만들어버렸다.

조건문

//갈인데 (0) 안 갔음
        if (x != (n - 1) && map[x + 1][y] == 0 && v[x + 1][y][blk] == 0) {
            v[x + 1][y][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk;
            q.push(temp);
        }
        //벽인데 (1) 아직 안 뚫었음
        if (x != (n - 1) && map[x + 1][y] == 1 && blk == 1) {
            v[x + 1][y][blk - 1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk - 1;
            q.push(temp);
        }

두 조건문이 다름을 알아야한다.

• 길이 0 일때 v[x + 1][y][blk] = v[x][y][blk] + 1;
• 길이 1 일때 (벽) v[x + 1][y][blk - 1] = v[x][y][blk] + 1;

적고보니 이게끝이다. 상당히 쉬운데 귀찮은 문제였다. 오랜만에 백준 푼 김에 업로드 한다.

#include <iostream>
#include <queue>
#include <stdio.h>

using namespace std;

typedef struct {
    int x;
    int y;
    int blk; ///벽을 뚫을 수 있는 횟수
} pos;

queue<pos> q;

int n, m,
    map[1005][1005] = {0,},v[1005][1005][2] = {0,};

int bfs() {
    pos p;
    p.x = 0;
    p.y = 0;
    p.blk = 1;
    v[0][0][1]=1;
    q.push(p);

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int blk = q.front().blk;
        q.pop();
//        cout<<x<<" "<<y<<" "<<blk<<"\n";

        if (x == n -1 && y == m -1)
            return v[x][y][blk];

        //갈인데 (0) 안 갔음
        if (x != (n - 1) && map[x + 1][y] == 0 && v[x + 1][y][blk] == 0) {
            v[x + 1][y][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk;
            q.push(temp);
        }
        //벽인데 (1) 아직 안 뚫었음
        if (x != (n - 1) && map[x + 1][y] == 1 && blk == 1) {
            v[x + 1][y][blk - 1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk - 1;
            q.push(temp);
        }

        // 2
        if (x != 0 && map[x - 1][y] == 0 && v[x - 1][y][blk] == 0) {
            v[x - 1][y][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x - 1;
            temp.y = y;
            temp.blk = blk;
            q.push(temp);
        }
        if (x != 0 && map[x - 1][y] == 1 && blk == 1) {
            v[x - 1][y][blk-1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x - 1;
            temp.y = y;
            temp.blk = blk - 1;
            q.push(temp);
        }

        // 3
        if (y != (m - 1) && map[x][y + 1] == 0 && v[x][y + 1][blk] == 0) {
            v[x][y + 1][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y + 1;
            temp.blk = blk;
            q.push(temp);
        }
        if (y != (m - 1) && map[x][y + 1] == 1 && blk == 1) {
            v[x][y + 1][blk -1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y + 1;
            temp.blk = blk -1;
            q.push(temp);
        }

        // 4
        if (y != 0 && map[x][y - 1] == 0 && v[x][y - 1][blk] == 0) {
            v[x][y - 1][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y - 1;
            temp.blk = blk;
            q.push(temp);
        }
        if (y != 0 && map[x][y - 1] == 1 && blk == 1) {
            v[x][y - 1][blk-1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y - 1;
            temp.blk = blk -1;
            q.push(temp);
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }

    cout<<bfs();

    return 0;
}

점화식을 세워서 푸는 문제! 난이도는 쉬운편. 백준으로 치면 실버 2~ 정도의 문제일 듯 함 좋아하는 형식의 문제라서 굳이 올린다.

[세대,차례] 의 형식으로 주어진다. n번째 세대의 p번째 차례의 완두콩의 유전형식을 구하는 문제. 정말 단순하다!!

코드

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

using namespace std;

int cong[5]={0,0,1,1,2};

int dfs(int a, int b){

    if (a == 2){
        return cong[b];
    }

    int x = b/4;
    int y = b%4;
    if (y!=0)
        x++;

    int n = dfs(a-1,x);

    if (n == 0)
        return 0;
    else if (n == 2)
        return 2;
    else {
        if (y == 1)
            return 0;
        else if (y == 0)
            return 2;
        else
            return 1;
    }
}

vector<string> solution(vector<vector<int>> queries) {
    vector<string> answer;

    for (int i=0; i<queries.size(); i++){
        int a = queries[i][0];
        int b = queries[i][1];

        if (a == 1){
            answer.push_back("Rr");
            continue;
        }

        int n = dfs(a,b);

        if (n == 0)
            answer.push_back("RR");
        else if (n == 2)
            answer.push_back("rr");
        else
            answer.push_back("Rr");

    }

    return answer;
}

9월 18일 일요일 PCCP 준비를 위해 모의고사를 풀어보는중 알 것 같은 문제의 구현이 어려워서 고민하고있는데 예지 언니가 이거 "N퀸 아니야?" 라고 하는것이다.... 와 라피신 코드 바로 뒤져서 풀었다!! 이 언니는 천재야 언니 생일축하해^^

대표를 뽑는 문제이다. 다만 2차원 배열이라 조합에 어려움을 느낄 수 있다.

백준 9663 N-Queen

https://www.acmicpc.net/problem/9663

유사한 문제를 첨부한다. N-Queen을 푼 사람이라면 바로 감을 잡을 수 있을것이다. == 먼저 풀고와라. 라피신때 코드가 도움이 되다니요 역시 42서울은 내 인생에 도움이 된다니까

Solution

dfs를 이용하여 index를 오른쪽으로 옮겨갈 것이다. 한 경우를 모두 다 찾았으면 최댓값을 갱신해준다. 이 때, 한 사람을 중복으로 체크하지않도록 v 배열을 만들어 체크하였다.

2차원 vector 함수 전달

보낼때

int solution(vector<vector<int>> ability) {
    dfs (ability,0);

받을때

void dfs(vector<vector<int>> &ability, int index){

근데 이 전달방법은 Call by Value라고 한다. Call by Reference를 하려면 &를 빼면 된다고 하는 것 같은데, 더 찾아보겠다.

수행시간

뿌듯!!

소스 코드

#include <string>
#include <vector>

using namespace std;

int v[10] = {0,};
int mymax = 0,sum = 0;

void dfs(vector<vector<int>> &ability, int index){

    if (index == ability[0].size()){ //한 경우를 다 찾았으면 합산
        if (mymax < sum)
            mymax = sum;
        return ;
    }

    for (int i=0; i<ability.size(); i++){
        if (v[i] == 1)
            continue;
        v[i]=1;
        sum += ability[i][index];
        dfs(ability,index+1);
        sum -= ability[i][index];
        v[i]=0;
    }
}

int solution(vector<vector<int>> ability) {
    int answer = 0;

    dfs (ability,0);
    answer = mymax;

    return answer;
}

map 을 이용하여 재귀호출하는 문제!

단순히 추천인을 찾아가며 10퍼센트의 이익을 더해주는 문제이다. 그러나 시간초과로 계속 고생했는데,, 그 이유에는 여러가지 요인이있다. 간단히만 정리하자면

1. MAP을 사용할 것.

• 처음에는 index의 값을 저장하여 find함수를 이용하여 풀었으나, map을 사용하니 시간복잡도가 획기적으로 낮아짐 (map의 시간복잡도가 logN이라고 한다.)

2. 10%의 이익이 1 미만일때 호출 멈추기

• 최대 재귀 호출에 1000번정도의 제한되어 있기 때문!!
• 최악의 경우 (일직선 트리일 때 ) 불필요한 호출이 계속 될 수 있음

이것만 명시하면 난이도가 높을 문제는 아닐 듯 하다. 내가 MAP에 대한 지식이 부족했었던터라, 공부하여 앞으로의 문제에서 자주 활용 할 필요가 있을 듯 하다.

처음 코드 (11~13 케이스에서 Time Out)

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

using namespace std;

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;

    //정답 배열 셋팅
    for (int i=0; i<enroll.size(); i++)
        answer.push_back(0);

    //seller 한 명 씩 계산
    for (int k=0; k<seller.size(); k++){
        string name = seller[k];
        int cost = amount[k]*100;

        //10%
        int per = cost / 10;
        cost -= per;

        int index = find(enroll.begin(), enroll.end(), name) - enroll.begin();

        while(cost != 0){ //반복

            answer[index] += cost;

            if (per < 1)
                break;

            //10%
            cost = per;
            per = cost / 10;
            cost -= per;

            //추천인 x
            if (referral[index] == "-")
                break;

            //다음 추천인
            index = find(enroll.begin(), enroll.end(), referral[index]) - enroll.begin();
        }

    }

    return answer;
}

정답 코드

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

using namespace std;

map <string, int> me;
map <string, string> par;

void dfs(string name, int cost){
    if (name == "-") return ;
    int ten = cost / 10;
    me[name] += cost - ten;

    if (ten > 0) dfs(par[name],ten);
}

vector<int> solution(vector<string> enroll, vector<string> referral, vector<string> seller, vector<int> amount) {
    vector<int> answer;

    for (int i=0; i<enroll.size(); i++){
        me[enroll[i]]=0;
        par[enroll[i]] = referral[i];
    }

    for (int i=0; i<seller.size(); i++){
        dfs(seller[i],amount[i]*100);
    }

    for (int i=0; i<enroll.size(); i++){
        answer.push_back(me[enroll[i]]);
    }

    return answer;
}

DEVOCEAN YOUNG 1기 포스터 sccc 단톡방에 올라왔는데, 포스터 보고 바로 신청했다. SK?! 너무너무 하고싶었음!!

-DEVOCEAN

https://devocean.sk.com

SK에서 운영하는 개발자 커뮤니티!

-합격

합격 문자

-발대식

2022/07/07 금

SKT타워!! 엄청 높았다.

자리에 이름표가 있었다. 맘에든다!

시간이 애매해서 빨리 갔는데 제일 먼저 도착해버렸다. 기다리면서 받은 샌드위치 먹었음!

HELLO! OT들었당

제일 왼쪽에 제가 있어요

오티가 끝난후, 다같이 치킨집으로 향했다.

와! 현직 개발자 마스터님들이랑 이야기했다.. 데보션 영 활동하면서 제일 궁금했던게 ‘현직 개발자님과의 만남’ 이었는데 이렇게 빨리 만나게 될 줄 몰랐다!!! 궁금했던것도 물어보고 다른 재미있는 이야기들도 하고 너무 조은 시간이었다!!!

Sk telecom, Sk C&C, Sk 하이닉스 등.. Sk 계열사 전부 데보션에 참여하는? 그런거라고 했는데 아무튼 머찐 사람들이 많이 왔음은 확실하다.

선물도 받았는데 이런이런 C타입 허브를 받았다 무려 html포트도 있음! 그리고 스티커 마음에 든다

음 짧고 허접한 후기이지만..

발대식에서 내가 앞으로 데보션 영으로 활동하면서 여러가지 유익하고 재미있는 활동들을 할 수 있음을 알 수 있었다. 물론 내가 열심히 노력하기에 달렸다! 지금 당장의 내가 좀 더 발전해야함을 깨달았다.

마스터님들과 함께 활동할 동기님들과 잠깐 교류한 것 만으로도 얻어가는것이 너무 많았다.

마스터님들의 이야기가 너무 재미있었다. 개발 이야기도, 다른 이야기들도!! 나도 마스터님들처럼 멋진 어른이 되고싶다!!

모든 동기님들과 이야기를 하지는 못 했지만, 그 날 함께 이야기한 동기님들이 너무 조았다. 활동하면서 친해져서 칭구하자구 할거다. 제일 첫번째 목표~

아무튼 5개월간의 활동이 너무 기대되며, 열심히 활동하겠다!! 는 다짐을 하며 마무리합니다.

외판원 순회 / Traveling Salesman problem

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것. 조합 최적화(Combinatorial Optimization) 문제로 각 변에 가중치가 주어진 완전그래프에서 가장 작은 가중치를 가지는 '해밀턴 순환'을 구하는 'NP-난해'에 속하는 문제

Solution

비트마스킹을 이용한 dp

DP사용이유를 설명하자면 메모리와 시간복잡도때문. n이 10이하인 경우는 브루트 포스(brute force)를 이용하여 구할 수 있다. 그러나 n이 16이하인 경우는 dp를 이용하여 중복 계산을 방지해주어야 한다.

비트마스킹을 이용하여 방문 상태를 표시할것이다. 비스마스킹을 사용하는 이유는, 각 정점마다 다른 모든 정점들의 방문상태를 표시해야하기 때문에 메모리를 줄이기 위해 사용한다.

대충 말 하자면 걍 dfs랑 비슷하다.

핵심 : dp[현재 방문도시][방문한 도시 (비트마스크)]에 경로값을 저장한다.

비트마스킹

정수의 이진수표현을 자료구조로써 쓰는 방법. 장점 : 빠른 실행시간, 보다 적은 메모리, 깔끔한 코드

비트연산자

사용한 연산자만 간단히 정리하자면

a&b

a의 모든 비트와 b의 모든 비트를 AND연산

a|b

a의 모든 비트와 b의 모든 비트를 OR연산

선언부

#define INF 987654321;
int n,map[16][16];
int dp[16][1<<16]; //각 마을이 방문한 도시를 2진법으로 저장

INF를 987654321로 잡았다. 더하는 연산이 있다보니 21억으로하면 오버플로우 난다. (틀렸었던 이유) map은 이동하는 비용, dp는 총 비용

dp배열 초기화

memset(dp, -1, sizeof(dp)); //dp배열 -1로 초기화

map배열을 입력받고 dfs를 실행하기 전, dp배열을 모두 -1로 초기화한다. 방문여부를 파악하기 위함이다.

dfs

문제 조건에서 항상 순회할 수 있는 경우만 입력으로 주어진다. 라고 제시를 해주었기때문에 dfs한바퀴만 돌려도 정답이 나온다.

int dfs(int cur, int visit)

dfs는 현재 도시 cur과 지끔까지 방문한 도시 visit을 받는다.

if (visit == (1<<n)-1){ //탐색 완료
        if(map[cur][0] == 0) //이동불가능
            return INF;
        return map[cur][0];
    }

 (1<<n)-1는 모든도시들의 방문 여부입니다. 참고로 1이 n개 (111~)

if (dp[cur][visit] != -1) //이미 탐색했으면
        return dp[cur][visit];

    dp[cur][visit] = INF;

처음에 입력받고 dfs 실행 전에 memset을 이용하여 전부 -1로 초기화 해놓았기 때문에, -1일때만 탐색

for (int i=0; i<n; i++){
        if (map[cur][i]==0) //길 X
            continue;
        if ((visit & (1<<i)) == (1<<i)) //이미 방문
            continue;
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1<<i));
    }

    return dp[cur][visit];

가장 중요한 부분!! 먼저 해당하는 도시로 갈 수 있는지 확인 하고 방문 여부를 파악한다. 그 다음이 핵심인데 처음시작 -> 현재도시 로 가는 거리와 현재도시 -> 방문하지않은 다른 도시로 가는 거리 중 작은것을 dp배열에 저장한다. 여기서 visited | (1<<i)를 사용하는 이유는 현재도시를 방문했다는 의미에서 사용한다.

전체코드

#include <iostream>
#include <cstring>
using namespace std;

#define INF 987654321;

int n,map[16][16];
int dp[16][1<<16]; //각 마을이 방문한 도시를 2진법으로 저장

int dfs(int cur, int visit){

    if (visit == (1<<n)-1){ //탐색 완료
        if(map[cur][0] == 0) //이동불가능
            return INF;
        return map[cur][0];
    }

    if (dp[cur][visit] != -1) //이미 탐색했으면
        return dp[cur][visit];

    dp[cur][visit] = INF;

    for (int i=0; i<n; i++){
        if (map[cur][i]==0) //길 X
            continue;
        if ((visit & (1<<i)) == (1<<i)) //이미 방문
            continue;
        dp[cur][visit] = min(dp[cur][visit], map[cur][i] + dfs(i, visit | 1<<i));
    }

    return dp[cur][visit];
}

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin>>n;
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            cin>>map[i][j];
        }
    }

    memset(dp, -1, sizeof(dp)); //dp배열 -1로 초기화
    cout<<dfs(0,1);

    return 0;
}

틀린 이유 첫번쨰는 cstring 미선언, 두번째는 INF 오버플로우

CCW / Counter Clockwise

CCW란?

평면 위에 놓여진 세 점의 방향관계를 구할 수 있는 알고리즘 점 a,b,c를 순서대로 검사하여 반시계방향으로 놓여있으면 양수를, 시계방향이면 음수를, 평행하면 0을 리턴한다. 기하 알고리즘의 한 종류입니다.

벡터의 외적

좀 더 부가적인 설명을 해보자면, 두 벡터의 결과를 행렬식으로 나타내어보자.

여기서 S의 부호에 따라서 세가지로 나눈다.

• s > 0 : 반시계방향
• s = 0 : 일직선
• s < 0 : 시계방향

구조체 구현

struct pos {
    int x,y;
};

간단하게 x,y좌표로 나타내었다. 매번 pair만 썼는데 구조체 깔끔하고 좋은 듯.

핵심 코드

long long tmep = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);

행렬식을 그대로 이용하여 코드를 짰다. 깔끔하다.

내 코드

long long temp = a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);

나는 저 방법을 알기전에 신발끈 공식을 이용하여 코드를 짰다. 다만 코드가 길어지니 나도 다음부터는 위 코드를 이용할 생각이다.

전체코드

#include <iostream>
using namespace std;

struct pos {
    int x,y;
};

int main(int argc, const char * argv[]) {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    pos a,b,c;
    cin>>a.x>>a.y;
    cin>>b.x>>b.y;
    cin>>c.x>>c.y;

    long long temp = a.x * b.y + b.x * c.y + c.x * a.y - (b.x * a.y + c.x * b.y + a.x * c.y);

    if (temp < 0)
        cout<<"-1";
    else if (temp > 0)
        cout<<"1";
    else
        cout<<"0";

    return 0;
}