부트캠프 멘토링 중 부트캠프 프로젝트의 도전 과제가 1인 MSA 프로젝트로 나왔는데,

많은 멘티들이 MSA의 개념을 모르거나, 구현하는 데에 많은 어려움을 겪고 계셨다.

그 와중 넥스트스텝에서 카카오, 무신사, 우형등의 기술이사를 맡고 계셨던, 객체지향의 사실과 오해라는 책을 집필하셨던

조영호 강사님의 DDD 세션이 열려서 들으러 갔다가 마침 알고만 있던 개발자분과 같이 세션을 듣게되어서 만나뵙고 식사를 하게 되었다.

 

작년 중순 즈음 처음 개발 단톡방에서 뵌 것 같은데, 항상 열심히 사시고 열심히 공부하고 계신 것 같아, 처음으로 용기를 내어 친한 개발자가 아닌, 다른 개발자분께 커피챗을 신청하게 되었다. 나는 항상 소심하고 폐를 끼치기 싫어서 커피챗을 신청하지 못했는데, 이 분은 한번은 꼭 뵙고 싶었다.

 

다음 질문들을 하고 싶었다. 물론 내가 이렇게 따라가고자 여쭌 건 아니고, 많은 사람들의 고견을 들으면서 선택지를 넓히고 싶었다.

  • 언제부터 개발을 시작하셨는지?
  • 공부 방법을 어떻게 가져가시는지?
  • 개발에 대해 어떤 생각을 가지고 계신지?
  • 신입 / 주니어때는 어떤 공부를 해야 할지?
  • 그 외에 개인적인 질문들

전공자라고 하셔서 정말 개발을 열심히 하셨을 것 같은데, 생각외로 그런건 아니고 대학 시절때 열심히 게임을 하면서 시간을 보내셨다고 했었다. 그래서 친구분들은 다 대기업에 계신데, 혼자 그러지 못해 작년에 조금 불안한 시간을 보내셨다고 한다. 물론 그래도 올 해 너무나 좋은 회사를 가셨지만.

이 말부터 굉장히 공감했다. 내 학창시절 친구들도 대학교때라도 개발을 시작한 친구들은 다들 다른 회사에서 CTO를 하고 있거나, 네카라쿠배의 개발자를 하고 있으니까. 그래서 내가 조금 더 급했는지도 모른다.

 

그래서 그런지는 모르겠는데, 사실 이 커피챗을 신청한 이유를 관통하는 대화였다.

요즘 개발이 너무 재미있는 시즌이기도 하고 성장에 메말라있던 때라, 또 내 욕심때문에도 계속 모르는 분야를 줄이고 싶었다. 그런데 '개발'이라는 필드가 너무나 광범위하기도 하고, 주위에 다들 잘하는 개발자들만 있으니 항상 이야기를 할 때 모르는 단어들이 너무 많이 나왔다. 그래서 계속 탐구하다보니 깊이보다도 계속 지식의 범위가 수평적으로만 확장되고, '이걸 다 어떻게 공부하지...'라는 생각만 들고, 결국에는 공부하려고 했던것들만 쌓이고 받아들이는 것은 한정되는, 소위 말하는 '체하는 현상'이 발생하기 직전이었다.

 

그래서 이것저것 너무 '찍먹'만 하고 있다고 생각했는데, 이분께서도 신입 시절은 기초를 탄탄히 하면서 퍼포먼스에 집중하는 때를 보내는게 어떻겠냐고 말씀하셨다. 너무 맞는 말이라 반박할 수가 없었는데, 현재 회사를 다니면서도 가장 힘든 부분이 디버깅을 하며 코드 플로우를 분석하는 것인데, 이걸 위한 공부보다는 내가 좋아하는 분야, 내가 개발하고 싶은 분야만 공부하고 있는게 아닌가 하는 생각이 들었다. 물론 회사에 도움되는 개인 프로젝트긴 해도, 백투베이직에 조금 더 신경써야 했었는데...

 

그래서 나온 대화가, 회사에서의 겸업 금지 조항이었다.

이분의 회사는 겸업을 원천적으로 금지하고 있었다. ~~콘에 나가서 강연을 하는것은 물론이고, 작은 멘토링까지 전부 금지 규정에 포함되어 있었다. 생각해보니 유명한 스타트업에 가 계심에도 불구하고, 이 회사에 대한 어떤 기술 블로그나 강연자를 본 적이 한 번도 없었다. '회사에 베스트 퍼포먼스를 보이러 왔지, 타 업무로 회사에 지장이 가는 어떤 일도 금지하자'라는 게 핵심인데, 그래서 회사에서 친목도모를 위한 업무시간 외의 모임이나 만남도 금지하고 있었다. (너무 사적인 모임 등) 중요한 결정의 순간에, 조금의 추가적인 정이 최선의 결정을 방해할 수 있다는 것이 그 이유였다.

 

어떻게 생각해보면 조금 가혹하다고 할 수도 있으나, 우리 회사에서 개발자들이 '왜 개발 외의 타 업무까지 해야하나'라는 상황을 고려해보건대, 정말 프로페셔널하다고도 생각했다. 대신 복지나, 다른 베네핏에 대해서는 확실하게 보장해 준다고도 했다. 그래서 사내에서는 워커홀릭도 많다고 하셨다. 베네핏 뿐 아니라 회사 내의 커뮤니케이션 또한 워커홀릭을 만들고 있었는데, B2B 기업과는 달리 B2C 서비스 기업이라 마케터들이 원하는 그런 기능을 개발할 때 오는 피드백이 큰 도파민을 가져다준다고 하셨다.

 

