LEESEUNGYEUL

알고리즘 키워드 1. 2. 3. 1. ( ) 가 뭔데? 정의를 적으시면 됩니다. 직역하자면 일관성 있는 서비스 추상화! 어댑터 패턴을 적용해 같은 일을 하는 다수의 기술을 공통의 인터페이스로 제어할 수 있게 한 것을 서비스 추상화라고 한다. 추상화 계층을 사용해서 어떤 기술을 내부에 숨기고 개발자에게 편의성을 제공해주는 것을 서비스 추상화(Service Abstraction)이라 한다. 서비스 추상화(Service Abstraction)로 제공되는 기술을 다른 기술 스택으로 간편하게 바꿀 수 있는 확장성을 갖고 있는 것이 Portable Service Abstraction이다. 환경과 세부 기술의 변화에 관계없이 일관된 방식으로 기술에 접근할 수 있게 해주는 것을 의미한다. 2. 알고리즘 대표하는 코드 ..

알고리즘 키워드 1. 2. 3. 1. LIS 가 뭔데? LIS == '가장 긴 증가하는 부분 수열' 부분 수열 (Subsequence) 수열에서 일부 요소를 제거하고 남은 요소들이 원래 순서대로 나열된 것을 말한다. 일반적으로 정형화된 알고리즘이라기 보다는, 알면 좋은 자주나오는 개념이라고 생각하면 된다. 1. 가장 기본적으로 해결하는 방법은 DP 를 사용하는 방법이 있고 -> O(N^2) 1) 수열의 각 위치에 대해서, 그 위치를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 찾아냄 2) 이후 이를 바탕으로 전체 문제의 해답을 구함. 2. 보다 효율적인 이분탐색을 가지고 활용하는 방안이 있다. -> O(NlogN) 1) 수열을 순차적으로 탐색하면서, 현재까지 발견된 가장 긴 증가하는 부분 수열을..

지난시간에는.. 1. 그리디 (Greedy) 탐욕 알고리즘의 원리 탐욕알고리즘 현재 상황에서 가장 좋아보이는 선택을 하는 방식으로 문제를 해결하는 방법 탐욕적 선택 속성 (Greedy Choice Property) 최적 부분 구조 (Optimal Substructure) 2. 예제 탐욕 알고리즘의 예제 크루스칼 알고리즘 다익스트라 알고리즘 그외 많이 나오는 그리디 알고리즘

1. 누적합 (Prefix Sum) 누적합을 왜 써야함? 정의 : 누적 합이란 배열의 각 요소에 대해 그 요소까지의 모든 요소의 합을 저장하는 방식. 쓰는 이유 1. 구간합을 빠르게 구하기 위해서 2. 특정값이 구간에 있는지 확인하기 위해서 1. 구간합을 빠르게 구하는 경우 배열에서 구간합을 구하는 경우일 때 사용한다. int[] arr = {1, 2, 3, 4, 5}; int[] prefixSum = new int[arr.length]; prefixSum[0] = arr[0]; for (int i = 1; i < arr.length; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i]; } int start = 1; int end = 3; int sum = prefix..