알고리즘, 자료구조
-
[Javascript] Codility Lesson 6 - NumberOfDiscIntersections알고리즘, 자료구조/Codility 2022. 5. 16. 01:44
문제: https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/ 문제 요약: 겹치는 원이 총 몇 쌍인지 구해야한다. 원의 반지름을 나타내는 정수를 요소로 갖는 배열 A가 주어진다. 배열 A의 길이 범위는 [1... 100000] 이다. 배열 A의 각 요소 범위는 [0..2147483647] 이다. 겹치는 원의 쌍이 10,000,000를 초과하면 -1를 반환한다. function solution(A) { let result = 0; let discsList = A.map((radius, point) => { return [point - radius, point + radius] }); discsList.sort(..
-
[Javascript] Codility Lesson 5 - GenomicRangeQuery알고리즘, 자료구조/Codility 2022. 5. 15. 15:37
문제: https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/ 문제 요약: A,C,G,T로 이루어진 문자열 S가 주어지며 각 문자는 순서대로 1,2,3,4 값을 갖는다. (A=1, C=2, G=3, T=4) 문자열 S의 길이 범위는 [1... 100000] 이다. 동일한 길이의 배열 P,Q가 주어지며, 배열의 요소 범위는 [0... N - 1] 이다. 배열 P,Q의 길이 범위는 [1... 50000] 이다. P[i]
-
[Javascript] Codility Lesson 4 - MissingInteger알고리즘, 자료구조/Codility 2021. 11. 22. 23:54
문제: https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/ 문제요약: N개의 요소를 갖는 배열A가 주어짐 배열 A의 요소 범위는 -100,000 ~ 100,000 배열 A의 요소에 미포함된 자연수 중 최솟값 찾기 function solution(A) { A.sort((a, b) => a - b); let min = 1; if (A[A.length - 1] min) { break; }; min = A[i] + 1; }; return min; ..
-
[Javascript] Codility Lesson 4 - MaxCounters알고리즘, 자료구조/Codility 2021. 11. 22. 01:52
문제: https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/start/ 문제 요약: N개의 0으로 채워진 a배열과, 임의의 수로 채워진 b배열이 있다고 가정 b배열을 순회하며 요소의 값에 따라 a배열의 요소 + 1 (increase) b요소의 값이 N + 1이면 a배열의 모든 요소를 max 값으로 변경 (maxCounter) function solution(N, A) { let nCounter = new Array(N).fill(0); const increase = (arr, x) => { arr[x - 1] += 1; return arr; } const maxCounter = (arr) => { let max = M..
-
[Javascript] 프로그래머스 디스크 컨트롤러알고리즘, 자료구조/프로그래머스 2021. 3. 24. 15:01
문제 programmers.co.kr/learn/courses/30/lessons/42627# 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr '하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.'라는 제한 사항이 이 문제를 푸는데 핵심이라고 생각한다. 요청 시점이 빠른 순서대로 작업을 정렬할 것 다른 작업을 처리하느라 이미 요청 시점을 지나버린 경우, 해당 작업은 waitQueue에 적재할 것 waitQueue에 있는 작업들을 처리할 때 소요 시간이 작은 작업부터 처..
-
이진 탐색 알고리즘 (Binary search Algorithm)알고리즘, 자료구조/정리 2020. 8. 10. 10:32
이진 탐색 알고리즘(이분 탐색 알고리즘)은 정렬된 배열에서 특정 값의 위치를 찾는 알고리즘이다. 맨 처음 단계에서 정렬된 배열의 중간의 값을 임의의 값으로 선택한다. 선택한 임의의 값과 찾고자 하는 값의 크고 작음을 비교하여 탐색하는 방식이다. 만약 임의의 값이 찾는 값보다 클 경우, 임의의 값은 새로운 최댓값이 된다. 반대로 임의의 값이 찾는 값보다 작으면 해당 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있으나, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다(O(l ogN)). BinarySearch(A[0..N-1], value, low, high) { if (high value) return BinarySearch(A, value,..
-
프로그래머스 알고리즘 복습하기알고리즘, 자료구조/프로그래머스 2020. 8. 4. 17:17
최적해를 구해야 되는 문제, 완전 탐색을 해야 되는 문제는 개인적으로 어려워하는 유형이라 이미 풀어봤던 문제일지라도 다시 풀어보면서 복습해야 될 것 같다. 틈틈이 업데이트하자! 앞으로는 github에 업데이트하기: https://github.com/jaemin-jeong/algorithm-programmers jaemin-jeong/algorithm-programmers Programmers algorithm training : https://programmers.co.kr/ - jaemin-jeong/algorithm-programmers github.com 완전 탐색, DFS, BFS 1. 타겟 넘버 https://programmers.co.kr/learn/courses/30/lessons/43165..
-
동적 계획법 알고리즘 (Dynamic programming Algorithm)알고리즘, 자료구조/정리 2020. 7. 30. 12:00
동적 계획법 알고리즘이란 동적 계획법이란 하나의 복잡한 문제를 여러 개의 간단한 하위 문제로 나누어 푼 다음, 이를 결합하여 답을 도출해내는 방법이다. 나누어진 하위 문제들의 결과를 따로 저장해두었다가 이후 동일한 문제가 나왔을 시 저장해둔 결과를 가져다가 쓰면 같은 문제를 반복해서 풀지 않아도 되기 때문에 문제를 해결하는데 시간을 절약할 수 있다. 즉 한번 푼 하위 문제는 중복해서 풀지 않는다. 그렇다면 어떤 문제인 경우에 동적 계획법으로 해결할 수 있을까? 우선 문제를 나누어봤을 때 반복되는 작은 문제들이 나와야 되고, 전체 문제의 최적해가 부분 문제의 최적해들로 구성되는지 확인해야 된다. 이 두 가지 조건 모두 충족한다면 동적 계획법으로 풀 수 있는 문제일 것이다. 지금까지 썼던 내용을 간단히 요약..