그래서 말씀드린 것이, 나는 강남언니처럼 테크블로그가 있는, 사내 개발 실력 증진도 좋지만 외부에도 사내 개발에 대한 이야기를 풀어갈 수 있는 컬쳐를 가진 회사가 너무 부럽다고 했다. 내가 처음 개발공부를 할 때 물론 개인 블로그에서도 인사이트를 많이 얻었지만, Naver D2, 우아한테크블로그, 강남언니등의 회사 블로그에서도 양질의 좋은 글을 많이 읽었기 때문이었다. 내가 개발자가 된 이유와도 얼추 겹쳐보여서 멋있다고 말씀드렸더니, 그것또한 공감을 해 주셨다.

 

외에도 많은 이야기를 나누었다. 자신이 정말 좋아해서 커피챗을 신청하기 위해 정말 긴 편지까지 써서 만났던 개발자에게 취직 축하를 받은 이야기, 사내에서 개발한 기능들이 어떻게 반영되는지, 또 본인이 다니고 있는 회사에 대해 어떻게 생각하는지, 지금 앞둔 목표는 무엇인지 등등, 정말 이야기 하는 내내 즐거워서 시간이 가는 줄 몰랐다.

 

이야기를 듣는 내내 T스러움이 정말 많이 느껴졌는데, 본인의 의견을 강단있게 말씀하시면서도 겸손까지 갖추신 모습을 보니 멋있었다. 사실 나도 멘토활동을 하면서 항상 '제가 뭐라도 되는 사람은 아니지만'이라고 했을 때 그래도 나에게 항상 응원과 환호를 보내주신 멘티님들이 이해가 됐다.

 

그래서 결론은, 지금 하고 있는 개발 공부까지만 해 보고, 이제는 회사에서 사용하는 기술스택에 대한 딥다이브를 해야겠다고 생각했다. 또, 새로운 목표를 가지게 되었다.

'잡설 > 개발자를 만나고' 카테고리의 다른 글

230708  (1) 2023.07.13

튜터로 학생들의 알고리즘 코드를 봐 주다가 다음 문제를 마주쳤다.

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

 

문제만 본다면 평범한 알고리즘 문제이지만, 다음 과정에서 문제가 있었다.

백준은 어떤 부분이 틀렸는가에 대해 제공하지 않기에 학생들은 스스로 반례 또는 틀린 코드를 찾고 있다가, 어느 코드가 틀린지 몰라 나에게 도움을 얻으러 왔다.

나도 분명히 이분탐색 로직에는 문제가 없는것 같아 어느 부분에서 틀렸지 찾다가, 다음을 바꿔보니 맞는 코드가 되었다.

int percentage1 = (int)((double)x * 100 / y);
int percentage2 = (int)((double)x / y * 100);

어떤 수식이 틀렸고, 어떤 수식이 맞을까?

부동소수점 이슈는 소수점 계산할 때 항상 나오는 이슈라 항상 알고는 있지만, 실제로 문제를 복기하며 무엇이 틀렸는지 찾을때는 부동소수점 이슈를 발견하기가 굉장히 어렵다.

마치 long type을 써주지 않아 overflow가 났을 때처럼.

일단, 문제를 해결하기 위해 어느 부분에서 문제가 터졌는지 확인하기 위해 살짝 코드를 짜 보았다.

public class Main {
    public static void main(String[] args) throws IOException {
        for (int x=0; x<100; x++){
            for (int y=1; y<100; y++){
                int z1 = (int)((double)x * 100 / y);
                int z2 = (int)((double)x / y * 100);
                if (z1 != z2 && x < y){
                    System.out.println("z1 = " + z1);
                    System.out.println("z2 = " + z2);
                    System.out.println("x = " + x);
                    System.out.println("y = " + y);
                }
            }
        }
    }
}

x와 y를 변환시켜 주면서, 위의 두 수식이 달라질 때를 찾았다.

그리고, 다음 결과를 발견할 수 있었다.

z1 = 58
z2 = 57
x = 29
y = 50

x = 29, y = 50일 때, z1는 58%를, z2는 57%를 반환했다.

정확하게 보기 위해 z1과 z2를 double로 바꾸었더니, x=29, y=50에 대해 다음을 반환했다.

z1 = 58.0
z2 = 57.99999999999999

상식상 29/50은 58%가 되어야 하기에, z1이 맞는 수식임을 알 수 있다.

따라서, 퍼센테이지를 나타낼 때 분자를 크게 가져가야만 소숫점을 잘 출력하는 것을 알 수 있다.

분자가 더 큰 경우에도 마찬가지다.(x>y)

9900가지 경우 중 39건의 경우에서 다른 결과를 반환했다.

이 경우에도 z1이 z2에 비해 조금 더 정확한 결과를 도출해 냄을 알 수 있다.

따라서 결과는 다음과 같다.

퍼센테이지 등의 결과를 도출해 낼 때에는, 항상 분자를 크게 가져가는것이 조금 더 정확하다.

글을 쓰다보니 사실 어떻게 생각해보면 당연한 결과긴 하지만, 그래도 오랜만에 한번 짚고 넘어갈 문제라 포스팅을 해 보았다.

