[백준] [이분 탐색] 1920번 수 찾기
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 62 63 64 65 66 67 68 | #include <iostream> #include <cstdio> void q_sort(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 c = num[l]; num[l] = num[r]; num[r] = c; l++; r--; } } if (left < r) q_sort(num, left, r); if (right > l) q_sort(num, l, right); } int bsearch(int num[], int size, int want) { int left = 0, right = size - 1; while (left <= right) { int middle = (left + right) / 2; if (num[middle] == want) return 1; else if (num[middle] <= want) { left = middle + 1; } else { right = middle - 1; } } return 0; } int main(void) { int n1, n2; int num[100001]; scanf("%d", &n1); for (int i = 0; i < n1; i++) scanf("%d", &num[i]); q_sort(num, 0, n1 - 1); scanf("%d", &n2); for (int i = 0; i < n2; i++) { int result; scanf("%d", &result); printf("%d\n", bsearch(num, n1, result)); } return -1; } | cs |
[백준] [DP] 2293번 동전 1
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 | #include <iostream> #include <cstdio> int coin_case[10001]; int main(void){ int n, money; int coin[101]; scanf("%d %d", &n, &money); for(int i = 1 ; i <= n ; i++) scanf("%d", &coin[i]); coin_case[0] = 1; for(int i = 1; i <= n ; i++){ for(int j = 1 ; j <= money; j++){ if( coin[i] <= j ) coin_case[j] += coin_case[j - coin[i]]; } } std::cout << coin_case[money] <<std::endl; return -1; } | cs |
'개발 > 백준_알고리즘' 카테고리의 다른 글
[백준] [DP] 10942번 팰린드롬? 문제 (0) | 2016.11.14 |
---|---|
[백준] 1254번 팰린드롬 만들기 (0) | 2016.11.13 |
[백준][DP] 2294번 : 동전 2 문제 (0) | 2016.11.08 |
[자료구조] [C++] CircularQueue 사이클 큐
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<string> typedef struct Node { std::string data; }Node; class cir_queue { private: Node* node; int size; int front; int back; public: cir_queue(int size) { this->size = size + 1; //더미 공간 node = new Node[this->size]; front = 0; back = 0; } void enqueue(std::string data) { int index; if (back == size - 1){ index = back; back = 0; } else { index = back++; } node[index].data = data; } std::string dequeue() { int index = front; if (front == size - 1) front = 0; else front++; return node[index].data; } int get_size() { if (front <= back) return back - front; else return size - front + back; } }; | cs |
'개발 > 자료구조' 카테고리의 다른 글
[자료구조] c++ 스택 (0) | 2016.11.17 |
---|---|
q_sort (1) | 2016.11.16 |
[자료구조] Select Sort (0) | 2016.10.26 |
Recursive 를 이용한 Permutation Generator (순열 생성기) (0) | 2016.10.25 |
Binary Search 이진 탐색 (0) | 2016.10.25 |
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; } |
'개발 > 자료구조' 카테고리의 다른 글
[자료구조] 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번 팰린드롬? 문제
문제
https://www.acmicpc.net/problem/10942
팰린드롬? 성공
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 2995 | 858 | 566 | 32.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 함수
swap 함수에 대해!char &a에서 &는 참조자인데 만약 swap(str1, str2) 를 했다고 보면str1 라는 변수의 주소에 &a 라는 참조자가 붙게 되어 값을 변경시 str1 값도 같이 변하게 된다.
123456 void swap(char &a, char &b){char c;c = a;a = b;b = c;}cs
[css] 이미지에 색 필터 넣기
<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번 팰린드롬 만들기
'개발 > 백준_알고리즘' 카테고리의 다른 글
[백준] [DP] 2293번 동전 1 (1) | 2016.11.16 |
---|---|
[백준] [DP] 10942번 팰린드롬? 문제 (0) | 2016.11.14 |
[백준][DP] 2294번 : 동전 2 문제 (0) | 2016.11.08 |
[부트스트랩] datetimepicker, selectpicker 사이트
부트스트랩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속성
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 |