죠노이 노트

q_sort

개발/자료구조2016. 11. 16. 16:44
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
//q_sort
 
#include <iostream>
 
 
 
void qsort(int num[], int left, int right) {
 
    int pivot = num[(left+right) / 2]; //중앙 값
    int l = left;
    int r = right;
 
    while (l < r) {
        while (pivot > num[l])
            l++;
 
        while (pivot < num[r])
            r--;
 
        if (l <= r) {
 
            int ch = num[l];
            num[l] = num[r];
            num[r] = ch;
            l++; r--;
        }
    }
 
    if (left < r) qsort(num, left, r);
    if (right > l) qsort(num, l, right);
 
}
 
int main(void) {
 
    int n[8] = { 67, 90, 57, 25, 84, 32, 73, 54 };
    qsort(n, 0, 7);
    for (int i = 0; i < 8; i++) {
        std::cout << n[i] << " ";
    }
    std::cout << std::endl;
    return -1;
}
 
 

cs


'개발 > 자료구조' 카테고리의 다른 글

[자료구조] c++ 스택  (0) 2016.11.17
[자료구조] [C++] CircularQueue 사이클 큐  (0) 2016.11.16
[자료구조] Select Sort  (0) 2016.10.26
Recursive 를 이용한 Permutation Generator (순열 생성기)  (0) 2016.10.25
Binary Search 이진 탐색  (0) 2016.10.25

[백준] [DP] 10942번 팰린드롬? 문제

개발/백준_알고리즘2016. 11. 14. 22:55




문제


https://www.acmicpc.net/problem/10942





팰린드롬? 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초256 MB299585856632.907%

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

  • S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
  • S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
  • S = 3, E = 3인 경우 1은 팰린드롬이다.
  • S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

예제 입력 

7
1 2 1 3 1 2 1
4
1 3
2 5
3 3
5 7

예제 출력 

1
0
1
1






















 

코드 설명)


1) num[] 자연수 N

2) ppap[s][e] s~e 사이가 펠린드롬이면 1 아니면 0


(1)처음에  ppap[0][0], [0][1], [1][0], [1][1] 1로 초기화

그리고 자기 자신은 [1][1], [2][2], ~ ... 펠린드롬이니 1로 초기화

ppap[i+1][i] = 1 로 초기화 해주는 이유는 예를 들어 num[1] =1, num[2] =1, num[3] =1 일때 [1] == [2] 같을때 비교문이 ppap[2][1] 을 가르키게 된다 ([2]==[3] 일경우 [3][2]를 가르킴) 그렇기 때문에 초기값을 1로 넣어줘야한다.  

* 제 소스만 해당하는 특별한 경우입니다 :(...  


(2) for문에서 ( for(int i = 1; i <= n - 1; i++) ) i는 거리를 나타냅니다.

예를 들어 12321 이있다고 하면

예) [1][2][3][2][1] 에서 i가 1일 경우 [1][2][3][2][1], [1][2][3][2][1], [1][2][3][2][1] ... 이고

i가 2일 경우 [1][2][3][2][1], [1][2][3][2][1], [1][2][3][2][1]

배열 사이의 거리를 의미한다고 생각하시면 됩니다.


다음 for문(for(int j = 1; j <= n - i; j++))는 배열 값의 최대를 넘지 않고 비교 하기 위한 위치를 나타내는 포문 입니다.

예를 들어 위의 예시 i 가 1일 때 [1][2][3][2][1], [1][2][3][2][1], [1][2][3][2][1] ...

파란색을 의미 하는 포문 입니다.


if문은 가르키는 위치가 서로 같은지 비교를 해주고 그 사이 값이 팰린드롬 인지 확인합니다.


이해하면 생각보다 쉬운데 소스가 생각보다 깔끔히 짜진 못했네요..



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
#include <iostream>
#include <cstdio>
 
int num[2001];
int ppap[2002][2002];
 
