BOBO's Note

www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 풀이 방법 임의의 칸에서 움직일 수 있는 모든 칸에 대해서 DFS 방식으로 확인해보면 된다. 이때, 시간 초과가 발생할 수 있으므로 DP를 이용한다. memo[i][j]에 board[i][j]에서 시작할 때 최대 움직일 수 있는 횟수를 저장하면, 똑같은 위치를 재방문할 때 곧바로 결과값을 알아낼 수 있다. 우선 dfs() 함수에서는 현재 위치 cur에서 시작할 때, 최대 움직일 수 있는 횟수를 반환한다고 하자...

https://programmers.co.kr/learn/courses/30/lessons/42629 코딩테스트 연습 - 라면공장 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니�� programmers.co.kr 풀이 방법 하루에 밀가루를 1톤씩 사용하므로, 밀가루 재고가 amount일 때 현재 날짜가 amount 보다 크거나 같으면 밀가루 재고가 부족하다. 따라서 이 경우에는 그 전에 밀가루를 미리 구매해야 한다. 이때, 밀가루 구매 횟수를 최소화하기 위해서는 한번에 최대한 많이 구매할 수 있는 날에 구매해야 한다. 따라서 우선순위 큐를 두어서 한번에 구매할 수 있는..

https://programmers.co.kr/learn/courses/30/lessons/49189?language=cpp 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 방법 1번 노드와 가장 멀리 떨어진 노드들의 개수를 구하는 문제이다. BFS를 이용해 거리 별로 방문하다가 가장 마지막에 방문한 노드 개수를 반환하면 된다. 우선 노드의 개수가 최대 20,000개이고, 간선의 개수는 최대 50,000개이므로 간선 정보를 인접 행렬보다는 인접 리스트에 저장하는 게 더 효율적이다. 왜냐하면 인접 행렬은 크기가 20,000*20,000인 반면, 인접 리스트는 50,000이기 ..

https://leetcode.com/problems/maximum-subarray/ Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 방법 주어진 배열에서 연속된 원소들의 합 중 최대를 구하는 문제이다. Brute force한 방법은, 모든 subarray에 대해 합을 구하고 그 중 최대값을 알아내는 방법인데, 이 방법은 배열의 크기가 N일 때, O(N^2)의 시간복잡도를 가진다. DP를 사용하거나 Divide-and-Con..

https://programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 방법 수를 제거해 최대한 큰 숫자를 얻으려면, digit이 큰 수를 최대한 앞쪽에 위치하도록 삭제해야 한다. 따라서 먼저 가장 큰 digit을 찾고, 이 digit을 삭제하지 않을 것을 mark[] 배열에 체크하고 추가한 digit 개수 added를 1 증가시킨다. char max_digit = number[start]; int max_idx = start; for(int i=start+1; i max_digit){ max_digit = number[i]; max_idx = i; if(max_digit == '9') break; } ..

https://leetcode.com/problems/validate-binary-search-tree/ Validate Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 방법 Binary Search Tree는 모든 노드가 다음을 만족하는 이진트리이다. 모든 왼쪽 서브트리의 자식 노드 값 val >= max->val) return false; if(min != nullptr && root->val val) return f..

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 풀이 방법 N을 1개 사용해서 만들 수 있는 표현식은 다음과 같다. 표현식을 계산한 값들의 집합을 SET1라고 하자. N N을 2개 사용해서 만들 수 있는 표현식은 다음과 같다. 표현식을 계산한 값들의 집합을 SET2이라고 하자. NN U SET1 op SET1와 같다. NN N + N N - N N * N N / N N을 3개 사용해서 만들 수 있는 표현식은 다음과 같다. SET3 = NNN U (SET1 op SET2) U (SET2 op SET1) 이다. NNN (N + N) +,-,*,/ N (N - N) +,-,*,/ N (N * ..

https://leetcode.com/problems/sliding-window-median/ Sliding Window Median - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이 방법 슬라이딩 윈도우에 속한 값들 중 중간값을 찾는 문제이다. 중간값은 정렬했을 때, 가장 가운데에 있는 값이다. 중간값를 쉽게 찾을 수 있도록 정렬되고, 중복된 원소를 저장할 수 있는 multiset을 사용하자. multiset에 슬라이딩 윈도우에 속하는 값들을 모두 넣고,..