MZ 개발자

이 문제는 N개의 카드중에서 M개의 카드 숫자가 몇개 있는지 찾는 문제이다. 단순한게 브루트포스 방법 O(n^2)으로 문제를 해결하려고 시도한다면 N = 500000, M = 500000 이므로 시간초과가 발생한다. 따라서 특정 숫자가 어디에 있는지 빠르게 탐색하기 위해 이진탐색으로 접근해야 한다. 이진탐색을 하기 위해서는 우선 상근이의 숫자 카드 N이 오름 차순으로 정렬이 되어있어야 한다. 이때 핵심은 중복된 숫자 카드를 어떻게 표현할 것인가 이다. 오름 차순 정렬 후 앞쪽부터 순회하면서 중복된 숫자를 pair 로 변환 시켜준다. 예를들어 N이 -10, -10, 1, 3, 5, 10, 10, 10 일경우 {-10,2}, {1,1}, {3,1}, {5,1}, {10,3} 과 같은 형태로 변환을 시켜준다...

이 문제는 기본적으로 A - B까지 갈수 있는 경로 중 최단 시간을 구하는 다익스트라 응용 문제이다. 기존에 자주 출제되는 다익스트라는 무방향 그래프로 A - B 까지의 최단 경로와 B - A 까지의 최단 경로는 같다. 하지만 이 문제는 방향 그래프로 A - B 까지의 최단 경로와 B - A 까지의 최단 경로가 다르다. 따라서 문제에서 학생들이 오고 가는데 가장 오래 걸리는 학생의 소요시간을 구하기 위해서는 다익스트라를 두번 돌려주어야 한다. #include #include #include #include #include #define INF 987654321 using namespace std; int n, m, x; vector adj[1001]; int dajik(int start, int end)..

이진트리 순회에 대해 다시 한번 복습 할 수 있는 문제이다. 기본적으로 이진트리 순회 방법은 전위(pre), 중위(in), 후위(post)로 3가지 방법이 존재한다. 이 문제는 단순 이진트리 순회가 아닌 중위, 후위 순서가 주어지고 이를 이용하여 트리를 재구성 하는 문제이다. 이진트리 순회 방법은 아래를 참고하자. 더보기 전위순회 루트 - 왼쪽 노드 - 오른쪽 노드 중위순회 왼쪽 노드 - 루트 - 오른쪽 노드 후위순회 왼쪽 노드 - 오른쪽 노드 - 루트 문제에서 입력은 중위 순서와 후휘 순서가 주어진다. 예를들어 입력이 다음과 같다고 가정해보자. 11 8 4 2 9 5 1 10 6 3 11 7 (중위) 8 4 9 5 2 10 6 11 7 3 1 (후위) 전위 순회를 하기위해서 각 레벨에서 루트를 찾는것이..

이 문제는 이전에 풀었던 문제와 입력 방식만 다른 완전히 같은 문제이다. https://devconf.tistory.com/40 BOJ 1967 트리의 지름 문제를 보고 몇시간 정도 풀이를 생각해보다가 도저히 떠오르지 않아 다른 사람 풀이를 참고하여 아이디어를 얻었다. 문제에 간선의 가중치는 100보다 크지 않는 양의 정수라고 하여 특정 노드 devconf.tistory.com 기본적인 방식은 특정 아무 위치에서 DFS를 통해 길이가 최대가 되는 시작점을 구하고, 그 시작점에서 다시한번 DFS를 돌리면 된다. #include #include #include #include using namespace std; int v; vector adj[100001]; bool visited[100001]; int ..

