데옴's 기록장

발상자체는 쉽다고 생각이 들 수 있지만 막상 보면 전혀 쉽지 않은 끔찍한 문제였다. 문제를 읽고 처음 든 생각은 "어? 되게 쉽네?? 이게 왜 다이아지?" 하는 생각이었지만.. 다이아는 다이아다. 이 문제를 풀고 얻은 교훈은 다이아는 그 이유가 다 있기 마련임을 알게 되었다. 먼저 로봇의 이동방식을 보자. 1. 로봇은 앞으로 이동하거나 뒤로 이동한다. 2. 로봇은 벽 위에 놓여있는 센서를 하나 또는 여러 개를 들고 이동할 수 있다. 이 두 가지 조건을 가지고 로봇의 전체적인 이동 과정을 그려보면 아래와 같음을 알 수 있다. 그렇다. 로봇을 최소한의 이동거리로 모든 센서를 배치하려면 어쩔 수 없이 위 그림과 같이 이동해야 한다. 1. 왼쪽구간에 센서가 식별하지 못하는 구역이 있으면 로봇은 센서를 가지러 이..

모든 i번째 수에 대하여 나머지 R이 되도록 하는 숫자를 구하는 문제이다. i번째 수를 M으로 나누었을때를 식으로 표현하면 다음과 같이 나타낼 수 있다. $N_i=MQ_i+R$ 첫번째 수와 두번째 수를 M으로 나눈 항등식으로 표현하면 아래와 같다. $N_1=MQ_1+R$ $N_2=MQ_2+R$ 두 수를 빼면 $N_1-N_2=(Q_1-Q_2)M$ 와 같이 나타낼 수 있다. 인접한 수들에 대해 전부 해보면 $N_1-N_2=(Q_1-Q_2)M$ $N_2-N_3=(Q_2-Q_3)M$ $N_3-N_4=(Q_3-Q_4)M$ $N_4-N_5=(Q_4-Q_5)M$ ... $N_{n-1}-N_n=(Q_{n-1}-Q_n)M$ 위 식을 토대로 인접한 두 수의 차의 GCD값이 구하고자 하는 M의 값임을 알 수 있다. 주어진 ..

숫자를 분해한 후 얻을 수 있는 숫자들의 곱을 최대화하는 문제이다. 당연하게도 많은 수를 곱하는것이 이득임은 쉽게 알 수 있다. 그럼 최대한 많은 수를 곱을 최대화하는 것이 관건이 된다. 1,2,3은 분해를 하지 않아야 최대이다. 4는 2+2로 분해할 수 있고 이는 최대이다. 5는 2+3으로 분해할 수 있다. 6은 3+3, 7은 3+2+2, 8은 3+3+2로 분해했을 때가 최대이다. 이제 알 수 있는 사실은 3을 가능한 많이 포함하는 것이 수를 분해했을 때 최대가 될 수 있는 것이다. 하지만 10과 같은 경우는 3+3+3+1로 나눠진다면 1로 곱하기 때문에 최대로 만들 수 없다. 3을 많이 넣으면서, 1이 포함되지 않도록 조절하면 답을 구할 수 있다.

k개의 소수들의 곱을 순서대로 나열할 때, n번째로 오는 숫자를 구하는 문제이다. 가장 단순하게 k개의 소수들로 만들 수 있는 숫자들을 만든다는 전략을 사용해 보자. i번째로 오는 수에 k개의 소수를 각각 곱하여 만들 수 있는 수를 우선순위큐에 넣어준다. 중복되는 경우가 있을 수 있기 때문에 하나의 경우만 있을 수 있도록 처리해 준다. 문제의 메모리가 적으므로 메모리 초과에 유의하자. 더보기 #define _CRT_SECURE_NO_WARNING #include #include #include #include using namespace std; using namespace __gnu_cxx; // utils #define fastio ios::sync_with_stdio(false);cin.tie(0)..

체감으로는 골드 4?정도로 느껴지는 우선순위큐를 잘 활용하는 법을 안다면 쉽게 구현할 수 있는 문제라고 생각한다. 문제를 꼼꼼히 읽으면 쉽게 접근법을 찾아낼 수 있다. 우선 요구사항을 정리하면 다음과 같다. 1. 계산대에 줄을 선 순서대로 고객이 들어온다. 2. 빨리 계산이 끝나는 계산대에 고객을 안내하고, 기다려야 하는 시간이 같다면 계산대 번호가 작은 순서대로 고객을 안내한다. 3. 계산이 끝나는 대로 고객이 나간다. 계산을 마친 고객이 여러 명이라면 계산대 번호가 큰 순서대로 나간다. 기본적으로 계산대에 사람이 있어야 하므로 처음 $min(k, n)$명에게 순서대로 계산대에 배정한다. 이제 계산이 가장 빨리 끝나는 계산대의 시간을 $t$라고 해보자, 다음 손님이 왔을 때 그 계산대에서 계산을 끝마치..