int main(){
    
    int n;
    // std::cin >> n;
    scanf("%d", &n);
 
    for(int i = 1 ; i <= n ; i++)
        scanf("%d", &num[i]);
        // std::cin >> num[i];
 
 
    int n2;
    scanf("%d", &n2);
    // std::cin >> n2;
 
    //init
    ppap[0][0] = 1;
    ppap[0][1] = 1;
    ppap[1][0] = 1;
 
    for(int i = 1; i <= n ; i++){
        ppap[i][i] = 1;    // self
        ppap[i+1][i] = 1;        // for the 1 block can be "1" ex) 1~2, 2~3
    }
 
    // distance
    for(int i = 1; i <= n - 1; i++)
        for(int j = 1; j <= n - i; j++)
            if( num[j] == num[j + i] && ppap[j + 1][j + i - 1] == 1)
                ppap[j][j+i] = 1;
 
    while (n2--){
        int S, E;
        scanf("%d %d", &S, &E);
        printf("%d\n", ppap[S][E]);
 
        // cin 으로 하면 시간 초과
        // int S, E;
        // std::cin >> S >> E;
        // std::cout << ppap[S][E] << std::endl;
    }
 
    return -1;
}
cs


'개발 > 백준_알고리즘' 카테고리의 다른 글

[백준] [DP] 2293번 동전 1  (1) 2016.11.16
[백준] 1254번 팰린드롬 만들기  (0) 2016.11.13
[백준][DP] 2294번 : 동전 2 문제  (0) 2016.11.08

[c++] swap 함수

개발/[언어] C++2016. 11. 14. 11:43 

swap 함수에 대해!


char &a에서 &는 참조자인데 만약 swap(str1, str2) 를 했다고 보면

str1 라는 변수의 주소에 &a 라는 참조자가 붙게 되어 값을 변경시 str1 값도 같이 변하게 된다. 


1
2
3
4
5
6
void swap(char &a, char &b){
    char c;
    c = a;
    a = b;
    b = c;
}
cs


[css] 이미지에 색 필터 넣기

개발/[언어] CSS2016. 11. 13. 13:17

<div class="container-fulid" style="margin-top:50px; position:relative">

      <div style="position:absolute; background-color:rgba(0, 0, 0, 0.65); z-index:10; height:100%; width:100% "></div>

      <img src="b1.jpg" width="100%" alt="배경1" style="position:relative; z-index:1">

    </div>


필터의 부모 클래스에 position : relative 를 사용하고

필터값을 position:absolute; height: 100% ; width 100%해주고 원하는 색상(background-color)과 z-index값을 설정 뒤

이미지 z-index를 필터보다 작게 작아주면된다.

'개발 > [언어] CSS' 카테고리의 다른 글

[생활코딩][CSS] 캐스케이딩 cascading  (0) 2016.12.06
[생활코딩][CSS] 다양한 선택자들 CSS 선택자  (0) 2016.12.05
[생활코딩][CSS] px vs em vs rem  (0) 2016.12.05
[css] input text속성  (0) 2016.11.10
CSS - Image 겹치기  (0) 2016.10.31

[백준] 1254번 팰린드롬 만들기

개발/백준_알고리즘2016. 11. 13. 11:19

https://www.acmicpc.net/problem/1254

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
#include<iostream>
int main(){
    std::string str;
    std::cin >> str;
    int str_len = str.length();
    int left, right;
    int num_other = 0; // 왼쪽 부터 비교 다르면 추가해야할 문자 수
    
    for(int i = 0 ; i < str_len - 1; i++){
        // i = 비교해야할 left / str_len - i = 제일 오른쪽 
        if(str[i] == str[str_len - 1]){ // 같다면 안에서 left 와 right 안쪽으로 들어오며 비교
            left = i; right= str_len - 1;
            for(int j = 0; j < (str_len - i) / 2 ; j++){
                if(str[left] == str[right]){
                    left++; right--;
                }
                else{  //다를 경우 추가해야할 문자수 ++ / 멈춤
                    num_other++;
                    break;
                }
                if(left > right || left == right){  // 다 도달했다는 뜻 i 값에 마지막 인덱스를 넣어주어 스탑
                    i = str_len - 1;
                    break;
                }
            }
        }
        else num_other++;
    }
    std::cout << str_len + num_other << std::endl;
    return -1;
}


'개발 > 백준_알고리즘' 카테고리의 다른 글

[백준] [DP] 2293번 동전 1  (1) 2016.11.16
[백준] [DP] 10942번 팰린드롬? 문제  (0) 2016.11.14
[백준][DP] 2294번 : 동전 2 문제  (0) 2016.11.08

[부트스트랩] datetimepicker, selectpicker 사이트

개발/[웹프론트] 부트스트랩(bootstrap)2016. 11. 10. 23:39




