Algorithm (10) 썸네일형 리스트형 [A-Z] 자바스크립트 자주 출제되는 알고리즘 문제 - 1. 문제 역순 String Reversal 시작하며 들어가기 앞서, 해당 블로그 내용은 현재 제가 구독하고 있는 siliconwat의 미디엄 블로그 글을 번역과 동시에 재해석하는 글임을 밝힙니다. 해당 자료는 아래 링크에서 참고할 수 있습니다 🫡 Algorithms in JavaScript 40 Problems, Solutions, and Explanations medium.com 원래 저는 전 직장에 근무할때만 하더라도 알고리즘 문제를 푸는 것이 업무적으로 그다지 도움이 된다고 생각을 하지 않았어요. 그러다가 백엔드 개발자들과 협업 및 코드리뷰를 진행하면서, 각자 다른 코딩 스타일과 해결 방법이 있고 최적의 방법을 찾기 위해서는 많은 문제를 풀어봐야겠다는 생각이 들어 해당 글을 작성하게 되었습니다. 출제가 자주되는 자바스크립트의 알고리즘을 쉬운.. [Python] 퀵정렬 구현하기 quick sort 입력으로 n개의 수가 주어지면, quick sort를 구현하는 프로그램을 작성하세요. 입력 예시 10 2 3 4 5 6 9 7 8 1 출력 예시 1 2 3 4 5 6 7 8 9 10 퀵정렬을 통해 오름차순으로 정렬된 array를 반환하는 함수를 작성하세요. def quickSort(array): ''' 퀵정렬을 통해 오름차순으로 정렬된 array를 반환하는 함수를 작성하세요. ''' # 1. 기저조건: array의 요소가 비어있거나 하나인 경우에는 array를 리턴합니다. if len(array) /*elice*/ 분할정복법 1. 재귀호출을 이용한 문제 해결 재귀호출은 분할정복법 이외에도 자주 나오는 개념이기 때문에, 재귀호출의 중요성을 강조해왔습니다. 재귀함수의 올바른 디자인 및 해석 재귀함수를 디자인 하기 위한 세 가지 단계 1) 함수의 정의를 명확히 한다 2) 기저 조건에서 함수가 제대로 동작하게 작성한다 3) 함수가 제대로 동작한다고 가정하고 함수를 완성한다 아래의 실습에서 가장 먼저 시도해야 하는 것은 '완전탐색'입니다. 완전탐색으로 풀기 위해서는, O(n)의 시간복잡도가 걸리게 됩니다. 따라서 해당 문제에서는 완전탐색이 동작을 할 수 있지만 기저조건 중 하나는 정렬된 이라는 문장을 볼 수 있습니다. n개의 숫자가 정렬되어 있다는 점을 이용한 방법으로는 이진탐색이 있습니다. 이진탐색에서는 중간값을 찾고 탐색을 시작합.. /*elice*/ 문제 해결 절차, 완전 탐색, 시간복잡도 1. 문제 해결의 절차 1. 문제를 정확히 이해한다. 2. 문제를 해결하는 알고리즘을 개발한다. 3. 알고리즘이 문제를 해결한다는 것을 증명한다. 4. 알고리즘이 제한시간내에 동작한다는 것을 보인다. 5. 알고리즘을 코드로 작성한다. 6. 제출 후 만점을 받고 매우 기뻐한다. 2. 시간 복잡도 알고리즘이 대략 몇개의 명령을 수행하는가? 프로그램의 수행 시간을 유추할 수 있음 sum = 0 for i in range(n) : for j in range(i) : sum = sum + i + j 이 알고리즘의 시간 복잡도는 O(n^2)으로, 해당 연산은 {n x (n-1)} / 2 으로 계산하여 최고 차항만을 취합니다. 왜? n^2 + 2n + 3 이 식에서 만약 n이 1000이라면, n^2 = 1,000,.. [Python] k번째 수 찾기 k번째 수 찾기 n개의 숫자가 차례대로 주어질 때, 매 순간마다 "지금까지 입력된 숫자들 중에서 k번째로 작은 수"를 반환하는 프로그램을 작성하세요. 프로그램의 입력으로는 첫째줄에 n과 k가 입력되고, 둘째줄에 n개의 숫자가 차례대로 주어집니다. 입력 예시 10 3 1 9 8 5 2 3 5 6 2 10 출력 예시 -1 -1 9 8 5 3 3 3 2 2 문제 조건 · n은 100보다 작은 숫자입니다. · 매 순간마다 지금까지의 입력중 k번째로 작은 수를 출력하되, 없다면 -1을 출력합니다. 입출력 예시 설명 10개의 숫자가 차례대로 주어집니다. 맨 처음 1만 입력을 받았을 경우, 3번째로 작은 숫자가 없으므로 -1을 출력합니다. 그 다음 9도 마찬가지입니다. 세 번째로 숫자 8을 입력받은 순간, 지금까지 .. /*elice*/ 알고리즘과 수학적 귀납법을 이용한 재귀호출이란? 1. 알고리즘이란? 알고리즘이란 문제를 해결하는 방법입니다. 예를 들어 전구가 작동하지 않는다면, 전구를 작동하도록 만드는 순서도를 구현하여 풀어본다면 아래와 같이 보일 것 입니다. 여기서 우리가 배우는 알고리즘이란, 계산을 통하여 해결할 수 있는 문제를 해결하는 방법입니다. 알고리즘에는 5가지 성질이 있습니다. 유한성 | 유한한 횟수를 거친 후 종료. 종료되지 않는 무한 루프는 알고리즘이 아닙니다. 명확성 | 각 단계가 명확하게 정의되어야 합니다. 입력 | 입력은 0개 이상 출력 | 출력은 1개 이상 효과성 | 시간적, 공간적인 효율과 유의미 해야합니다. [실습 1] k번째 숫자 찾기 문제를 해결하는 방법 1. 숫자 하나를 입력받는다. 2. 지금까지 받은 숫자들을 정렬한다. 3. k번째로 작은 숫자를 .. 프론트엔드 개발자라면 알아야할 다섯가지 알고리즘 5 JavaScript Algorithms You Should Know How To Solve 5 Beginner JavaScript Algorithms With Examples javascript.plainenglish.io 이 블로그 글은 위의 내용을 번역한 자료입니다! 알고리즘이란 무엇인가? What is an Algorithm? 알고리즘은 문제를 해결하기 위한 또는 특정한 결과에 다다르기 위한 순서의 나열이다. 알고리즘을 풀기 위해서는 그 문제를 이해를 해야하고, 코딩으로 풀 수 있어야한다. 알고리즘을 쉽게 해결하기 위해서는 먼저 작은 부분들로 나누어야 한다. 그리고 이 작은 문제를 먼저 풀어나가는게 전체 문제에 먼저 접근하는 것보다 훨씬 쉬울 것이다. 알고리즘은 매우 중요하고 유용하다. 코딩 문.. [알고리즘] 알고리즘의 기초 정리자료-2 알고리즘 기초 정리자료-1 (분할정복, 동적 프로그래밍, 욕심쟁이)에 이어서 만들었기 때문에, 링크는 여기에 → https://sohyunsaurus.tistory.com/6 (4) 정렬 알고리즘 ❋ 내부정렬 ↔️ 외부정렬 정렬하고 싶은 모든 데이터를 주기억장치에 적재시킨이후에 하는 것을 내부정렬이다. 정렬하는 방식에 따라 내부 정렬은 비교 기반 알고리즘 ↔️ 데이터 분포 기반 알고리즘으로 나눠진다. ❋ 안정적 정렬 동일한 값을 갖는 데이터가 정렬 전의 상대적 위치와 정렬 후의 상대적 위치가 동일할 경우 ❋ 제자리 정렬 내가 정렬하고 싶은 입력 데이터를 저장하는 공간 이외에 추가적인 공간이 상수개 만큼 필요할 때는 제자리 정렬 추가적으로 필요할 때엔 제자리 정렬이 아니다. 정렬 방식 알고리즘 성능 안정적.. 이전 1 2 다음
