본문 바로가기

알고리즘 공부5

그리디,구현,DP / 순열조합,GCD,LCM, 멱집합 코드스테이츠에서 배운 알고리즘2 그리디 알고리즘, 구현(+시뮬레이션), Dynamic Programming https://riverpigeon.tistory.com/189 4/5 일일정리 알고리즘 Greedy,구현,DP Greedy Algorithm 그리디(탐욕) 알고리즘은 선택의 순간에 눈앞의 가장 최적인 상황을 고르면서 해답에 도달하는 방법이다. 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 riverpigeon.tistory.com 순열/조합 , GCD/LCM , 멱집합(Power Set) https://riverpigeon.tistory.com/191 4/6 일일정리 알고리즘(순열/조합,GCD/LCM, 멱집합) 순열과 조합 순열(Permutation) 순열은 서로 다른 n개의.. 2023. 4. 8.
재귀, 스택/큐, 트리/그래프 코드스테이츠 과정에서 배운 자료구조/ 알고리즘 재귀 https://riverpigeon.tistory.com/120 2/13 일일정리 재귀 재귀 알고리즘 재귀(recursion)함수란 자기 자신을 호출하는 함수를 말한다. function recursion () { console.log("This is") console.log("recursion!") recursion() } 위의 코드는 끝에 자기자신을 호출하여 무한정으로 co riverpigeon.tistory.com 스택 / 큐 https://riverpigeon.tistory.com/165 3/14 일일정리 스택/큐 자료구조 자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다. 여러 자료 구조중에 오늘은 스택과 큐에 대해 공부해.. 2023. 3. 14.
합병 정렬 , 퀵 정렬, 기수 정렬 합병 정렬(Merge Sort) 합병정렬은 분할, 정렬, 합병 세가지가 조합되어 있다. 분할 정복 알고리즘을 활용한다. 먼저 배열을 반으로 반으로 반으로 계속 분할해서 요소가 0개 또는 1개인 배열로 전부 쪼개질 때 까지 분할한다. 배열을 분할하는데는 재귀함수 사용한다. 0개요소, 1개요소 배열은 이미 정렬되어 있다. 쪼개진 0개 또는 1개 자리 배열을 다시 2개씩 합병한다. 다 합치면 다시 배열을 2개씩 합병하고 다합치면 또 2개씩 합병하고... 를 반복한다. 배열을 합칠 때 2개의 배열 요소 전부를 정렬하면서 합친다. 배열을 2개씩 계속해서 합쳐가면서 원래 크기의 배열이 될 때까지 합친다. 배열 합병 역시 재귀함수를 활용한다. 합병을 위한 서브 함수가 하나 필요하다. 복잡도 분할할때 log n , 비.. 2023. 3. 4.
버블 정렬, 선택 정렬, 삽입 정렬 1. 버블정렬(Bubble Sort) 버블 정렬은 인접한 두 요소를 비교하여 정렬하는 알고리즘이다. 1번째 요소와 2번째 요소비교후 정렬, 2번째원소와 3번째요소 비교후 정렬, ... n-1번째 요소와 n번째 요소를 비교하여 정렬한다. 그러면 마지막 n번 요소는 자신의 자리에 정렬이된다. 이후 다시 첫번째 요소부터 n-1 번째 요소까지 위의 과정을 반복하면 n-1번재 요소도 자신의 자리에 정렬된다. 이 과정을 마지막 요소가 정렬될 때 까지 반복하여 정렬한다. 시간복잡도 평균 : O(n^2) 예시 자바스크립트 코드(오름차순 정렬) function bubbleSort(arr) { let notSorted; for (let i = arr.length; i > 0; i--) { notSorted = true; .. 2023. 2. 27.
Big O Notation 빅 오 표기법 대부분의 사람들이 알고리즘 공부를 시작할 때 Big O Notation, 빅 오 표기법이라는 개념을 접하게 된다. 컴퓨터 과학에서의 빅 오 표기법은 일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다. 시간복잡도란 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다. (* 공간복잡도의 이론적인 상한은 시간복잡도이기 때문에 보통은 시간복잡도가 좀 더 중요하게 취급된다.) 쉽게 이야기 하면 입력값의 개수가 늘어날 때 출력까지 걸리는 시간이 얼마나 되느냐를 함수 혹은 그래프 형태로 나타내는 표기법이라고 할 수 있다. 배경 빅 오 표기법과 같은 시간, 공간복잡도 측정 기법이 생겨난 배경은 알고리즘의 성능을 측정하기 위해서다. 일반적으로 하나의 알고리즘 문제에서 해답이 될 수.. 2023. 2. 20.

티스토리툴바