본문 바로가기

알고리즘

 (5)
[ 알고리즘 ] DP(Dynamic Programming) - 동적계획법 안녕하세요 ! 이번 글에서는 DP를 알아보도록 하겠습니다. DP란? 큰 문제를 작은 문제로 나눠서 해결하는 방법을 말합니다. 주어진 문제에서 반복되는 작은 문제를 찾고, 이를 해결하면 큰 문제가 해결되는 것입니다. 예를 들어서 피보나치 수열로 설명할 수 있습니다. 피보나치는 1, 1, 2, 3, 5, 8, 13, ... 으로 n번째 수 = n-1번째 수 + n-2번째 수 의 형태로 표현할 수 있습니다. public int fibonacci(int n) { int[] dp = new int[n+2]; dp[1] = 1; dp[2] = 1; for (int i = 3; i
[알고리즘] 자료구조 - 특수 정렬 ( 계수 정렬, 기수 정렬, 버킷 정렬 ) 이번 글에서는 정렬 중 특수 정렬에 대해서 정리해보겠습니다 ! ( 지난 기본 정렬, 고급 정렬에 이어 특수 정렬도 오름차순을 기준으로 설명하겠습니다. ) 특수 정렬인 계수 정렬, 기수 정렬, 버킷 정렬에 대한 개념 정리를 하고 예시 코드도 설명하도록 하겠습니다. 계수 정렬 ( Counting Sort ) 정렬되지 않은 배열의 수들을 각 수들이 몇번 나왔는지 세고, 순서대로 정렬하는 알고리즘 정렬 과정 배열의 수들이 몇번 나왔는지 세어줍니다. → 몇 번 나왔는 지 count한 배열을 순회하여 정렬된 배열에서 몇 번째에 나와야 하는지 기록해줍니다. 아이디어는 굉장히 간단합니다. 정렬할 데이터들이 주어졌을때 각 데이터들의 갯수를 count해주고 몇 번째 나와야 할지 ( 현재 숫자 앞의 숫자의 갯수 : coun..
[알고리즘] 자료구조 - 고급정렬 ( 병합 정렬, 퀵 정렬, 힙 정렬, 셸 정렬 ) 지난 글에서 기본정렬에 대해서 알아보았습니다 ! 이번 글에서는 고급 정렬을 정리해보겠습니다 ! ( 지난번과 같이 오름차순을 기준으로설명하겠습니다. ) 고급 정렬에는 병합 정렬, 퀵 정렬, 힙 정렬, 셸 정렬이 있습니다. 그럼 순서대로 개념 정리를 해보고, java 로 구현한 예시 코드도 소개하도록 하겠습니다. 병합 정렬 ( Merge Sort ) 분할, 정복, 결합으로 정렬하는 알고리즘 정렬 과정 분할 : 데이터 배열을 같은 크기의 2개의 부분 배열로 분할합니다. → 정복 : 부분 배열의 크기가 1이 될때까지 순환 호출로 분할을 반복해서 합니다. 부분 배열의 크기가 1이 되면 부분 배열을 정렬합니다. → 결합 : 정렬된 부분 배열을 하나의 배열에 합병합니다. 결합할 때에는 왼쪽 부분 배열과 오른쪽 부분 ..
[알고리즘] 자료구조 - 기본 정렬 ( 선택 정렬, 버블정렬, 삽입 정렬 ) 정렬은 크게 기본 정렬, 고급 정렬, 특수 정렬 세가지로 나눌 수 있습니다. 이번 글에서는 기본 정렬에 대해서 정리해보겠습니다 ! 기본 정렬인 선택 정렬, 버블 정렬, 삽입 정렬에 대해 알아보겠습니다. ( 오름차순을 기준으로 설명하겠습니다. ) 선택 정렬 ( Select Sort ) 현재 위치에 들어갈 테이터를 찾아 선택하는 알고리즘 정렬 과정 주어진 리스트에서 최솟값을 찾습니다. → 최솟값을 맨 앞 자리의 값과 교환합니다. → 맨 앞 자리를 제외한 나머지 데이터들 중 최솟값을 찾아 같은 방법을 반복합니다. 1회전이 끝나면 맨 앞자리가 정해집니다. 시간 복잡도는 O(n^2)입니다. 버블 정렬 ( Bubble Sort ) 서로 인접한 두 데이터를 검사하여 정렬하는 알고리즘 정렬 과정 첫 번째 데이터와 두 ..
정렬 알고리즘 알고리즘과 자료구조에 대해 다시 짚어보면서 개념을 정리하고 기록해보려고합니다. 우선, 오늘 정리할 개념은 정렬 알고리즘입니다. 전공 과정상 수업시간에도 다뤄졌던 내용이지만, 확실히 정리해두지 않으면 개념에 대한 이해도가 많이 떨어질 것 같아 시작하게되었습니다. Do my utmost. 이제 시작입니다! 버블 정렬(Bubble Sort) 인접한 두 개의 원소를 비교하여 정렬하는 알고리즘 시간 복잡도 : O(n^2) 공간 복잡도 : O(1) [4, 2, 5, 1, 3] 첫번째 원소 4와 두번째 원소 2를 비교한 뒤, 2가 더 작으므로 두 원소의 위치를 바꾼다. [2, 4, 5, 1, 3] 두번째 원소 4와 세번째 원소 5를 비교, 위치 변동X 세번째 원소 5와 네번째 원소 1 비교, 1이 더 작으므로 두 원..
728x90
반응형

티스토리툴바