부트스트랩3 datetimepicker : http://eonasdan.github.io/bootstrap-datetimepicker/Functions/



부트스트랩3 Select : https://silviomoreto.github.io/bootstrap-select/

'개발 > [웹프론트] 부트스트랩(bootstrap)' 카테고리의 다른 글

부트스트랩 navbar 가운데 로고 넣기  (0) 2016.10.21
carousel의 carousel-inner 검정 배경 전체로 채우기  (0) 2016.10.21
부트스트랩 가운데 정렬  (0) 2016.10.13
부트 스트랩 공부하면서 정리한 것 (w3school)  (1) 2016.10.03

[css] input text속성

개발/[언어] CSS2016. 11. 10. 21:52 
width: 100%;  /* 원하는 너비 설정 */ 
  height: auto;  /* 높이값 초기화 */
  line-height : normal;  /* line-height 초기화 */
  padding: .8em .5em; /* 원하는 여백 설정, 상하단 여백으로 높이를 조절 */
  font-family: inherit;  /* 폰트 상속 */
  border: 1px solid #999;
  border-radius: 0;  /* iSO 둥근모서리 제거 */
  outline-style: none;  /* 포커스시 발생하는 효과 제거를 원한다면 */
  -webkit-appearance: none;  /* 브라우저별 기본 스타일링 제거 */
  -moz-appearance: none;
  appearance: none;


'개발 > [언어] 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 - Image 겹치기  (0) 2016.10.31

[백준][DP] 2294번 : 동전 2 문제

개발/백준_알고리즘2016. 11. 8. 23:20




동전 2 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초128 MB87812028136124.629%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. (각각의 동전은 몇개라도 사용할 수 있다.)

입력

첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.

출력

첫째줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

예제 입력 

3 15
1
5
12

예제 출력 

3

힌트

출처

  • 잘못된 조건을 찾은 사람: apples1309
  • 데이터를 추가한 사람: isac322

알고리즘 분류




소스)
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
  
#include<iostream>
 
 
int main() {
 
    //input coin_num 코인의 수, coin_total 구하려는 코인 값
 
    int coin_num;
    int coin_total;
 
    //코인
    int coins[100];
    
 
    //각 코인의 횟수 
    int min_coins_num[10001];
 
    std::cin >> coin_num >> coin_total;
    
    for (int i = 0; i < coin_num; i++) {
        std::cin >> coins[i];
    }
 
    min_coins_num[0] = 0;
 
    // 첫번째 코인부터 구하려는 코인값까지 dp
    for (int i = 1; i <= coin_total; i++) {
        
        int min = 10001; // 최대 나올수 있는 최악의 코인의 수는 10000
        for (int j = 0; j < coin_num; j++) {
            if (i - coins[j] < 0) continue;        // 음수 일 경우 계산 될 수 없는 부분이다.
            else{
                if (min_coins_num[i - coins[j]] < 0) continue;    // 전 코인을 참조 할 때 -1 이 있으면 그 수는 계산 불가능이다.
                if (min_coins_num[i - coins[j]] + 1 < min) {    // 가능할경우 최소의 수 비교
                    min = min_coins_num[i - coins[j]] + 1;
                }
            }
        }
        if(min < 10001)
            min_coins_num[i] = min;
        else
            min_coins_num[i] = -1;    //불가할경우 -1 
    }
 
    std::cout << min_coins_num[coin_total] << std::endl;
    return -1;
}
cs












 


'개발 > 백준_알고리즘' 카테고리의 다른 글

[백준] [DP] 2293번 동전 1  (1) 2016.11.16
[백준] [DP] 10942번 팰린드롬? 문제  (0) 2016.11.14
[백준] 1254번 팰린드롬 만들기  (0) 2016.11.13

[android] java파일에서 actionbar hide

개발/[앱] Android2016. 11. 7. 17:26

Oncreate 에 추가 해주면 됩니다.


ActionBar actionbar = getSupportActionBar(); actionbar.hide();


'개발 > [앱] Android' 카테고리의 다른 글

[안드로이드] Android Service 개념 및 사용방법 [펌]  (0) 2016.10.26
[Android] Button을 처리하는3가지 방법  (0) 2016.05.11

[js] HTML에서 JavaScript 로드하기

개발/[언어] JS2016. 11. 5. 17:42

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

티스토리툴바