길고 긴 방황을 끝내고 회사에 첫 출근을 했다.

앉아서 팀장님과 커피챗을 나누고 있는데, 마이바티스에 대한 이야기가 나왔다.

"저는 프로젝트 할 때 ORM으로 마이바티스 대신 JPA를 써서요" 라고 했더니 돌아오는 답변

"마이바티스는 ORM이 아닌데?"

"?????"

백엔드 공부를 얼마 하지 않은 입장에서 [프레임워크 + 프로젝트 관리 도구 + ORM]의 한 세트를

'Spring + Maven + MyBatis'와 'Spring Boot + Gradle + JPA'로 이해하고 있었다.

 

글을 읽는 사람도, 나도 하도 많이 들어서 다음 3가지는 알고 있을 것이다.

- JPA는 자바 진영의 ORM 표준이고, 이를 구현한 것이 Hibernate이다.

- ORM은 OOP를 지향하는 언어와 DB의 relation을 맺어주는 기법이다.

- Gradle은 Maven보다 현저히 빌드 속도가 빠르고 스크립트가 짧다.

 

이렇게 현대의 김영한님 강의를 듣고 자란 사람들이나 국비교육이 아닌 사비 부트캠프를 다닌 사람은 보통 jpa, gradle, spring boot에 대해서는 이해도가 높지만, 반대로 maven+mybatis를 이해하는 경우는 잘 없다.

 

일단 mybatis는 ORM이 아니다. myBatis는 SQL 매핑 프레임워크다.

JPA와 비슷하지만, 객체를 매핑해준다기보다 SQL안에 객체의 프로퍼티들을 잘 넣을 수 있게 한다.

JPA도 동적 쿼리를 지원하지만, myBatis는 조금 더 세밀한 쿼리 튜닝을 가능하게 한다.

 

다음에는 myBatis를 이용한 쿼리튜닝을 포스팅을 해야겠다.

 

 

'DB' 카테고리의 다른 글

DOCKER로 MySQL 다루기  (0) 2023.08.24
POSTGRESQL - RDB  (0) 2023.08.19
POSTGRESQL - 분노의 설치  (0) 2023.08.19

개괄


 

Jira나 Linear을 이용하다보면, 가끔 내가 해결한 티켓들을 그대로 고이 모셔 두기가 너무 아깝다.

같은 프로젝트를 하더라도, 내가 이 사람보다 월등히 일을 많이 해결했는데 인정받지 못하는 순간이 아쉬워서

어떤 프로젝트(또는 회사) 안의 SubTask를 만들고, 그 Task 안에서 Ticket을 발부할 때마다 티켓의 중요도와 난이도를 가지고 인사평가를 할 수 있는 프로젝트를 만들었다.

 

그런데 프로젝트 도중 내부 회의를 하다가 이상한 점을 발견했다.

그동안의 점수 로직은 0~5까지의 0.5단위의 점수를 매길 수 있는 중요도와 난이도를 그냥 합산한 수치로 계산했는데,

나는 어쩔때는 예상 밖의 예외에 집착하고 많은 엣지케이스를 실험해 보는 습관이 있어서

내가 짠 로직들에 대해 악감정을 가지고 어떻게 해야 개발자를 골려먹을 수 있을까에 대해 실험해 보았다.

 

결과적으로는 이 로직을 악용하기에 충분했다. 모든 난이도와 중요도를 5점으로 설정해 놓으면 모든 사원이 만점을 받고, 정상적으로 난이도와 중요도를 매긴 타 업체나 타 프로젝트들에 비해 이 사람이 어떤 능력을 가진 사람인지 예상하기 힘들었고, 편애를 받는 사람은 그 사람이 가진 티켓의 난이도나 중요도만 상위 직급에 있는(Subtask나 Project장) 사람이 올려놓으면 다른 사람의 질타를 받기 충분했다.

 

토의


그럼 이 문제를 어떻게 해결할까 하다가 대학교 2학년때 배운 선형대수가 떠올랐다.

바로 'Weight Sum(가중합)'을 이용하는 것이다.

가중합이라고 하면 이름만 어렵지 사실은 우리가 옛날에 배운 기초 수학이다.

먼저, 우리가 여태 사용하던 평균을 구하는 공식을 가지고 예를 들어 보자.

  국어 수학 음악 평균
영준 70 80 90 80
대현 100 100 40 80

영준이와 대현이는 공부를 열심히 했으나 둘 다 평균 80점을 받았다.

그런데 사실 대현이는 불만이 있었다. 수업 시수는 국어와 수학이 압도적으로 많은데, 비교과 내신인 음악 과목 때문에 결국 똑같은 평균 취급을 받아야 한다니..

대현이는 바로 교장선생님께 달려가서 이 부당함을 일렀고, 교장선생님은 이런 부당함을 없애기 위해 조치를 취했다.

바로 평균을 낼 때, 수업 시수를 고려한 평균을 내는 것이다.

  국어 수학 음악 평균
수업 3 5 2  
영준 70 80 90 79
대현 100 100 40 88

영준이는 ( 3 * 70 + 5 * 80 + 2 * 90 ) / (3+5+2) 인 평균 79점이,

대현이는 ( 3 * 100 + 5 * 100 + 2 * 40 ) / (3+5+2) 인 평균 88점이 나오게 됐다.