처음 생각한 방법은 노선 길이가 가장 긴 구간부터 구간에 겹치는지 안겹치는지 확인하려고 하였다. 여기서 발생한 문제는 정류소의 갯수가 3 ~ 1,000,000,000개 이기 때문에 모든 정류소를 배열로 정의할 수 없다. 따라서 어떤 노선이 다른 노선에 포함되는지 안되는지 한번에 알수 있는 방법이 필요하다. 만약 모든 노선 a,b에서 ab 라면 조금 복잡하다. 예를들어 [0~3]와 [9~4]는 위의 방법을 적용할 수 없다. 위의 방법을 적용한다면 겹치는 노선임에도 불구하고 겹치지 않는 유효한 노선이 되버린다. 이를 해결하기 위해 노선을 직선상으로 바꿔보자. a>b 일때 ab 인 모든 노선을 ab 일때 직선상으로 변환하면서 노선을 두개를 추가하였기 때문에 결과에는 중복된 값이 저장된다. 따라서 중복된 값을 ..

문제 풀이의 핵심은 한블럭 이동을 w 대각선 이동을 s라 할때 (0,0) 에서 (1,1)로 갈수 있는 방법중 최소시간을 우리는 구할 수 있다. 즉 s 와 2*w 중 걸리는 시간이 작은 것을 고르면 된다. 단순하게 생각하면 만약 대각선으로 움직이는 것이 직선으로 이동하는것보다 작을 경우 즉 s> x >> y >> w >> s; if(2 * w

문제의 힌트를 보면 잘 이해가 되지 않는다. 상식적으로 웅덩이를 덮을때 시작점에 딱 맞춰서 널빤지를 붙이면 최적이다. 힌트를 보면 웅덩이는 1에서 시작하는데 널빤지를 0에서 부터 붙이기 시작하여 사실상 힌트 오류라고 할수 있다. 실제 맞는 예시는 다음과 같다. .111222.333444555 .MMMMM..MMMM.MMMM 풀이 방법은 각 웅덩이 위치를 백터 v에 넣어 정렬한 후 각 웅덩이 마다 깔수 있는 널빤지를 구해주면 된다. 핵심은 널빤지가 다른 웅덩이를 일부 덮는다면 거기서부터 계속 붙여나가고, 그렇지 않고 널빤지의 끝이 일반 땅이라면 그다음 웅덩이부터 다시 붙여나가면 된다. #include #include #include using namespace std; int main() { ios_bas..

문제에서 어떤 두 정수 min과 max 사이에 수가 1보다 큰 제곱수로 나누어 떨어지지 않을때 제곱 ㄴㄴ 수 라고 정의를 하였다. 어떤 수가 제곱수로 나누어 떨어지지 않은것을 구하기 위해 우리는 에라토스테네스 방법을 응용할 수 있다. 처음 떠올린 방법은 부르트포스로 생각하였는데 제곱수가 될수 있는 n이 1000000, max-min이 1000000이므로 1000000*1000000 즉 1조가되어 시간초과가 발생한다. 기본적인 에라토스테네스는 소수를 구하기 위해 2,3,5,7의 배수를 모두 지우고 지워지지 않고 남은 수를 우리는 소수임을 알수 있다. 이를 응용하여 i*i (i>1) 가 max 보다 작을때 까지 i*i의 배수를 모두 지워주면 된다. 이때 시작지점은 i*i 가 min 보다는 커야하므로 min/..

이 문제는 0을 뒤집거나 1을 뒤집어서 최소한의 뒤집기로 같은 숫자를 만드는 문제이다. 따라서 0과 1이 바뀌는 구간을 기준으로 0인 구간의 갯수과 1인 구간의 갯수중 최소인 숫자를 뒤집으면 답이된다. 예를들어 0001100의 경우 0의 구간은 앞쪽 000, 뒷쪽 00으로 총 2번 뒤집어야한다. 하지만 1의 구간의 경우 가운데 11으로 1번만 뒤집으면 된다. 따라서 최소한으로 뒤집어야하는 횟수는 1이 된다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; int oneCnt = 0, zeroCnt = 0; for(int i..

S는 서로 다른 N개의 자연수의 합이기 때문에 N은 1부터 증가하면서 누적 합이 S를 초과하기 전의 N을 구하면 되는 문제이다. 하지만 S의 범위는 int를 초과하는 범위이기때문에 long long으로 바꿔주어야한다. #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); long long s; cin >> s; long long sum = 0; long long answer = 0; for(long long i = 1; ; i++) { if(sum + i