문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 출력 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 풀이 시간복잡도를 보면 가치의 합 최대가 10,000 , 그리고 동전의 갯수 최대가 100개이다. 따라서 복잡도는 O(n*k), 즉 100만번이 최대이다. 새로운 동전이 들..
람다식 설명 자바 1.8부터 추가되었다 함수랑 메서드는 약간은 다르다(메서드는 객체지향의 의미를 가진 함수, 클래스가 필요함) 사용이유 불필요한 코드를 줄이고, 가독성을 높이기 위함, 컴파일러가 문맥을 살펴 타입을 추론하고 람다식으로 선언된 함수는 1급 객체이기 때문에 Stream API의 매개변수로 전달가능 람다식 작성법 //기존 반환 타입 메서드이름(매개변수 선언){ 문장들 } //람다식 (매개변수 선언) -> { 문장들 } //return 식 대체 //기존 (매개변수 선언) ->{ return a>b ? a:b; } //람다식 (매개변수 선언) -> a > b ? a:b //심지어 타입까지 생략가능(int형인 a,b가 있다고 가정) (a, b) -> a > b ? a : b //파라미터하나일경우 a..
문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 풀이 첫번째 문자열과 비교해서 두번째 문자열의 문자가 들어올때마다 lcs값을 측정해줘야하고 첫번째 문자열의 문자와 새로들어온 문자가 같을때는 해당칸의 lcs와 앞선 문자의 max lcs를 비교해서 수정해줘야한다 그리고 수정한 문자의 위치는 방문체크를 해줘서 이후..
제네릭 정의 JDK 1.5에 처음 도입, 다양한 타입의 객체들을 다루는 메서드나 컬렉션 클래스에 컴파일 시의 타입 체크해주는 기능이다. 추가로 에러는 언제나 런타임보다 컴파일 타임에 잡는것이 좋다(런타임 에러는 프로그램이 실행되는 동안 발생하는데 이는 프로그램 실행 중단으로 이어질 수 있다) 제네릭의 장점 타입 안정성을 제공 리스트의 형을 정함으로써 컴파일러가 들어오는 데이터의 타입을 자동으로 체크해준다(리스트에 타입이 다른 데이터가 못들어오게함 = 안정성) 타입체크와 형변환을 생략 할 수 있으므로 코드가 간결해진다 ex. 원래는 list의 객체를 가져올때 object()형으로 반환되서(String)list.get(0)이런식으로 문자열을 가져와야하는게 이제는 쓸 필요가 없다 예시 //제네릭 미사용 Lis..
옵저버 패턴 정의 옵저버들의 목록을 객체에 등록하여 상태 변화가 있을 때마다 메서드 등을 통해 객체가 직접 목록의 각 옵저버에게 통지하도록 하는 디자인 패턴이다. 다른 객체의 상태 변화를 별도의 함수 호출 없이 즉각적으로 알 수 있기 때문에 이벤트에 대한 처리를 자주해야 하는 프로그램에 매우 효율적이다. 장점 실시간으로 한 객체의 변경사항을 다른 객체에 전파할 수 있다. 느슨한 결합으로 시스템이 유여하고 객체간의 의존성을 제거할 수 있다. 단점 너무 많이 사용할 경우 상태 관리가 힘들 수 있다. 데이터 배분에 문제가 발생하면 큰 문제로 발전할 수 있다. 옵저버 패턴 적용전 Client public class Client { public static void main(String[] args) { Scor..
Computer OS를 사용하는 이유(개발자 입장) 주요 구성 요소 요소 역할 CPU Central Processing Unit(중앙 처리 장치): 연산 Memory(주 기억 장치, RAM) 데이터 저장(휘발성) (SSD,HDD,…)보조 기억 장치 데이터 저장 I/O 장치 모니터, 키보드, 마우스 등 OS가 위에 언급된 구성 요소를 관리한다 프로세스 관리 및 CPU스케줄링 메모리 관리 보조 기억 장치 데이터(파일)관리 I/O처리 개발자가 OS를 알고있어야 하는 이유 추후 AWS서버에서 램, CPU를 설정할때 사용량에 관련해서 지나치게 비용지불을 하지 않아도 된다 Process/Thread Process(프로그램 실행 단위) 프로그램을 실행 → 하나의 프로세스가 생성 → CPU할당과 메모리에 적재 응용 프..
커맨드 패턴 정의 이벤트가 발생했을 때 실행될 기능이 다양하면서 변경이 필요한 경 우 이벤트를 발생시키는 클래스의 변경없이 재사용하고자 할 때 기술적정의: 실행될 기능을 캡슐화 함으로써 기능의 실행 요구하는 호출자 클래스(Invoker)와 실제 기능을 실행하는 수신자 클래스(Receiver, ex.Lamp)사이의 의존서을 제거한다. 따라서 기능의 변경에도 호출자 클래스를 수정없이 사용 가능 버튼이 눌렸을때 수행 될 기능을 캡슐화 기존의 코드는 OCP를 위배함 따라서 Command라는 인터페이스를 생성해서 새로운 기능이 추가되도 버튼에는 코드가 추가되지않는다. 커팬드 패턴 예시 이미지 출처 실습 인보커 로딩 순서 클라이언트 커맨드 객체 생성 SetCommand() 호출 클라이언트에서 인보커에서 명령 요청 ..
Data Base DBMS(Data Base Management System) RDB, NoSQL RDB(관계형 데이터베이스): MySQL, Oracle, Ms-SQL, SQLite NoSQL(Not Only SQL): Redis, Hbase, mongo DB DELETE vs TRUNCATE vs DROP DELETE: 데이터(ROW)만 삭제(따라서 1,2 삭제후 새로운 데이터 넣을때 다시 1,2id 지급) TRUNCATE: ROW도 삭제하는데 메타데이터도 삭제(1,2삭제후 데이터 넣을때 3,4id 지급) DROP: 완전히 테이블 자체를 삭제 DML, DDL, DCL 차이도 알아두면 좋음 DML(Data Manipulation Language): CRUD(Create, Read, Update, Dele..
문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 입력 첫..
문제 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ ..