문제 제목이 참... 좀 그렇다 ㅋㅋ 이 문제는 BOJ 1489와 같다. 솔직히 이게 왜 플레지.. 생각이 들 정도로 단순한 그리디로 해결된다는 사실이다. 구해야 하는 것은 이안이와 예환이가 점수내기를 하고 이안이가 얻을 수 있는 최대 이익이다. 비교하기 쉽게 일단 정렬을 해보자. 이안이가 가장 최적의 효율로 내기에서 이기기 위해선 점수차가 최소가 되면서 이기거나 비기는 것이 중요하다. 여기까지 느낌을 잡았다면 그 후는 구현만 하면 된다. n제한은 10000으로 $O(n^2)$ 알고리즘을 사용할 수 있다. 이안이가 최소한의 점수차로 이길 수 있는 모든 과목 -> 무승부가 가능한 모든 과목 -> 지는 모든 과목순으로 점수를 계산해 주면 된다. 더보기 struct team { int point; bool u..

면접을 보고 난 후 2일이 지났다. 드디어 11/13일, 5시에 합격 발표가 나온다니 그 전날부터 면접 보는 것과 같은 긴장감을 가질 수 있었다. 11/13일로 만들기 위해 잠을 청했고 침대에 누워 눈을 감으니 불합격의 메시지가 담긴 입학관리 시스템의 모습이 보였다.. 꿈을 꾸는데도 자꾸만 불합격의 예감이 들었다. 면접 때 제대로 답하지 못한 찝찝함 때문이었을까? 점점 불안한 마음에 잠에 제대로 들지 못한 채 날이 밝았다. 학교에 등교하고 디미고에 지원한 친구와 함께 손을 붙잡고 붙기를 간절히 바라였다. 발표 전까지 우리는 1분마다 디미고 합격 기원을 외치기로 하였고 실행했다(?) 점점 면접 때 어떤 말실수를 했고 과연 면접관이 원했던 말이 무엇이었는지 의문이 들기 시작했다. 이런 생각을 가지게 되면서 ..

혼자 사다리타기에 대한 다양한 방법으로 연구하며 시간을 보내다 만난 문제이다. 오랜 시간 연구했던 탓인지 상대적으로 쉽게 해결할 수 있었다. 사다리들이 배치되어 있고 꼭 필요한 사다리들만 출력하는 문제이다. 문제를 해결하기 앞서 사다리타기의 성질을 알아보자. 세로줄 사이에 사다리를 하나 놓으면 a,b는 서로 swap이 된다. 그렇다면 여기서 할 수 있는 발상은 매우 단순하다. 한번 이미 사다리를 타고 이동했을때의 모든 도착지점을 안다고 생각해보자. i번째 출발점에서 도착점으로 가기 위해서는 그 거리만큼 사다리가 필요하다. 여기서 중복되는 사다리들이 존재할 수 있는데 여기서는 교차점이라고 말하겠다. n개의 출발점에서 도착지점으로 이동하는 모습을 표현하면 결국 사다리는 중복됨으로 교차점이 발생하는 구간에서 ..

2023/11/11, 빼빼로 데이에 디미고 면접을 보러 갔다. 평소 열심히 학교 생활을 하며 성적도 잘 나왔고 자소서도 열심히 작성해서 1차는 무난하게 붙었다. 문제는 2차 면접이었고 그게 빼빼로 데이인 오늘이었다. 가기 전까지는 ps를 하며 매우 즐거운 시간을 보냈지만 막상 도착하고 보니 굉장히 떨렸다..(어쩌면 당연한 것일지도) 대기실에 입실하고 많은 디미고 형님누님들이 디미고에 대한 환상(?)을 깨주기도 하고 재밌는 썰도 많이 풀어주셨다. 디미고 기숙사 생활을 하며 제일 재밌는 게 샤워시간이라나 뭐라나... 아무튼 나는 대기번호 6번이었고 같이 디미고에 지원한 친구는 3번으로 먼저 면접을 보러 갔다. 친구가 면접을 보러 나가고 인싸의 향기가 나는 디미고 선배 중 한 명은 노래를 부르는 장기자랑을 했..

유명한 그리디의 스케줄링 문제이다. 발상이 떠오르지 않는다면 어려울 수 있는 그리디 문제이다. 그러나 한번 알아두면 평생 쓴다! 어떤 방법으로 강의들을 배정해야 최소한으로 필요한 강의실을 개수를 구할 수 있을까? 순서대로 계획을 짜보자 1. 빨리 시작하는 순으로 배정한다. 시작이 빠른 강의가 가장 늦게 끝나는 경우가 있음으로 사용하기 어렵다. 2. 강의 시간이 짧은 순서대로 배정한다. 강의 시간이 짧은 강의가 제일 나중에 나오게 되면 비효율적이다. 3. 적게 겹치는 강의부터 배정한다. 이 역시 쉽게 반례를 찾을 수 있다. 4. 빨리 끝나는 순으로 배정한다. 뭔 짓을 해도 반례를 찾을 수 없다. 전략이 나왔다. 빨리 끝나는 순으로 강의를 배정시켜 보자. 이는 우선순위큐를 이용해 배정할 수 있다. 빠른 순으..