일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 5525
- 주식 가격
- colorSyntax
- 1620
- Git Convention
- 숫자 문자열과 영단어
- 소수 체크
- n^2 배열 자르기
- javascript
- 프로그래머스
- BOJ
- 구간 합 구하기 4
- C++
- 다이내믹 프로그래밍
- 2018 KAKAO BLIND RECRUITMENT
- Hasing
- 없는 숫자 더하기
- 위클리 챌린지
- 4796
- 옵셔널 체이닝 연산자
- react
- codeSyntaxHighlight
- 브루트포스 알고리즘
- js
- 10162
- 이분탐색
- 정수 삼각형
- 18111
- mermaid js
- 깊이 우선 탐색
- Today
- Total
목록Algorithm/BOJ (49)
개발하는 kim-hasa
https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 물건을 사고 남은 거스름돈의 최소 갯수를 구하는 문제입니다. 가장 큰 돈부터 거스름돈을 주고, 점점 금액을 줄여가는 식으로 구하면 됩니다. #include using namespace std; int main(){ int coin; cin >> coin; coin = 1000 - coin; int count = 0; while(coin > 0){ if(coin >= 500) ..
https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 두 배열의 원소의 곱을 최소로 만들면 된다. 두 배열을 모두 정렬한 후, a의 최소값 * b의 최대값을 곱하는 방식으로 구했다. 실제 문제 조건에서는 a는 재배열하면 안된다고 했는데, 그 경우를 찾아서 풀어봐야겠다. #include #include #include using namespace std; int main(){ int n; cin >> n; vector arrA; for(int ..
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디를 적용시키는 문제입니다. 뭐로 그리디를 적용시킬까 고민하다가 종료시간을 기점으로 그리디를 시키면 된다는 것을 알았습니다. 종료시간을 기준으로 pair함수를 이용해서 정렬시킵니다. 그 이후 빨리 시작하는 것부터 시작을 한 후 종료시간을 저장시킵니다. 종료시간 이후로 혹은 같은 시간에 시작하는 것 중 짧은 종료시간을 가진 것을 찾습니다. 이런식으로 이어가면서 개수를 카운트하면 끝 ! #include #include #include using namespace std; int main(){ int n; cin ..
https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 그리디 알고리즘을 이용한 문제입니다. 연속된 P일 동안 최대 L 일이므로, 전체 기간을 P로 나누게 되면 그 횟수가 나오는데, 횟수당 최대 L일 이므로 L을 곱해서 더해줍니다. 그 다음 나머지가 L보다 크다면 L을 더하고, 그렇지 않다면 남은 일수만 더합니다. #include using namespace std; int main(){ int L,P,V; int count = 1; while(..
https://acmicpc.net/proble64 듣도 못한 사람과 보도 못한 사람의 입력을 받아서 둘 다 속해있는 사람을 구하는 문제입니다. 먼저 듣도 못한 사람의 이름을 배열에 넣고, 보도 못한 사람의 이름이 들어올 때 마다 찾아서 같은게 있다면 정답 배열에 넣고 카운트를 증가시킵니다. 이 때, 이진 탐색을 이용해서 시간을 줄입니다. #include #include #include using namespace std; vector name; vector emeqh; int ncount = 0; void binary(int start, int end, string find){ int mid = (start + end) / 2; if(start > end) return ; if(name[mid] == ..
https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 산술 평균, 중앙값, 최빈값, 범위를 구하는 문제입니다. 최빈값 조건 중 같은게 있을 경우 두번째로 작은 값을 구하는 문제가 있어서 힘들었던 문제입니다. 두번째 것을 저장시켜두고 출력하면 되는 문제였습니다. #include #include #include #include using namespace std; vector arr; int main() { int n; cin >> n; int sum = 0; int..
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 주어지는 숫자를 정렬하는 문제입니다. 가장 먼저 풀었을 때는 머지소트를 시도했고, 그 다음에는 퀵소트를 시도했는데 둘다 메모리 초과가 떠서 검색해보던 와중 숫자의 최대치가 10000이라는 점을 이용해서 구하는 방법이 있어 그 방법으로 구현했습니다. 최대 숫자의 개수가 10000000개라서 이 방법으로 푸는게 맞는거 같습니다. 숫자가 나올때마다 카운트를 해서 마지막에 카운트 개수만큼 그 index를 출력하면 됩니다. ..
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 저장된 사이트의 비밀번호를 찾는 문제입니다. 가장 먼저 pair 함수를 이용해서 사이트와 비밀번호를 저장합니다. 그 이후 사이트를 받아와서 저장된 벡터의 first를 비교후, 같다면 second를 출력하는 방법입니다. 다만, 이 방법에서 그냥 순차 검색을 이용할 경우 시간초과가 나기 때문에 이진검색으로 나누어서 풀었습니다. 어차피 string sort시 알파벳 순서대..
https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net n개의 숫자가 주어지고 특정 두 수 사이의 합을 구하는 문제입니다. 앞에서부터 하나씩 더해서 누적합을 쌓아갑니다. 그 후에 두 수의 차이를 구하면 그 사이의 합이 구해집니다. #include using namespace std; int arr[100001]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,m; ci..
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 삼각형을 추가해서 그 삼각형의 변의 길이를 구하는 문제입니다. 123 번째는 1, 45 번째는 2의 크기를 가지고 있고, 그 이후부터는 arr[i] = arr[i-1] + arr[i-5] 가 성립합니다. 미리 배열을 다 만들어 놓은 후, 수가 입력될 때 마다 그 위치의 원소를 꺼내서 출력합니다. #include using namespace std; int main(){ int n; cin >> n; l..