개발지식 먹는 하마 님의 블로그

Java 전공책 복습을 이어갔다.오버라이딩 부분을 공부했다.동적 탐색법 문제를 풀려고 했는데 이분 탐색을 알아야 했다.이분탐색을 공부하고 관련 문제를 하나 풀어본 후, 해당 문제 풀이를 완료했다.가계부 프로젝트를 진행했다.정말 나만 쓰려고 했는데, 프로젝트 개발 이야기를 들은 친구가 자기도 쓰고 싶다고 얘기했다.보안 문제와 데이터 베이스 사용량 때문에 고민했는데한 명 정도는 괜찮을 것 같아서 흔쾌히 수락했다.친구에게만 배포 후, 필요한 기능을 추가해나가는 과정이 재밌을 것 같았다.따라서, 친구와 나를 구분해줄 로그인 페이지를 먼저 만들기로 했다.[오늘의 학습 키워드]#오버라이딩 #이분 탐색 #동적 계획법 #로그인 페이지 [학습 내용 정리]오버라이딩https://devhippo.tistory.com/39 ..

[ 오버로딩 overloading ]한 클래스 내에서 같은 이름의 메소드가 여러 개 정의될 때, 오버로딩 또는 메소드 중복이라고 한다.중복되는 메소드들은 매개변수의 개수 또는 타입이 달라야 한다.오버로딩은 자동으로 타입을 변환할 수 있다.max(double n1, double n2){ }max(double n1, double n2, double n3){ }위와 같은 함수가 오버로딩 되었을 때, max(5, 10)을 호출하면max(int n1, int n2)가 없기 때문에 매개변수의 타입이 자동으로 변환되어max(double n1, double n2)가 호출된다.[ 오버라이딩 overriding ]수퍼클래스의 메소드와 서브클래스의 메소드가 이름, 매개변수의 목록, 반환 타입까지 모두 같을 때,이를 메소드 ..

[Dynamic Programming, 동적 계획법]큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.탐욕법 Greedy Algorithm은 작은 단계에서 최선의 방법만 고려하지만,동적계획법은 작은 단계에서 모든 방법을 계산한다는 차이점이 있다.​일부 단계에서는 최선이 아닌 방법들이 전체 문제에서 최적방법이 되는 경우를 고려한다.완전탐색과는 달리, Memoization을 사용한다.계산한 부분문제들의 데이터를 별도 메모리에 저장하여, 추후 같은 계산이 필요한 경우 상수시간만에 해당 값을 호출한다.문제를 읽고 점화식을 어떻게 구성하는지에 따라 복잡도가 확연히 달라진다.ex) 거스름돈을 얼마나 지급할 것이냐.[탐욕법]1000원짜리부터 최대한 많이 사용해서 동전의 개수를 줄인다.[동적 계획법 ]모든 경우의 수를 ..

https://www.acmicpc.net/problem/11053> 제한조건더보기시간제한 : 1초메모리 제한 : 256MB> 문제더보기수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.> 입력더보기첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)> 출력더보기첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.> 풀이1. 이분 탐색 법의 lower_bound를 사용한다.2..

https://www.acmicpc.net/problem/2805> 제한조건더보기시간제한 : 1초메모리 제한 : 256MB> 문제더보기상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는..

[ 이분탐색 (Binary Search) ]정렬된 데이터에서 특정 값을 찾는 알고리즘이다.탐색 범위를 반씩 줄여나간다.O(log n) 대규모 데이터에 대해서 효율적이다.#include #include #include using namespace std;int main() { int target; vector list; int left = 0; int right = list.size() - 1; int mid; int result = -1; while (left target) { //탐색값이 타겟보다 큰 경우 right = mid-1; //좌측 탐색 } else { //탐색값이 타겟보다 작은 경우 left = mid+1; //우측 ..