이렇게 영준이는 조금은 억울하지만 물론 쉬운 음악 과목을 날먹했으므로 억울함은 토로할 수 없었고,

대현이는 중요한 내신인 국어와 수학을 열심히 공부해서 좋은 평균을 냈으니 이보다 더 공정할 수는 없었다.

벡터의 내적또한 사실 가중합 방식과 같다.

이렇게 둘은 공평한 점수를 얻게 되었다.

이것이 가중합 방식이고, 수업 시수는 가중치라고 생각하면 된다.

이 방식을 이용해 조금 더 공평한 점수를 구할 수 있다.

 

적용


이를 적용하여 나름 공평한 시스템을 설계할 수 있었다.

  1. 티켓과 그 티켓을 담고 있는 하나의 '일'인 Task에 대해서 얼마나 진행되었는지를 조사한다.
    1. 티켓이 완료되지 않았다면 이 티켓에 대해 점수를 줄 수 없어야 하고,
    2. 티켓을 처리하여 완료시간이 나왔다면, 전체 진행도에 비해서 이 티켓을 얼마나 빨리 끝냈는가를 체크한다.
  2. 진행도는 '분 단위'를 기준으로 계산한다.
  3. 그리고는 아까 계산한 평균처럼 점수 * 가중치 / 전체를 계산한다.

DTO로 매핑하기 위한 소스코드를 첨부한다. 매핑 프레임워크는 Mapstruct를 사용하였다.

@Named("calculateScore")
default double calculateScore(Ticket ticket) {
    Task task = ticket.getTask();
    if (ticket.getCompletedAt() == null) {
        return 0;
    } else {
        double taskProgress = task.getExpiredAt() == null ? 0.0d : checkTicketDurationWithTask(ticket);
        double difficultyWeight = 4;
        double priorityWeight = 4;
        double taskProgressWeight = 2;
        return (ticket.getDifficulty() / (double)task.getTotalDifficulty()) * difficultyWeight +
            (ticket.getPriority() / (double)task.getTotalPriority()) * priorityWeight +
            taskProgress * taskProgressWeight;
    }
}
/*
 * 1. 티켓과 task의 expiredAt의 자유도를 고려한다.
 */

default double checkTicketDurationWithTask(Ticket ticket) {
    if (ticket.getCompletedAt() == null || ticket.getCompletedAt()
        .isAfter(ticket.getTask().getExpiredAt().plusDays(1).atStartOfDay())) {
        return 0;
    } else {
        long now = ChronoUnit.MINUTES.between(ticket.getCreatedAt(), ticket.getCompletedAt());
        long total = ChronoUnit.MINUTES.between(ticket.getCreatedAt(),
            ticket.getTask().getExpiredAt().plusDays(1).atStartOfDay());
        return now / (double)total;
    }
}

쉽게 예를 들기 위해 가중치를 보이게 설정했으나, Property 파일에 담아서 암호화해줄 수 있다.

 

결론 및 더 발전할 점


이 방식을 이용해서 조금 더 공정한 점수 방식을 채택할 수 있었다.

이 글만 읽어보면 또 개인이 한 태스크에 한 티켓만 만들면 어떡하나요 라는 문제점을 제기할 수도 있지만,

B2B SaaS 프로젝트를 생각하고 만들었기에 1인이 어뷰징하는 일은 상관 없으며,

프로젝트나 태스크를 만들고 티켓의 난이도나 중요도를 설정하는 것은 각자의 역할을 잘 설정함으로서 해결하였다.

이를테면, 프로젝트의 장은 그 프로젝트 아래의 모든 태스크를 총괄할수 있으며, 태스크의 장은 그 태스크 안의 모든 티켓을 총괄할 수 있다. 또 그 태스크 예하에 라벨(팀)을 설정하여 이런저런 설정과 권한을 부여할 수 있다.

 

프로젝트를 조금 더 돌볼 시간이 있었더라면, 개인적으로는 Kafka를 이용해 티켓을 등록할 때마다 태스크 내의 참여인원들에게 SSE로 Noti를 줄 수 있다거나 스케쥴링을 이용해 태스크가 완료되지 않았더라도 실시간 점수를 계산해서 보여주는 시스템을 만들고 싶었다.

 

다음 진행할 사이드 프로젝트에서는 이를 보완하여 조금 더 안전한 시스템을 만들어볼 생각이다.

그리디 문제를 풀다보면, 우선순위 큐가 필요할 때가 종종 등장한다.

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

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

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

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

www.acmicpc.net

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

 

1202번: 보석 도둑

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci

www.acmicpc.net

이런 문제들이 우선순위 큐를 가지고 풀어야 하는 문제다.

물론 다른 방식으로 풀 수 있지만, 시간초과가 발생하는 경우가 많다.

 

이 문제들은 왜 우선순위 큐가 필요할까? 또 우선순위 큐를 어떻게 이용할까?

 

첫 번째, '카드 정렬하기(1715)'문제를 보자.

카드 정렬하기 문제의 핵심은 '고르는 순서'다.

문제의 설명에 나온 대로 10장, 20장, 40장의 카드 묶음이 있을 때, (10+20)을 묶고, 이 30장짜리 카드묶음을 (30+40)으로 또 묶어버리면 100번의 비교가 필요하지만, (10+40)을 묶고, 50장짜리 카드묶음을 (50+20)으로 묶어버리면 120번의 비교가 필요하다. 

