프로그래밍나무

개념 오름차순으로 정렬된 리스트에서 특정한 값을 찾는 알고리즘입니다 의사코드 BinarySearch(A[0..N-1], value, low, high) { if (high value) return BinarySearch(A, value, low, mid-1) else if (A[mid] < value) return BinarySearch(A, value, mid+1, high) else return mid // found } BinarySearch(정렬된 배열, 찾을 값, 배열의 첫 인덱스, 배열의 마지막 인덱스) 를 통해 이진 탐색을 수행할 수 있습니다 활용 그러면 해당 알고리즘을 코테 문제에 어떻게 적용할 수 있는지 생각해 보겠습니다. https://www.acmicpc.net/problem/1300..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 접근방법 해당 문제에 이분탐색을 적용하여 해결하겠습니다. 이동하는 물품들의 중량을 정해놓고 가능한지 검사해나가면 중량의 최댓값을 구할 수 있습니다. 순서 각 다리의 중량 제한의 최댓값을 구한다. low = 0, high = 중량의 최댓값으로 설정 low와 high을 가지고 이분탐색 mid = (high + low) / 2 + 1 mid 중량으로 다리..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 접근 방법 해당 문제는 그리디 알고리즘을 이용해 풀 수 있습니다. 보석의 최대 가격을 구하기 위해서는 각각의 가방에 넣을 수 있는 보석 중 최대 가격을 가진 보석을 넣어야 합니다. 결국, 각 가방에 담을 수 있는 최대 무게보다 작은 보석 중에서 제일 큰 가격을 가지고 있는 보석을 선택하면 됩니다. 하지만 보석을 넣을 때는 최대 무게가 작..

프로젝트에서 사용하기 위해 d3를 사용하였는데, 빠른 적용을 위해서 d3의 examples를 이용하였습니다. 그중 제가 사용한 것은 zoomable circle chart입니다. vuex의 store에 데이터를 저장해놓았다가 버튼을 클릭 시 해당 차트가 보이도록 설정하였습니다. example 가져오기 chart = { const root = pack(data); let focus = root; let view; const svg = d3.create("svg") .attr("viewBox", `-${width / 2} -${height / 2} ${width} ${height}`) .style("display", "block") .style("margin", "0 -14px") .style("backgr..

개발하던 도중 pull을 받으려는데 conflict가 발생했습니다. 이유는 저와 같은 파일을 수정한 내용이 remote에 있어서였습니다. 해당 파일의 내용을 제 local 내용으로 덮어쓰기 하는 것으로 결정하고 수정을 진행하였습니다. 수정은 다음과 같은 순서로 진행하였습니다. local의 내용들을 stash에 저장 pull 받아오기 stash 파일로 덮어써서 commit local의 내용들을 stash에 저장 이렇게 하면 현재 local에서 pull 받은 이후(또는 commit 한 이후)까지 작업했던 내용들은 stash에 저장되고 local의 상태가 그전으로 돌아가게 됩니다. pull 받아오기 이제 프로젝트에서 pull을 받게 되면 현재 local에는 수정한 기록이 없기 때문에 remote의 내용이 co..

배낭 문제는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법입니다. 이 배낭 문제는 두 가지로 나누어집니다. 짐을 쪼갤 수 있는 경우인 분할 가능 배낭(Fractional Knapsack) 짐을 쪼갤 수 없는 경우인 0-1 배낭(0-1 Knapsack) 분할 가능 배낭 이 문제는 그리디 알고리즘을 적용하면 다항 시간 안에 풀 수 있습니다. 짐을 쪼갤 수 있는 경우에는 무게당 가치가 제일 높은 물건이 먼저 들어가야 하므로 각 물건의 가치/무게를 구한 다음 가장 높은 물건부터 무게의 최댓값까지 넣습니다. 0-1 배낭 이 문제는 백준 12865번의 예제를 참고하여 설명하겠습니다. 물건을 담았을 때의 가치를 계산할..

LIS 개념 증가하는 부분 수열에 대해서 먼저 설명하자면 한 배열에서 어떤 원소들을 지웠을 때 나머지 모든 원소들이 증가하는 형태를 나타내는 것을 말합니다. [1, 3, 2, 4]라는 배열이 있다고 가정하겠습니다. 그럼 증가하는 부분 수열은 [1, 3], [1, 3, 4], [1, 2, 4] 등이 나올 수 있습니다. 이런 부분 수열 중에서 가장 긴 수열을 LIS라고 합니다. LIS 알고리즘 LIS를 구현하는 알고리즘은 다음과 같습니다. 다른 모든 원소들을 비교하는 O(N^2) 알고리즘 이진 탐색으로 원소들을 비교하는 O(NlogN) 알고리즘 N^2 알고리즘 이 알고리즘은 각 원소마다 해당 원소를 마지막 원소로 가진 LIS 길이를 구합니다. 이 길이중에서 가장 긴 길이가 전체 LIS길이가 됩니다. 각 원소..