[알고리즘] 동적 계획법(Dynamic Programming) 알아보기개발/DS&Algorithms / 2022. 5. 7.안녕하세요😎 백엔드 개발자 제임스입니다 :) 이번에는 동적 계획법과 관련해서 포스팅하려고 합니다. 사실 동적 계획법은 어떠한 문제를 풀기 위한 전략 또는 기법에 가깝습니다. 따라서 추후 알고리즘을 다룰 때 해당 기법을 응용하여 개념을 정의하는 경우가 종종 있습니다. 이제 자세하게 알아보도록 하겠습니다. 동적계획법(Dynamic Programming, DP) DP라고도 불리는 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 각 결과들을 저장한 뒤, 다시 큰 문제를 해결하는 방법입니다. 이것을 '상향식 접근법'이라고 하며, 가장 최하위 해답을 구한 후 이것을 활용하며, 상위 문제를 풀어가는 의미입니다. 캐시(cache) : 이미 계산한 값을 저장해 두는 메모리 중복되는 부분 문제(overla..
[알고리즘] 재귀 용법(recursive call, 재귀 호출) 알아보기개발/DS&Algorithms / 2022. 5. 2.안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘은 재귀 용법 또는 재귀 호출에 대해서 포스팅하려고 합니다. 이 재귀 용법은 어떻게 보면 중요한 개념인데요. 앞으로 알고리즘을 학습하다 보면 굉장히 많이 접하기 때문입니다. 이제 자세하게 알아보도록 하겠습니다. 재귀 용법 (recursive call, 재귀 호출) 재귀는 자기 자신을 참조하는 것 함수 안에서 동일한 함수를 호출하는 형태 '재귀 함수'라고도 함 코드의 가독성이 좋음 스택 메모리 사용 예시 형태 public int sum(int num) { * * // 생략 * return sum(num-1); } 위 코드 내용처럼 함수 안에서 자신을 호출하는 방식입니다. 단, 재귀 함수를 사용할 때 호출시마다 입력값(파라미터)은 변합니다. 그리고 위 코드에서..
[알고리즘] 삽입 정렬(Insertion sort) 알아보기개발/DS&Algorithms / 2022. 4. 26.안녕하세요 🌟🌟 오늘 포스팅할 내용은 정렬 알고리즘 중, [삽입 정렬]입니다. 이번에도 역시 [버블 정렬], [선택 정렬]과 비슷한 방식으로 진행되고, 마찬가지로 구현이 어렵지 않습니다. 이제 삽입 정렬에 대해서 자세하게 알아보도록 하겠습니다 :) * 다양한 정렬 알고리즘 1. 버블 정렬 2. 선택 정렬 3. 삽입 정렬 4. 병합 정렬 5. 퀵 정렬 6. 힙 정렬 삽입 정렬(Insertion Sort) 이미 정렬된 상태에서 새로운 요소를 추가하여 비교한 후, 재정렬하는 방식 손 안의 카드를 정렬하는 방법과 유사 01. 그림으로 방식 이해하기 어센딩 방식을 예시로 들었습니다. 아래 [9, 1, 4, 2, 7]을 가진 배열이 있습니다. 1) 정렬을 하기 위해서 먼저 인덱스 1번 데이터를 인덱스 0번의 데이터..
[알고리즘] 선택 정렬(Selection sort) 알아보기개발/DS&Algorithms / 2022. 4. 25.안녕하세요🌟 이번 포스팅은 저번에 이어서 정렬 알고리즘의 [선택 정렬]에 대해서 알아보도록 하겠습니다. * 다양한 정렬 알고리즘 1. 버블 정렬 2. 선택 정렬 3. 삽입 정렬 4. 병합 정렬 5. 퀵 정렬 6. 힙 정렬 선택 정렬(Selection Sort) 주어진 배열(데이터) 속에서 전체 순회를 하여 최솟값을 찾고, 해당 최솟값을 배열의 맨 앞 데이터와 위치 교환 이와 같이 순회를 돌면서 최소값을(디센딩 방식은 최댓값을) 찾고 선택하여 교체하며 정렬하는 방식 단, 앞으로 이동한 최소값들은 다음 순회 때 순회 대상에서 제외됨 어떻게 보면 버블 정렬과 유사합니다. 01. 그림으로 방식 이해하기 어센딩 방식을 예시로 들었습니다. 1) 아래 그림처럼 정렬되지 않은 데이터를 가진 배열이 있습니다. 인덱스 0..
[알고리즘] 버블 정렬(bubble sort) 알아보기개발/DS&Algorithms / 2022. 4. 21.안녕하세요🌟 이번 포스팅은 알고리즘 중 [정렬 알고리즘]에 대해서 정리하려고 합니다. 정렬 알고리즘은 원소(데이터)들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘입니다. 예를 들어서 배열 안에 [ 3, 5, 1, 2, 4 ] 처럼 값이 무작위로 있을 때, 다양한 방법을 통해서 [ 1, 2, 3, 4, 5 ] 와 같이 수 들을 정렬하는 것입니다. 정렬을 위한 알고리즘은 다양하게 존재합니다. 대표적으로는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등이 있는데요. 어떤 알고리즘을 사용하느냐에 따라 공간 및 시간 복잡도가 상이하여 서로 다른 수행 시간을 보입니다. * 다양한 정렬 알고리즘 1. 버블 정렬 2. 선택 정렬 3. 삽입 정렬 4. 병합 정렬 5. 퀵 정렬..
[자료구조] 힙(Heap) 알아보기개발/DS&Algorithms / 2022. 4. 14.안녕하세요😊 오늘은 힙(Heap)에 대해서 포스팅하도록 하겠습니다. 힙(Heap) 힙(Heap) 자료구조는 완전 이진트리를 기초로 하며, 우선순위 큐를 위해 만들어진 자료구조입니다. 힙 자료구조를 사용하면 최댓값과 최솟값을 빠르게 찾을 수 있습니다. 보통 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(N)이 걸립니다. 하지만 Heap은 O(logN)만 발생하게 됩니다. 자세한 것은 뒤에서 알아보도록 하겠습니다. 배열을 통해 [최댓값과 최솟값을 구하는 알고리즘]은 아래 링크를 참고해주세요. https://kang-james.tistory.com/entry/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-JAVA%EB%A1%9C-%ED%91%B8%EB%8A%94-%E..
[알고리즘] 동적 계획법(Dynamic Programming) 알아보기
개발/DS&Algorithms
/ 2022. 5. 7.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 이번에는 동적 계획법과 관련해서 포스팅하려고 합니다. 사실 동적 계획법은 어떠한 문제를 풀기 위한 전략 또는 기법에 가깝습니다. 따라서 추후 알고리즘을 다룰 때 해당 기법을 응용하여 개념을 정의하는 경우가 종종 있습니다. 이제 자세하게 알아보도록 하겠습니다. 동적계획법(Dynamic Programming, DP) DP라고도 불리는 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 각 결과들을 저장한 뒤, 다시 큰 문제를 해결하는 방법입니다. 이것을 '상향식 접근법'이라고 하며, 가장 최하위 해답을 구한 후 이것을 활용하며, 상위 문제를 풀어가는 의미입니다. 캐시(cache) : 이미 계산한 값을 저장해 두는 메모리 중복되는 부분 문제(overla..
[알고리즘] 재귀 용법(recursive call, 재귀 호출) 알아보기
개발/DS&Algorithms
/ 2022. 5. 2.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘은 재귀 용법 또는 재귀 호출에 대해서 포스팅하려고 합니다. 이 재귀 용법은 어떻게 보면 중요한 개념인데요. 앞으로 알고리즘을 학습하다 보면 굉장히 많이 접하기 때문입니다. 이제 자세하게 알아보도록 하겠습니다. 재귀 용법 (recursive call, 재귀 호출) 재귀는 자기 자신을 참조하는 것 함수 안에서 동일한 함수를 호출하는 형태 '재귀 함수'라고도 함 코드의 가독성이 좋음 스택 메모리 사용 예시 형태 public int sum(int num) { * * // 생략 * return sum(num-1); } 위 코드 내용처럼 함수 안에서 자신을 호출하는 방식입니다. 단, 재귀 함수를 사용할 때 호출시마다 입력값(파라미터)은 변합니다. 그리고 위 코드에서..
[알고리즘] 삽입 정렬(Insertion sort) 알아보기
개발/DS&Algorithms
/ 2022. 4. 26.
안녕하세요 🌟🌟 오늘 포스팅할 내용은 정렬 알고리즘 중, [삽입 정렬]입니다. 이번에도 역시 [버블 정렬], [선택 정렬]과 비슷한 방식으로 진행되고, 마찬가지로 구현이 어렵지 않습니다. 이제 삽입 정렬에 대해서 자세하게 알아보도록 하겠습니다 :) * 다양한 정렬 알고리즘 1. 버블 정렬 2. 선택 정렬 3. 삽입 정렬 4. 병합 정렬 5. 퀵 정렬 6. 힙 정렬 삽입 정렬(Insertion Sort) 이미 정렬된 상태에서 새로운 요소를 추가하여 비교한 후, 재정렬하는 방식 손 안의 카드를 정렬하는 방법과 유사 01. 그림으로 방식 이해하기 어센딩 방식을 예시로 들었습니다. 아래 [9, 1, 4, 2, 7]을 가진 배열이 있습니다. 1) 정렬을 하기 위해서 먼저 인덱스 1번 데이터를 인덱스 0번의 데이터..
[알고리즘] 선택 정렬(Selection sort) 알아보기
개발/DS&Algorithms
/ 2022. 4. 25.
안녕하세요🌟 이번 포스팅은 저번에 이어서 정렬 알고리즘의 [선택 정렬]에 대해서 알아보도록 하겠습니다. * 다양한 정렬 알고리즘 1. 버블 정렬 2. 선택 정렬 3. 삽입 정렬 4. 병합 정렬 5. 퀵 정렬 6. 힙 정렬 선택 정렬(Selection Sort) 주어진 배열(데이터) 속에서 전체 순회를 하여 최솟값을 찾고, 해당 최솟값을 배열의 맨 앞 데이터와 위치 교환 이와 같이 순회를 돌면서 최소값을(디센딩 방식은 최댓값을) 찾고 선택하여 교체하며 정렬하는 방식 단, 앞으로 이동한 최소값들은 다음 순회 때 순회 대상에서 제외됨 어떻게 보면 버블 정렬과 유사합니다. 01. 그림으로 방식 이해하기 어센딩 방식을 예시로 들었습니다. 1) 아래 그림처럼 정렬되지 않은 데이터를 가진 배열이 있습니다. 인덱스 0..
[알고리즘] 버블 정렬(bubble sort) 알아보기
개발/DS&Algorithms
/ 2022. 4. 21.
안녕하세요🌟 이번 포스팅은 알고리즘 중 [정렬 알고리즘]에 대해서 정리하려고 합니다. 정렬 알고리즘은 원소(데이터)들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘입니다. 예를 들어서 배열 안에 [ 3, 5, 1, 2, 4 ] 처럼 값이 무작위로 있을 때, 다양한 방법을 통해서 [ 1, 2, 3, 4, 5 ] 와 같이 수 들을 정렬하는 것입니다. 정렬을 위한 알고리즘은 다양하게 존재합니다. 대표적으로는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등이 있는데요. 어떤 알고리즘을 사용하느냐에 따라 공간 및 시간 복잡도가 상이하여 서로 다른 수행 시간을 보입니다. * 다양한 정렬 알고리즘 1. 버블 정렬 2. 선택 정렬 3. 삽입 정렬 4. 병합 정렬 5. 퀵 정렬..
[자료구조] 힙(Heap) 알아보기
개발/DS&Algorithms
/ 2022. 4. 14.
안녕하세요😊 오늘은 힙(Heap)에 대해서 포스팅하도록 하겠습니다. 힙(Heap) 힙(Heap) 자료구조는 완전 이진트리를 기초로 하며, 우선순위 큐를 위해 만들어진 자료구조입니다. 힙 자료구조를 사용하면 최댓값과 최솟값을 빠르게 찾을 수 있습니다. 보통 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(N)이 걸립니다. 하지만 Heap은 O(logN)만 발생하게 됩니다. 자세한 것은 뒤에서 알아보도록 하겠습니다. 배열을 통해 [최댓값과 최솟값을 구하는 알고리즘]은 아래 링크를 참고해주세요. https://kang-james.tistory.com/entry/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-JAVA%EB%A1%9C-%ED%91%B8%EB%8A%94-%E..