MZ 개발자

이 문제는 포켓몬 도감에 수록되어 있는 N개의 포켓못 정보를 가지고 M개의 질문이 들어왔을때 적절하게 결과를 반환해야 한다. 우선 질문은 두가지로 다음과 같다. 1. 포켓몬 이름을 주어질 때 해당 포켓몬이 도감의 몇번째에 존재하는지 2. 숫자가 주어질때 해당 숫자의 포켓몬 이름은 무엇인지 도감에 수록된 포켓몬의 숫자 N는 100,000 이고 질문 M은 100,000 이므로 부르트포스 방법으로는 시간내에 문제를 해결할 수 없다. 따라서 해싱을 통해 O(1) 만에 탐색해야 한다. 숫자가 주어졌을 때 포켓몬 이름을 구하는 방법은 간단하게 배열의 인덱스를 활용하여 해결 가능하다. 하지만 포켓몬 이름이 주어졌을 경우 조금 생각을 해야한다. 만약 이름을 아스키 코드로 변환하여 그 값을 해시값으로 사용한다면 해시충돌..

이 문제는 땅의 높이를 0~256중 하나로 하여 땅을 고르게 만들때 걸리는 시간과 땅의 높이를 출력하는 프로그램이다. 처음 생각한 방법은 같은 높이의 블록 갯수를 파악하여 {높이,갯수} 형태로 배열에 저장하고 이들중 하나의 높이로 통일 시킬 때 걸리는 시간과 높이를 구하여고 하였다. 하지만 위와 같은 방법의 문제점은 문제에서 주어진 높이로만 땅을 고르게 할때 다음과 같은 반례가 나올 수 있다. 1 3 1 1 4 1 다음과 같은 경우 정답은 6 2 가 되지만 처음 생각한 방법으로 구현 하였을 경우 배열에 {1,2},{4,1}이 들어가고 결과는 6 1 이 나오게 된다. 이는 문제에서 시간이 같다면 높이가 높은것을 구하라고 하는것을 빼먹은 것이다. 이를 해결하기 위해 모든 높이에 대해 걸리는 시간을 모두 구하..

이 문제는 상근이가 가지고 있는 숫자 카드 N개 중 주어진 M(정수)를 몇개씩 가지고 있는지 구한는 문제이다. N은 -10,000,000 ~ 100,000,000 사이의 숫자로 중복된 값이 들어올 수 있다. 이를 해결하기 위해 N개의 카드 중 특정 숫자가 몇개 존재하는지 체크를 해야한다. 가장 간단한 방법은 카드에 적혀 있는 숫자를 배열의 인덱스로 하여 카운팅 해주는게 편리한데 그렇게 할 경우 인덱스 범위가 0~ 200,000,000이 되어 해당 크기의 배열을 정의할 수 없다. 따라서 다른 방법을 생각해야한다. 생각해낸 방법은 백터를 이용하여 N을 정렬한 후 순차 탐색하면서 이전의 값이랑 중복되는지 안되는지 확인하여 새로운 해싱 백터를 만드는 것이다. 자세한 방법은 아래 코드에서 확인할 수 있다. 위의 ..