결국 첫 번째 방법은 10 + 20 + 30(10+20) + 40 = 100이고

두 번째 방법은 10 + 40 + 50(10 + 40) + 20 = 120으로 해석할 수 있다.

따라서 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미치는 것을 알 수 있다.

묶음의 개수는 정해져 있으므로, 카드의 개수가 작은 순서대로 먼저 합쳐야 한다는 것을 알 수 있다.

그래서 작은 묶음의 데이터 2개를 뽑아서 계속 비교해나가므로 삽입, 삭제, 정렬이 자주 일어난다는것을 알 수 있다.

 

두 번째 문제로, '강의실 배정(11000)' 문제를 보자.

강의실 배정하기의 문제의 핵심은 '수업을 최대한 겹치지 않게' 배정하는 것이다.

수업 시작시간을 기준으로, 가장 빨리 끝나는 시간을 비교해서 같은 강의실 안에 최적으로 배치해서 최소한의 강의실을 이용해야 한다.

따라서 (1,3), (2,4), (3,5)의 수업이 주어졌을 때, 가장 일찍 시작하는 수업을 먼저 배치하고, 그 다음 수업들을 비교해서 다른 수업의 시작시간이 처음 고른 수업의 종료시각보다 느리면 우선순위큐에 넣는다.

위의 예제를 이용해 말로 풀어서 설명하면, 1시부터 3시까지 진행하는 수업을 강의실에 배치하고, 2시부터 4시까지 진행하는 수업은 아직 강의실이 비지 않았으니 새로운 강의실에 배치한다(pQueue.offer). 3시부터 5시까지 진행하는 수업은 우선순위큐의 top을 봤을 때(pQueue.peek) 3시에 끝나는 수업이 있으므로 이 수업을 꺼내고, 3시부터 5시까지 진행하는 수업을 넣는다.

결국 마지막에 남는 우선순위 큐에는 (2,4) (3,5)가 남고, 이 큐가 결국 필요한 강의실의 개수가 되는 것이다.

우선순위 큐를 사용하지 않으려면 강의를 전체 배정하고, 시작시간을 기준으로 정렬한 뒤 강의를 매번 돌면서 겹치지 않는 수업을 지워줘야 한다. ArrayList의 조회 시간복잡도는 O(1)이지만, 삽입과 삭제의 시간복잡도는 O(N)이기 때문에 조회와 삽입/삭제를 같이 해주어야 해서 N*N의 시간복잡도가 걸리기 때문에 최대 (200,000) * (200,000)의 연산을 하게 된다.

이 또한 삽입, 삭제, 정렬이 자주 일어나는 문제임을 알 수 있다.

 

마지막으로, '보석 도둑(1202)' 문제를 보자.

보석 도둑 문제의 핵심은 '가방의 무게보다 같거나 작은 최소 무게로 최대한의 가격'을 내야 한다.

무게, 가격이 (1,65), (5,23), (2,99)인 보석과 무게가 각각 (10), (2)인 가방이 있을 때

첫번째와 두 번째 보석을 훔친다면 65+23 = 88의 가격을 낼 수도 있지만,

첫번째와 마지막 보석을 훔친다면 65+99 = 164의 가격을 낼 수 있다.

그래서 가방의 무게를 기준으로 들어갈 수 있는 보석의 list를 나열해서 가격이 최대인 보석을 넣어야 한다.

그런데 각 가방의 무게를 기준으로 들어갈 수 있는 보석을 전부 나열해서 고르고, 보석 리스트에서 제거하려면 어마어마한 시간이 소요되게 된다.

그래서 보석과 가방의 무게를 기준으로 정렬한 뒤, 보석의 리스트를 새로 갱신하지 않고 우선순위 큐에 추가해서 가격이 높은것만 빼주는 것이다.

먼저 보석을 무게순으로 정렬하면 (1,65) , (2,99), (5,23)이 될 것이다.

그 다음 가방의 무게가 2라면 첫번째 보석과 두 번째 보석을 우선순위 큐에 넣고, 그 중 가격이 가장 높은 (2,99)보석을 택한다. 그 다음 무게가 10인 가방이 있으므로 나머지 보석 리스트에서 무게가 10 이하인 보석들을 전부 우선순위 큐에 넣는다. 그러면 (1,65), (5,23)중에서 또 밸류가 높은 보석을 뽑으면 된다.

 

이 3개의 문제를 봤을 때, 공통점은 '삽입, 삭제, 조회가 빈번하느냐'이다.

그런데 '삽입, 삭제, 조회가 빈번하느냐'에 무조건 우선순위 큐를 쓰냐고 하면 그런건 또 아니다.

에초에 삽입/삭제/조회시간을 줄이기 위해서 알고리즘을 풀기 때문에...

그렇다고 문제 유형을 일일히 외워두고 '이런 유형은 무조건 우선순위 큐를 써야지'라고 생각하면 또 안된다.

두 번째 문제와 비슷한 '회의실 배정(1931)' 문제를 보자.

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

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

정말 비슷하게 생긴 문제지만, 이 문제는 우선순위 큐가 사용되지 않는다.

회의실을 1개만 사용하기 때문에, 겹치지 않는 회의를 최대한 밀어넣으면 끝이기 때문이다.

 

