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에서 시작할 때, 최대 움직일 수 있는 횟수를 반환한다고 하자...

세그먼트 트리는 어떠한 배열이 주어졌을 때, 각 구간의 대표값(예. 합, 최대값 등)을 빠르게 구할 수 있는 자료구조이다. 배열의 크기가 N일 때, 임의의 구간에 대한 쿼리를 O(logN)에 수행할 수 있다. 인덱스 트리는 팬윅 트리(Fenwick Tree)라고도 하며, 세그먼트 트리처럼 각 구간의 대표값을 빠르게 구할 수 있다. 세그먼트 트리보다 구현하기 더 간단하고 속도가 빠르다는 장점이 있다. 이 포스터에서는 구간합을 세그먼트 트리를 이용해 빠르게 구하는 방법에 대해 알아보자. 구간합 구하기 배열 arr[0], arr[1], ..., arr[N-1]이 있다고 할 때, 임의의 구간 [l, r]에 대하여 구간합 arr[l] + arr[l+1] + ... + arr[r-1] + arr[r]을 구해라. 위..

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..

DP 문제를 푸는 방법 다음과 같은 순서로 알고리즘을 개선해나가자. recursive 관계를 찾아낸다. recursive하게 알고리즘을 구현한다. (top-down) recursive한 알고리즘에 memo[] 배열을 사용하여 반복을 줄인다. (top-down) iterative한 알고리즘으로 바꿔본다. (bottom-up) memo[] 배열 대신에 N개의 변수로 줄여본다. (bottom-up)

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; } ..

Binary Tree 이진트리는 각 노드가 최대 2개의 자식을 갖는 트리이다. Binary Search Tree 이진 탐색 트리는 모든 노드 n에 대해 left subtree