이 문제는 STL의 Queue 사용법에 대해 알고있으면 쉽게 해결할 수 있는 문제이다. 풀이 코드는 다음과 같다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; queue q; for(int i = 0; i > method; if(method == "push") { int num; cin >> num; q.push(num); } else if(method == "size") { cout

이항 계수는 n개의 서로 다른 물건 중에서 순서 없이 k개를 뽑는 조합의 가짓수 이고 이는 다음과 같이 정의 된다. 이 식을 프로그래밍 하면 된다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; int a = 1, b = 1; for(int i = 0; i 0; i--) { b *= i; } cout

기본적으로 우선순위 큐는 삽입,삭제에 대해 O(logN)의 시간복잡도를 가진다. 또한 트리구조를 취하는 MaxHeap( 또는 MinHeap)으로 구현된다. 문제에서 Q의 종류중 D 1 은 가장 큰 값 삭제, D -1은 가장 작은 값 삭제를 수행하야 하지만 우선순위 큐 한개로는 불가능 하다. 따라서 MaxHeap, MinHeap으로 구현된 우선순위 큐 2개를 사용해야 한다. 여기 까지가 처음 생각한 방법이다. 하지만 문제는 두 큐가 동기화가 되지 않는다는 점이다. 한참을 고민하던도중 multiset이라는 자료구조를 이용하면 해결 가능하다는 것을 발견하였다. multiset이란 기본적인 set은 중복을 포함하지 않고 정렬되어있지만 multiset은 중복을 허용한 정렬된 자료구조이다. 또한 특정 값을 eras..

문제를 분석해보면 새로 생성된 좌표 X`은 Xi > Xj를 만족하는 좌표의 갯수를 의미하는 것을 알 수 있다. 이는 i번째 좌표보다 작은 좌표의 갯수가 압축된 좌표임을 나타내는데, 핵심은 어떻게 특정 좌표보다 작은 좌표의 갯수를 구하는것이다. 가장 단순하게 이중 for문을 사용하며 부르트포스 방식으로 탐색한다면 O(n^2) 으로 시간초과가 발생한다. 따라서 다른 방법을 떠올려야한다. 입력을 보았을때 가장 작은 숫자는 항상 0으로 압축이된다. 이를 바탕으로 좌표를 오름차순으로 정렬하고 i=1, i번째 좌표가 i-1번째 좌표보다 클 경우 이전 좌표값에서 1을 증가시켜주는 방법으로 갯수를 파악할 수 있다. 이 방법을 사용하면 O(n) 만에 특정 값보다 작은 값의 갯수를 구할 수 있다. #include #inc..

이 문제는 얼마전 포스팅했던 BOJ 1654 랜선 자르기 문제와 100%일치하는 문제이다. 핵심은 적절한 나무 길이를 구하기 위해 이진 탐색을 이용해야하는 것이다. https://devconf.tistory.com/65 BOJ 1654 랜선 자르기 이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개( devconf.tistory.com #include #include #include #include using namespace std; typedef long long ll; int n, m; vector len; ll result; bool cmp(ll a, ll ..

이 문제의 접근 방법은 현재 가진 연료로 갈수 있는 주유소 중 멈췄을때 가장 많은 연료를 획득할 수 있는 주유소에서 멈추면 된다. 주유소의 위치가 순서대로 들어오지 않기 때문에 주유소 위치를 정렬 시켜주어야 한다. 이후 현재 가진 연료로 멈출 수 있는 모든 주유소에서 얻을 수 있는 연료의 양을 우선순위 큐에 넣고 빼면서 전체 획득한 연료 양을 누적시킨다. #include #include #include #include using namespace std; priority_queue pq; vector v; int n; int l, p; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 0; i < n; i..

이 문제는 K개의 랜선이 주어지고 이를 이용하여 N 개(이상)의 랜선을 만든는데 랜선의 길이를 가장 길게 만들때 그 랜선의 길이를 구하는 문제이다. 시작 아이디어는 주어진 K개의 랜선으로 N개(이상)의 랜선을 만들수 있는지 없는지에 초점을 두었다. 여기서 핵심은 적절한 랜선의 길이를 어떻게 잡는가 이다. 여기서 선택지는 두가지로 다음과 같다. 1. 가장 큰 길이를 기준으로 적절한 랜선 길이를 찾아내기 2. 가장 작은 길이를 기준으로 적절한 랜선 길이를 찾아내기 가장 작은 길이로 적절한 랜선 길이를 찾아낼 경우 최대 랜선의 길이를 구할 수 없다. 예를들어 입력이 2 10 100 4 일때 최대 랜선의 길이는 10 이 되지만 가장 작은 길이를 기준으로 하였을 경우 결과는 4가 된다. 가장 큰 길이의 랜선을 기..