그럼, 언제 우선순위 큐를 사용해야 하는 것일까?

1번, 2번, 3번 문제를 보면, 공통적으로 나타나는 특징이 하나 있다.

남아있는 리스트를 계속 사용하면서, 어떤 시점에서 재조회를 하지 않고 최대/최소를 찾아야 한다.

카드 정렬하기 문제를 보면, 카드 뭉치를 하나씩 사용하면서 다시 그 뭉치를 이용한 최솟값 조회를 해야 한다.

강의실 배정 문제를 보면, 가장 빨리 끝나는 강의실을 갱신하면서 다른 강의의 시작시간을 조회해야 한다.

보석 도둑 문제를 보면, 주어진 무게 이하의 무게에서 가치의 최댓값을 조회해야 한다.

 

따라서, 조회가 빈번하게 일어나는 상황 속에서, 기존의 데이터를 포함해서 계속 갱신을 해나가며 최댓값/최솟값을 찾을 때 우선순위 큐를 이용해야 한다는 결론에 도달한다.

 

기존 데이터의 마지막 값만을 참조하는 스택을 이용하는 문제와는 다르다.

개인적으로는, '이런 문제는 우선순위 큐다 / 스택이다' 보다는, 계속 문제를 풀어보면서 스택을 이용하는지, 또 우선순위큐를 이용하는지 감을 익히는것이 제일 중요하다고 생각한다.

'알고리즘' 카테고리의 다른 글

이진 탐색, 이분 탐색  (0) 2023.10.04
구간합 & 투 포인터 & 슬라이딩 윈도우  (0) 2023.09.27
탐색(2) - BFS  (0) 2023.09.17
탐색(1) - DFS  (0) 2023.09.11
DP  (0) 2023.09.07

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력


첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

출력


첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

풀이


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static int[] entry;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		entry = new int[N];
		for (int i=0; i<N; i++){
			entry[i] = Integer.parseInt(br.readLine());
		}
		Arrays.sort(entry);
		long start = 0;
		long mid = 0;
		long end = 1000000000000000001l;
		while (start <= end){
			mid = (start + end) / 2;
			long count = 0;
			for (int i=0; i<N; i++){
				count += mid/entry[i];
				if (count > M) break;
			}
			//받을수 있는 사람이 승객보다 적다면 총 시간 늘려줘야함
			if (count >= M){
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}
		end = Math.min(end, mid);
		//최소 시간 출력
		System.out.println(end+1);
	}
}

해설


프로그래머스에 동일한 문제가 올라갈 만큼의 well-known한 문제이다.

https://school.programmers.co.kr/learn/courses/30/lessons/43238

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

이분탐색의 대표격인 만큼 다음 2가지는 꼭 알고 가야한다.

  • Sorting
  • 상한(Upper Bound)과 하한(Lower Bound)

소팅은 꼭 필요한 경우가 있고, 필요하지 않은 경우도 있다.

예를 들어,

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

 

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

이런 '순서'가 문제 풀이의 핵심인 문제들은 반드시 소팅을 해야 한다.

그러나 '매개변수 탐색(Parametric Search)'과 같은, '순서'보다는 '크기''개수'가 중요한 문제들은 소팅이 필요 없거나, 시간이 조금 더 단축된다. 나무 베기, 랜선 자르기 등과 같은 문제가 이에 해당한다.

 

상한과 하한은 문제를 해석할 때 다음을 생각해 보면 된다.

  • 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치 => 하한
  • 찾고자 하는 값 초과의 값이 처음으로 나타나는 위치 => 상한

다음 배열을 보자.

Arr =      | 1 | 2 | 3 | 3 | 4 | 5 | 7 | 8 | 9 |

index =    0   1   2   3   4   5   6   7   8

 

3 이상의 값이 처음으로 나타나는 인덱스 = 2

2를 초과하는 값이 처음으로 나타나는 인덱스 = 2

그래서 사실은 하한과 상한 둘 다의 방법으로 풀 수 있으나, 

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

 

10816번: 숫자 카드 2

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0

www.acmicpc.net

위의 문제처럼 가끔은 하한과 상한 문제 두 가지 전부를 이용해서 풀어야 하는 문제도 존재한다.

각각을 위의 배열을 이용해 슈도 코드로 이용해서 나타내보자.

Arr =      | 1 | 2 | 3 | 3 | 4 | 5 | 7 | 8 | 9 |

index =    0   1   2   3   4   5   6   7   8

  • 하한을 이용해 3 이상의 값이 처음으로 나타나는 구간
int start = 0;
int end = 8;
int target = 3;
while (start < end) {
	int mid = (start + end) / 2;
    if (target <= arr[mid]){
    	end = mid;
    } else {
    	start = mid + 1;
    }
}
return start;
  • 상한을 이용해 3을 초과하는 값이 처음으로 나타나는 구간
int start = 0;
int end = 8;
int target = 3;
while (start < end) {
	int mid = (start + end) / 2;
    if (target < arr[mid]){
    	end = mid;
    } else {
    	start = mid + 1;
    }
}
return start;

물론, while 뒤에 start <= end를 함으로써 end를 mid - 1해줄 수도 있고, if 안의 조건을 바꿀수도 있다.

문제의 조건을 보고, '이분 탐색'이다 싶으면 이를 변경해주면 된다.

 

