Algorithm
-
[다이나믹 프로그래밍] 개념 정리Algorithm/개념정리 2021. 11. 23. 21:11
다이나믹 프로그래밍(동적 계획법)?! 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법임 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 구현은 일반적으로 2가지 방식(탑다운 & 보텀업)으로 구성됨 '동적 계획법' 이라고도 부르는데, 흔히 프로그래밍에서 다이나믹은 '프로그램이 실행되는 도중에' 라는 의미임 예를 들어, 자료구조에서 동적 할당은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법임 하지만 다이나믹 프로그래밍에서의 '다이나믹'은 동적 할당(Dynamic Allocation)에서의 다이나믹과는 다른 의미임 다이나믹 프로그래밍의 기본적인 아이디어 1줄 요약 : 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면..
-
[이진 탐색] 문제 이름 : 부품 찾기 - 배열 Sort, Binary SearchAlgorithm/유형별 문제 풀기 2021. 11. 18. 11:33
문제 설명 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M = 3 [5, 7, 9] 이때 가게 안에 손님이 원하는 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 사용 개념 탐색 문제 해결 아이디어 비교 대상이 되는 값들을(가게의 부품 번호) 배열에 저장하므로, java.util.Arrays 에서 제공하는 sort()로 정렬하고, binarySearch() 사용하여 탐색함 코드 import java.util.Arrays; import java.util.Scanner; public class Q1 { public static void main(String[] args) {..
-
[이진 탐색] 개념정리Algorithm/개념정리 2021. 11. 18. 10:25
순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 '보통 정렬되지 않은 리스트'에서 데이터를 찾아야 할 때 사용함 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 시간 복잡도: O(N) → 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요함 이진 탐색 : 반으로 쪼개면서 탐색하기 조건: 배열 내부의 데이터가 정렬되어 있어야 함 → 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음 특징: 탐색 범위를 좁혀가며 데이터 탐색 가능함 이진 탐색은 위치를 나타내는 변수 3개를 사용함(탐색하고자 하는 범위의 시작점, 끝점, 중간점) 찾으려는 데이터와..