[백준][DP] 2294번 : 동전 2 문제
동전 2 성공
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 8781 | 2028 | 1361 | 24.629% |
문제
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)
입력
첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.
출력
첫째줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
예제 입력
3 15 1 5 12
예제 출력
3
힌트
출처
- 잘못된 조건을 찾은 사람: apples1309
- 데이터를 추가한 사람: isac322
'개발 > 백준_알고리즘' 카테고리의 다른 글
[백준] [DP] 2293번 동전 1 (1) | 2016.11.16 |
---|---|
[백준] [DP] 10942번 팰린드롬? 문제 (0) | 2016.11.14 |
[백준] 1254번 팰린드롬 만들기 (0) | 2016.11.13 |
[android] java파일에서 actionbar hide
Oncreate 에 추가 해주면 됩니다.
ActionBar actionbar = getSupportActionBar(); actionbar.hide(); | |
'개발 > [앱] Android' 카테고리의 다른 글
[안드로이드] Android Service 개념 및 사용방법 [펌] (0) | 2016.10.26 |
---|---|
[Android] Button을 처리하는3가지 방법 (0) | 2016.05.11 |
[js] HTML에서 JavaScript 로드하기
HTML에서 JavaScript 로드하기
1) inline 방식
inline 방식은 태그에 직접 자바스크립트를 기술하는 방식이다. 장점은 태그에 연관된 스크립트가 분명하게 드러난다는 점이다. 하지만 정보와 제어가 섞여 있기 때문에 정보로서의 가치가 떨어진다.
<!DOCTYPE html>
<
html
>
<
body
>
<
input
type
=
"button"
onclick
=
"alert('Hello world')"
value
=
"Hello world"
/>
</
body
>
</
html
>
onclick
=
"alert('Hello world')" : js의 이벤트를 부른다.
onclick, onchange 등등 값이 변했을때 반응하는 inline의 속성이다.
단점 : 정보 + 제어가 짬봉 되어있다. -> 코딩하는 사람의 입장에서 유지보수가 어렵다.
이문제 해결하는 방법 -> script tag!
2)Script
<script></script> 태그를 만들어서 여기에 자바스크립트 코드를 삽입하는 방식이다. 장점은 html 태그와 js 코드를 분리할 수 있다는 점이다
<!DOCTYPE html>
<html>
<body>
<input type=
"button"
id=
"hw"
value=
"Hello world"
/>
<script type=
"text/javascript"
> <- HTML5 부터 text/javascript 없이 사용가능
var
hw = document.getElementById(
'hw'
);
hw.addEventListener(
'click'
,
function
(){
alert(
'Hello world'
);
})
</script>
</body>
</html>
3)외부 파일로 분리
s를 별도의 파일로 분리할 수도 있다. 장점은 보다 엄격하게 정보와 제어를 분리할 수 있다. 하나의 js 파일을 여러 웹페이지에서 로드함으로서 js의 재활용성을 높일 수 있다. 캐쉬를 통해서 속도의 향상, 전송량의 경량화를 도모할 수 있다.
1 2 3 4 5 6 7 | <!DOCTYPE html> <html> <body> <input type= "button" id= "hw" value= "Hello world" /> <script type= "text/javascript" src= "script2.js" ></script> </body> </html> |
script2.js
1 2 3 4 | var hw = document.getElementById( 'hw' ); hw.addEventListener( 'click' , function (){ alert( 'Hello world' ); }) |
장점 : 유비 보수가 용이하다. (여러 html이 사용하는 js 하나만 고칠경우 다 고쳐지기 때문이다.)
캐쉬를 사용하기 때문에 속도 빠르고, 전송량 경량!
4)Script 파일의 위치
script를 head 태그에 위치시킬 수도 있다. 하지만 이 경우는 오류가 발생한다.
1 2 3 4 5 6 7 8 9 | <!DOCTYPE html> < html > < head > < script src = "script2.js" ></ script > </ head > < body > < input type = "button" id = "hw" value = "Hello world" /> </ body > </ html > |
아래와 같이 script2.js의 코드를 수정해야 한다.
1 2 3 4 5 6 | window.onload = function (){ var hw = document.getElementById( 'hw' ); hw.addEventListener( 'click' , function (){ alert( 'Hello world' ); }) } |
window.onload = function(){} 함수는 웹브라우저의 모든 구성요소에 대한 로드가 끝났을 때 브라우저에 의해서 호출되는 함수다. 이러한 것을 이벤트라고 하는데 이벤트는 뒤에서 배울 것이다.
자바스크립트의 특징 - 발견 시 바로 다운받는다 그 후 나머지내용 쭉 실행한다. 자바스크립트 파일의 코드는 head에서 호출시 hw아이디값을 가지고 있는것을 조회 아직 밑의 hw를 인식하지 못함 그래서 id = "hw" 값을 해석하기 전이다. 그래서 헤드의 hw는 null 값을 가지고 있다.
window.onload = function(){} 를 사용하여 헤드에서 사용해야한다.
바디 제일 아래에 해줄경우 window.onload를 사용할 필요가 없어진다.
성능 자체도 바디 제일 아래 하는것이 더 빠르다. 이유는 헤드에 스크립트를 만나게 될 경우 다운될때 까지 지연되기 때문에 사용자들은 웹페이지가
훨씬 빠르게 로드되는것 처럼 느낀다.
'개발 > [언어] JS' 카테고리의 다른 글
[js] jquery로 hover 상태일때 다루기 (0) | 2016.11.23 |
---|
CSS - Image 겹치기
이미지를 겹치기 위해서 Style 프로퍼티의 Position을 이해해야 한다.
position의 default 값은 static이며 이는 해당 document에 그려지는 element 순서대로 위치하게 한다.
relative는 기본 위치에서 해당 element를 이동시켜준고 td 정렬 기준으로 div 전반부를 사용한다.
absolute는 가장 가까운 곳에 위치한 조상 엘리먼트에 상대적으로 위치가 조정된다.
코드의 구조가 td > div > img 로 되있었으므로 다음과 같이 작성하면 해당 td에 들어가는 이미지에 한해서 겹쳐지게 된다.
<td>
<div style="position: relative;">
<img style="position: absolute;"/>
</div>
</td>
absolute 로 지정하면 td 정렬 기준으로 div 왼쪽 영역부터 채워지니 이점 고려해서 left, top, padding 프로퍼티 값을 부여해서 컨트롤 하면 원하는 위치로 img 태그를 놓을 수 있다.
'개발 > [언어] CSS' 카테고리의 다른 글
[생활코딩][CSS] 캐스케이딩 cascading (0) | 2016.12.06 |
---|---|
[생활코딩][CSS] 다양한 선택자들 CSS 선택자 (0) | 2016.12.05 |
[생활코딩][CSS] px vs em vs rem (0) | 2016.12.05 |
[css] 이미지에 색 필터 넣기 (0) | 2016.11.13 |
[css] input text속성 (0) | 2016.11.10 |
[안드로이드] Android Service 개념 및 사용방법 [펌]
<안드로이드 Application을 구성하는 4가지 컴포넌트>
자 그러면, Service에 대해 알아보겠습니다. 아래의 그림에서 빨간색 중요 표시가 되어 있는 컴포넌트에 대한 설명입니다.
1. Service란 무엇인가? |
Service는 안드로이드 Application을 구성하는 4가지 컴포넌트 중에 하나이며, Activity처럼 사용자와 상호작용 하는 컴포넌트가 아니고, Background(화면뒷단)에서 동작하는 컴포넌트를 말합니다.
2. Service는 왜 필요한가? |
3. Service 사용방법 |
Service의 종류에는 2가지가 있습니다. 1번째는 startService()를 이용한 방법이고, 2번째 방법은 bindService()를 이용하는 방법 입니다. 2가지의 차이점에 대해서는 나중에 얘기를 해보도록 하구요. 이번 포스팅 에서는 1번째 방법만 설명 하도록 하겠습니다.
Service 실행 : startService(Intent Serivce) 메서드 호출.
Service 중지 : stopService(Intent Serivce) 메서드 호출.
4. Service 사용시 주의사항 |
4.1. Service의 ANR 발생 |
Android는 Linux 기반의 프로그램 입니다. 프레임웍 단에는 Linux로 구현되어 있습니다. 메모리 관리 또한 Linux Kernel에서 해주게 되는데요.
하나의 프로세스를 자세히 살펴보면, 아래와 같은 구조를 가지고 있습니다.
여기서 주의 해야 할 점은, 모든 컴포넌트들이 Main Thread 안에 실행된다는 점 입니다. Main Thread는 앞서 Thread의 예제에서 살펴봤듯이, UI 작업을 처리해주는 Thread 입니다. Service 역시 Main Thread에서 관리하는 녀석이므로, Thread 작업이 필요한 경우, 작업Thread를 생성해서 관리해줘야 한다는 점 입니다.
아니면 ANR이 발생하여, 종료시켜 버리게 됩니다. 그렇기 때문에 Service사용시에도 Thread작업이 필요할 경우에는, 별도의 작업Thread를 만들어서 사용해야 합니다. 이점 유의해 주시기 바랍니다.
4.2. Service의 실행 중에 startService() 호출 |
Service 실행중에 startService() 메서드를 호출하게 되면 어떤 현상이 발생 할까요? 일반적으로 Service가 무한정 생성될거 같은데요, Service 실행도중에 startService() 메서드를 실행하게 되면 Service의 onStartCommand() 메서드를 호출 하게 합니다.
Service 주기는 onCreate() -> onStartCommand() 순으로 이뤄 지는데요, Service가 실행되고 있는 도중에 다시한번 startService() 메서드가 호출되면 onStartCommand() 주기 부터 실행하게 됩니다. 마치 Activity의 onResume() 처럼 말이죠. 그렇기 때문에 중요한 작업에 대해서는 onCreate() 보다는 onStartCommand() 메서드에 구현을 해줘야 합니다.
안드로이드 2.0 이하 버전의 Service의 주기는 onCreate() -> onStart() 구조 였지만, 2.0 이상 부터는 Service의 문제점과 기능을 보완하여 onStart()메서드 대신 onStartCommand() 메서드 사용을 권장하고 있습니다. 현재 onStart() 메서드를 사용해도 상관은 없지만 구글에서 권장하는 onStartCommand() 메서드를 사용하는게 실제 사용시 좀 더 다양한 기능을 사용 할 수 있습니다.
[기존 Service Life cycle]
[2.0 이후의 Service Life cycle]
5. Service onStartCommand() 사용방법 |
Service는 기본적으로 프로세스에 의해 종료가 되더라도 다시 살아나는 구조를 가지고 있습니다. Service의 종료메서드인 stopService() 메서드를 호출 하기 전까지는 말이죠.
프로세스에 의해 종료된 Service는 onCreate() -> onStartCommand() 순으로 주기를 타게 됩니다. startService() 메서드를 호출하지 않았기 때문에 정상적으로 동작 하는 것이지요.
onStartCommand() 메서드는 3가지 리턴 타입을 갖게 되는데요.
|
일단 기본적인 리턴방법에 대해 알아봤습니다. 그런데 보통 Service Class를 상속받고 onStartCommand() 메서드를 오버라이드 하면 아래와 같은 형태의 메서드가 기본 형태인데요. 위에서 알아본 3가지 리턴방식과는 다른 모양 입니다.
음 이건 몰까요? 이것 역시 START_STICKY 과 동일한 리턴 타입 입니다. START_STICKY 플래그(FLAG)의 값은 상수 1이고 super.onStartCommand(intent, flags, startId) 역시 상수 1을 리턴 합니다. 그렇기 때문에 START_STICKY 와 동일게 동작 합니다.
6. Service의 종류 |
Service의 종류가 2가지가 있다고 위에서 잠깐 언급했었는데요. 2가지 방식의 Service를 살펴 보자면 첫번째로 지금 까지 설명했던 1번 startService() 메서드에 의한 실행방법이 있습니다. 이 Service는 현재 실행중인 프로세스안에서의 동작을 하게 되는 Service 입니다.
이 처럼 하나의 프로세스 안에서 해당 패키지 내의 다른 컴포넌트들과의 유기적으로 통신하는 어플리케이션의 역할을 하고 있습니다.
2번째 bindService()로 실행하는 방법은
프로세스 내에서 다른컴포넌트들과 서로 유기적으로 통신을 하며, 다른 프로세스(어플리케이션)와도 Data 공유 및 통신을 하게 되는 Service를 실행하는 방법입니다.
bindService()에 관한 내용은 다음 포스팅때 설명하도록 하겠습니다.
'개발 > [앱] Android' 카테고리의 다른 글
[android] java파일에서 actionbar hide (0) | 2016.11.07 |
---|---|
[Android] Button을 처리하는3가지 방법 (0) | 2016.05.11 |
[자료구조] Select Sort
Select sort는 정렬이 되지 않은 전체 배열에서 하나를 선택하여 위치를 교환하는 정렬방법이다.
1) 7[0] 을 선택한 뒤 배열 [1]~[6] 까지 중 가장 작은 수를 선택한다. 가장 작은 수 = 1[6]
2) 가장 작은 수 1[6]과 7[0]의 자리를 swap 한다.
3) 그다음 4[1]를 선택한 뒤 배열 [2]~[6] 가장 작은 수를 선택한다. 가장 작은 수 = 2[5]
4) 끝에 도달할 때 까지 반복한다.
ex)
void sort(int *a, const int n)
{ // Sort the n integers a[0] to a[n-1] into nondecreasing order.
for (int i = 0; i < n; i++)
{
int j = i;
// find smallest integer in a[i] to a[n-1]
for (int k = i + 1; k < n; k++)
if (a[k] < a[j]) j = k;
swap(a[i], a[j]);
}
}
'개발 > 자료구조' 카테고리의 다른 글
[자료구조] c++ 스택 (0) | 2016.11.17 |
---|---|
[자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
q_sort (1) | 2016.11.16 |
Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
Binary Search 이진 탐색 (0) | 2016.10.25 |
Recursive 를 이용한 Permutation Generator (순열 생성기)
perm(a, b, c, d);
1) a + perm(b, c, d)
2) b + perm(a, c, d)
3) c + perm(a, b, d)
4) d + perm(a, b, c)
perm(b, c, d)
1) b + perm(c, d)
2) c + perm(b, d)
3) d + perm(b, c)
perm(c, d)
1) c + perm(d)
2) d + perm(c)
perm(a, 0, n) → a[0], a[1], ⋯, a[n-1]
소스 C++)
void Permutations (char *a, const int k, const int m)
{// Generate all the permutations of a[k], ..., a[m].
if (k == m) { // output permutation
for (int i = 0; i <= m; i++) cout << a[i] << “ “;
cout << endl;
}
else // a[k:m] has more than one permutation. Generate these recursively
for (int i = k; i <= m; i++) {
swap(a[k], a[i]);
Permutations(a, k+1, m);
swap(a[k], a[i]);
}
}
'개발 > 자료구조' 카테고리의 다른 글
[자료구조] c++ 스택 (0) | 2016.11.17 |
---|---|
[자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
q_sort (1) | 2016.11.16 |
[자료구조] Select Sort (0) | 2016.10.26 |
Binary Search 이진 탐색 (0) | 2016.10.25 |
Binary Search 이진 탐색
Binary Search란
< 그림으로 설명 >
[이진 탐색]
left, right: 배열(a[0], a[1], ⋯, a[n-1])의 왼쪽, 오른쪽 끝 지점
초기 값으로 left = 0, right = n-1
list의 중간 위치 middle = (left + right) / 2로 설정
a[middle]과 x를 비교할 경우 3가지 경우 중에 하나를 고려
⑴ x > a[middle]: left를 middle+1로 설정
⑵ x < a[middle]: right를 middle-1로 설정
⑶ x = a[middle]: middle을 반환
예시) C++
int BinarySearch (int *a, const int x, const int n){ // x - 찾으려는 값, n = 배열의 원소 수 or 찾으려는 배열의 크기
int left = 0, right = n -1;
// 찾거나 left가 right 넘어갈 경우 멈춘다.
while(left <= right){
int middle = (left + right) / 2; //중간위치 항상
if(x > a[middle]) left = middle + 1 ;
else if (x < a[middle]) right = middle - 1;
else return middle //찾앗다.
}
//못 찾았다.
return -1;
}
'개발 > 자료구조' 카테고리의 다른 글
[자료구조] c++ 스택 (0) | 2016.11.17 |
---|---|
[자료구조] [C++] CircularQueue 사이클 큐 (0) | 2016.11.16 |
q_sort (1) | 2016.11.16 |
[자료구조] Select Sort (0) | 2016.10.26 |
Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
[알고리즘] Graph - DFS(깊이 우선 탐색) [ 펌 - manducku]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
package Graph_07;
import java.util.*;
public class DfsTest { static int nE; static int nV; static int[][] ad; static boolean[] visit; public static void dfs(int i){ visit[i] = true; // 함수 호출 시, visit 했음을 표시
System.out.print(i+ " "); for(int j = 1; j < nV+1; j++){ if(ad[i][j] == 1 && visit[j] == false){ // j를 방문하지 않았으면 j를 방문한다.
dfs(j); } } } public static void main(String[] args) { Scanner scan = new Scanner(System.in); nV = scan.nextInt(); nE = scan.nextInt(); ad = new int[nV+1][nV+1]; // 변수 초기화
visit = new boolean[nV+1]; // 변수 초기화
for(int i = 0; i < nE; i++){ int t1 = scan.nextInt(); int t2 = scan.nextInt(); ad[t1][t2] = ad[t2][t1] = 1; } dfs(1); // 1번부터 탐색 시작
} } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
package Graph_07;
import java.util.*;
public class DfsTest02 { static int Nv; static int Ne; static boolean[] visit; static ArrayList<ArrayList<Integer>> ad; public static void dfs(int i){ visit[i] = true; System.out.print(i); for(int j : ad.get(i)){ // 배열 null check
if(visit[j] == false){ dfs(j); } } } public static void main(String[] args){ Scanner scan = new Scanner(System.in); Nv = scan.nextInt(); Ne = scan.nextInt(); ad = new ArrayList(Nv+1); // 인접 리스트 초기화
visit = new boolean[Nv+1]; // visit 배열 초기화
for(int i = 0; i < Nv+1; i++){ // 인접 리스트 속의 리스트 초기화
ad.add(new ArrayList()); } for(int i = 0; i < Ne; i++){ int t1 = scan.nextInt(); int t2 = scan.nextInt(); ad.get(t1).add(t2); ad.get(t2).add(t1); } dfs(1); } } | cs |
'개발 > 알고리즘' 카테고리의 다른 글
[알고리즘] Graph - BFS (너비 우선 탐색) [펌 - manducku] (0) | 2016.10.22 |
---|
[알고리즘] Graph - BFS (너비 우선 탐색) [펌 - manducku]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
package Graph_07;
import java.util.*;
public class BfsTest01 { static int Ne; static int Nv; static int[][] ad; static boolean[] visit; public static void bfs(int i){ Queue<Integer> q = new <Integer> LinkedList(); HashMap <Integer, Boolean> hash = new HashMap<Integer, Boolean>(); //hash Map을 이용하여 queue 입력여부 확인
q.offer(i); while(!q.isEmpty()){ int temp = q.poll(); visit[temp] = true; System.out.print(temp); for(int j =1; j <= Ne; j++){ if(ad[temp][j] == 1 && visit[j] == false){ if(!hash.containsKey(j)){ q.offer(j); hash.put(j, true); } } } } } public static void main(String[] args) { Scanner scan = new Scanner(System.in); Ne = scan.nextInt(); Nv = scan.nextInt(); ad = new int[Nv+1][Nv+1]; visit = new boolean[Nv+1]; for(int i = 0; i < Nv; i++){ int t1, t2; t1 = scan.nextInt(); t2 = scan.nextInt(); ad[t1][t2] = ad[t2][t1] = 1; } bfs(1); } } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
package Graph_07;
import java.util.*;
public class BfsTest02 { static int[][] ad; static boolean[] visit; static int Ne, Nv; public static void bfs(int i){ Queue <Integer> q = new <Integer> LinkedList(); q.offer(i); visit[i] = true; while(!q.isEmpty()){ int temp = q.poll(); System.out.print(temp); for(int j = 1; j <= Nv; j++){ if(ad[temp][j] == 1 && visit[j] == false){ q.offer(j); visit[j] = true; // 큐에 넣을 노드들을 잠재적으로 방문한다는 가정하에 입력
} } } } public static void main(String[] args){ Scanner scan = new Scanner(System.in); Nv = scan.nextInt(); Ne = scan.nextInt(); ad = new int[Nv+1][Nv+1]; visit = new boolean[Nv+1]; for(int i = 0; i < Ne; i++){ int t1, t2; t1 = scan.nextInt(); t2 = scan.nextInt(); ad[t1][t2] = ad[t2][t1] = 1; } bfs(1); } } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
package Graph_07;
import java.util.*;
public class Bfs03 { static ArrayList<ArrayList<Integer>> ad; static boolean[] visit; static int Ne, Nv; public static void bfs(int i){ Queue <Integer>q = new <Integer> LinkedList(); HashMap<Integer, Boolean> hash = new HashMap<Integer, Boolean>(); q.offer(i); while(!q.isEmpty()){ int temp = q.poll(); visit[temp] = true; System.out.print(temp); for(int j : ad.get(temp)){ if(visit[j] == false && !hash.containsKey(j)){ q.offer(j); hash.put(j, true); } } } } public static void main(String[] args) { Scanner scan = new Scanner(System.in); Nv = scan.nextInt(); Ne = scan.nextInt(); ad = new <ArrayList<Integer>> ArrayList(Nv+1); visit = new boolean[Nv+1]; for(int i = 0; i <= Nv+1; i++){ ad.add(new ArrayList()); } for(int i = 0; i < Ne; i++){ int t1, t2; t1 = scan.nextInt(); t2 = scan.nextInt(); ad.get(t1).add(t2); ad.get(t2).add(t1); } bfs(1); } } | cs |
'개발 > 알고리즘' 카테고리의 다른 글
[알고리즘] Graph - DFS(깊이 우선 탐색) [ 펌 - manducku] (0) | 2016.10.22 |
---|