다시 문제로 돌아와서, 이 문제는 '최소한의 시간'으로 '주어진 만큼의 승객'을 받으면 된다.

따라서, count를 만족하는 최소한의 시간이므로 6명의 탑승객이 탑승해야 한다면

- 5명을 초과하는 최소의 시간(상한)

- 6명 이상인 최소의 시간(하한)

중 하나를 이용해 풀이하면 된다.

while (start <= end){
    mid = (start + end) / 2;
    long count = 0;
    for (int i=0; i<N; i++){
        count += mid/entry[i];
        if (count > M) break;
    }
    //받을수 있는 사람이 승객보다 적다면 총 시간 늘려줘야함
    if (count >= M){
        end = mid - 1;
    } else {
        start = mid + 1;
    }
}
end = Math.min(end, mid);
//최소 시간 출력
System.out.println(end+1);

처음에 시간을 최대한으로 많이 잡아놓고,

각각의 카운터를 배열로 설정한다.

카운터 1번이 입국심사를 받는 데 7분이 걸리고, 카운터 2번이 입국심사를 받는데 10분이 걸린다면

28분이 주어질 경우 1번 카운터는 4명, 2번 카운터는 2명을 받을 수 있게 된다.

시간 절약을 위해 count > M을 하면 자동으로 반복문을 빠져나가 다시 이분탐색을 할 수 있게끔 하였다.

그래서 결국 6명을 받을 수 있는 최소한의 입국심사 시간을 찾아서 리턴하게 되는 것이다.

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

  1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
  2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력


첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

출력


첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

풀이


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int[] budget;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		budget = new int[N];
		int max = Integer.MIN_VALUE;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i=0; i<N; i++){
			budget[i] = Integer.parseInt(st.nextToken());
			if (budget[i] > max){
				max = budget[i];
			}
		}
		int budgetMax = Integer.parseInt(br.readLine());
		int start = 0;
		int end = max;
		while (start <= end){
			int mid = (start + end) / 2;
			int sum = 0;
			for (int i=0; i<N; i++){
				sum += Math.min(budget[i], mid);
			}
			if (sum <= budgetMax){
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		System.out.println(end);
	}
}

해설


가장 전형적인 이분탐색 문제이다.

예산의 상한을 이분탐색으로 찾아서, 각 지자체의 예산이 상한을 넘으면 상한값으로, 넘지 않으면 예산만큼을 sum에 추가해주고, 총 예산을 넘는다면 작은 데이터셋으로, 예산을 넘지 않는다면 큰 데이터셋으로 넘어가면 된다.

for (int i=0; i<N; i++){
    budget[i] = Integer.parseInt(st.nextToken());
    if (budget[i] > max){
        max = budget[i];
    }
}

이분탐색 문제지만, 정렬이 딱히 필요하진 않다.

다만 처음에 틀렸던 부분은 예산의 최소, 최대를 다 정해줬는데,

최소 상한은 0원으로 고정해놓고, 최대 상한만 max값을 넘기지 않도록 해주는 것이 중요하다.

최소 상한이 반드시 지자체의 최저예산보다 커야하는 법은 없기 때문이다.

 

이런 언어적인 부분을 코드로 해석하는것이 중요한데, 아직까지는 조금 부족한 것 같다.

int start = 0;
int end = max;
while (start <= end){
    int mid = (start + end) / 2;
    int sum = 0;
    for (int i=0; i<N; i++){
        sum += Math.min(budget[i], mid);
    }
    if (sum <= budgetMax){
        start = mid + 1;
    } else {
        end = mid - 1;
    }
}
System.out.println(end);

마지막으로 핵심적인 이분탐색을 시작하는 부분이다.

우리가 구해야 할 것이 Lower bound인지, Upper bound인지, 정확한 값인지를 아는 것이 매우 중요하다.

문제에서는 우리가 구해야 할 것을 다음과 같이 지정했다.

'정해진 총액 이하에서 가능한 한 최대의'

이 말은 결국 Upper bound를 구해야 하므로, 예산의 합이 총 합보다 작거나 같을때(sum <= budgetMax)는 계속 더 낮은 값을 찾기 위해 탐색해주어야 하고, 마지막에 예산의 최댓값인 end를 출력해주어야 한다.

 

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

[백준/11758] - CCW(JAVA)  (0) 2023.09.28
[백준/2143] - 두 배열의 합(JAVA)  (0) 2023.09.27
[백준/2573] - 빙산(JAVA)  (0) 2023.09.20
[백준/7569] - 토마토(JAVA)  (0) 2023.09.19
[백준/14502] - 연구소(JAVA)  (0) 2023.09.19

데이터베이스와 테이블의 차이는 무엇인가요?

우리가 가장 관심있어하는 정보는 테이블 안에 있고, 이 테이블 안의 여러 데이터를 제어하는 것이 우리가 가장 하고 싶어하는 일이다. 이 테이블을 묶어서 그룹핑하고, 이름을 붙인 것이 스키마이고, 이 스키마를 관리하기 위한 것이 데이터베이스이다. 여러개의 데이터베이스를 묶은 것을 클러스터라고도 하고 DBMS라고도 하는데, 이 DBMS를 데이터베이스라고 부르기도 한다.

