MZ 개발자

우선 이 문제는 그래프 문제로 N 개의 정점이 주어지고 M개의 연결이 주어질때 '모든 정점'에서 '모든 정점'으로의 최단경로를 구하는 문제이다. 플로이드 와샬 알고리즘을 알고 있었다면 간단하게 해결할 수 있는 문제이다. 하지만 플로이드 와샬 알고리즘을 몰랐기 때문에 인접리스트를 이용하여 DFS로 문제를 해결하였다. 각 정점에서 다른 정점까지 최단 경로를 구해야 하기 때문에 생각해낸 방법은 리스트에 찾고자 하는 정점이 있을경우 1번에 탐색 가능, 없을경우 리스트에 있는 정점으로 이동하여 다시 탐색하는 방법을 사용하였다. 어찌어찌 이상한 방법으로 문제를 해결하였지만 알고리즘 분류를 확인하고서 플로이드 와샬이라는 것을 알게 되었다. 우선 내가 푼 방법을 공유하고 다시 플로이드 와샬로 문제를 풀어보도록 하겠다...

처음 문제를 봤을때 무식하게 이동하려는 채널의 자릿수를 확인하면서 누를 수있는 버튼중 차이가 가장 작은것을 선택할 생각을 하였다. 하지만 다음 입력 예제를 가지고 생각해 보았을때 처음 생각한 방법으로 답을 구할 수 없는 것을 할게 되었다. 500000 6 0 2 3 6 7 8 위의 입력으로 버튼을 눌러서 500000과 최대한 가깝게 이동할 수 있는 곳은 499999 이다. 하지만 처음 생각한 방법으로 각자리의 차가 가장 작은것을 선택하게 된다면 511111이 된다. 이럴 경우 정답은 7인데 오답 11117이 나오게 된다. 이를 해결 하기 위해 각 자리마다 경우의 수가 붙게 되는데 이를 찾는 것 뿐만 아니라 구현하는 것도 왠지 이 방법으로 문제를 풀었다고 해도 어디선가 반례가 나올것 같았다. 여기서 생각한..

이 문제는 N*N 크기의 종이를 모든 부분이 같은 색으로 칠해져 있을때 까지 N/2*N/2로 계속 나누면서 각각 1을 파란색, 0을 하얀색으로 나타내고 이때 파란색 색종이와 하얀색 색종이의 갯수를 각각 출력하는 문제이다. 풀이 방법은 재귀를 이용한 방법이다. 전체 종이 길이 N에 대해서 재귀를 반복할 때마다 색종이의 한변 길이를 N/2 씩 줄여나가면서 1사분면,2사분면,3사분면,4사분면으로 분할하여 탐색하면 된다. 이렇게 분할 하였을때 가장 중요한 부분은 범위이다. (1,1)을 기준으로 모든 사분면의 범위를 구하는 방법은 다음과 같다. 1사분면 : (1,1) / 2사분면 : (1,1+N/2) / 3사분면 : (1+N/2,1) / 4사분면 : (1+N/2,1+N/2) 이 되고 이를 일반화 하면 1사분면 :..

이 문제는 포켓몬 도감에 수록되어 있는 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..