MySQL에서 데이터를 조회할 때 사용하는 기본 SQL 명령어를 설명해주세요

  • SELECT
    • SELECT절은 여러 조건들을 처리한 후 남은 데이터에서 어떤 ROW를 출력할 지 선택하는 역할을 한다.
  • WHERE
    • WHERE절은 FROM절에서 읽어온 테이블에서 조건에 맞는 결과만 갖도록 데이터를 필터링한다.
  • FROM
    • 조회하려는 전체 테이블의 정보를 가져온다.
  • HAVING
    • HAVING절은 그룹핑 후 각 그룹에 사용되는 조건절로, HAVING절은 각 그룹에 조건을 걸기 때문에 퍼포먼스가 떨어지는 단점이 있다. 그래서 WHERE에 조건을 쓸 수 있다면 WHERE에 조건을 쓰는게 좋다.
  • JOIN
    • JOIN절은 2개나 그 이상의 테이블을 연결하고, 연결한 테이블로부터 필요한 열을 조회할 수 있도록 한다.
  • ORDER BY
    • ORDER BY절은 출력할 ROW를 어떤 순서에 맞게 보여줄 지 결정한다.

SQL 명령문의 실행 순서는?

  1. 먼저 FROM절에서 조회하려는 전체 테이블의 정보를 가져온다. JOIN이 있다면 다른 테이블과 조인하여 필요한 정보를 가져온다.
  2. WHERE절로 FROM절에서 조회한 테이블에서 필요한 데이터를 필터링한다.
  3. GROUP BY로 선택한 칼럼으로 그룹핑한다.
  4. HAVING으로 그룹핑한 각 그룹에서 조건을 걸어 다시 필터링한다.
  5. SELECT절로 여러 조건들을 처리한 후의 데이터를 가져온다.
  6. ORDER BY를 이용하여 SELECT문에서 가져온 ROW를 어떤 순서에 맞게 보여줄 지 정한다.
  7. LIMIT로 보여줄 ROW의 개수를 정한다.

'Primary Key'와 'Foreign Key'의 차이와 각각의 역할에 대해 설명해주세요.

PK

  • Primary Key는 데이터베이스 테이블의 각 레코드를 고유하게 식별하는 역할을 합니다.
  • 한 테이블에는 하나의 PK만 존재할 수 있으며, 이 PK는 해당 테이블의 모든 레코드에 대해 고유해야 합니다.
  • PK는 NULL이 될 수 없습니다.
  • PK로 지정된 컬럼은 클러스터링의 기준으로 사용되어, 데이터가 저장되는 방식을 결정합니다.

FK

  • Foreign Key는 다른 테이블의 PK를 참조하여 두 테이블 간의 관계를 설정하는 역할을 합니다.
  • FK로 지정된 필드 혹은 필드 셋의 값은 참조하는 PK에 있는 값 중 하나여야 합니다. 이 규칙은 참조 무결성의 제약 조건을 만족시키기 위한 것입니다.
  • FK는 NULL일 수도 있으며, 참조하는 PK에 없는 값을 가질수도 있습니다.

차이점

  • PK는 한 테이블 내에서 각각의 ROW / RECORD를 고유하게 식별하기 위해 사용되며, FK는 한 테이블과 다른 테이블의 관계를 구축하기 위해 사용됩니다.
  • PK는 같은 컬럼 안의 모든 레코드가 UNIQUE해야하는 반면 FK는 같은 컬럼 안의 레코드가 중복될수도 있고, NULL이나 참조하는 PK의 ROW에 해당하지 않는 값을 가질수도 있습니다.

MySQL에서 'JOIN'이란 무엇이며, 'INNER JOIN'과 'LEFT JOIN'의 차이점은 무엇인가요?

JOIN은 두 개 이상의 TABLE에서 ROW를 결합하는 데 사용되는 연산이며, 주로 테이블 간에 관계를 맺고 있을 때 사용됩니다. JOIN의 형태는 여러개지만, 가장 기본적인 형태는 INNER JOIN과 LEFT JOIN입니다.

INNER JOIN

  • INNER JOIN은 두 테이블 간의 교집합을 반환합니다.
  • 즉, 조인 조건에 일치하는 레코드만 결과로 반환합니다.
  • 예를 들어 A라는 테이블과 B라는 테이블이 있어서 INNER JOIN을 하면, A와 B 모두에 들어있는 데이터만 반환합니다.

LEFT JOIN(LEFT OUTER JOIN)

  • LEFT JOIN은 첫 번째 테이블의 모든 레코드와 일치하는 두 번째 테이블의 레코드를 반환합니다.
  • 오른쪽(두 번째) 테이블에서 일치하는 값이 없을 경우 NULL을 반환합니다.

정규화(Normalization)란 무엇이며, 왜 중요한가요?

NORMALIZATION은 테이블의 각 레코드의 중복을 최소화하고, 데이터 구조를 효율적으로 만드는 과정입니다. NORMALIZATION을 통해 데이터의 무결성(INTEGRITY)와 일관성(CONSISTENCY)을 유지할 수 있습니다.

정규화의 단계는 1NF, 2NF, 3NF 등이 있지만 너무 많은 정규화를 사용할 경우 성능하락이 동반될 수도 있으므로 성능과 무결성 사이에서 적절한 균형을 찾아야 합니다.

'DB > SQL' 카테고리의 다른 글

SQLD - Alter시 Oracle, MySQL, MSSQL의 차이  (0) 2023.02.13

+ Recent posts