www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net C++ 이분탐색 쉬운 이분탐색 응용없이 그냥 이분탐색만 하면 되는 문제 이건..실버4이기엔 쉬운 문제인 것 같다. 접근방법 상근이가 갖고 있는 숫자카드는 배열로 받아서 정렬해주고 주어지는 정수 M은 바로 받아서 이분탐색하는 것 끝 오답노트 내가 코드를 잘 못짜서 그런건지는 모르겠지만 일단 기본 코드는 시간초과 났었고 sync_with_stdio 해주고 cin tie해주니까 통과됐다..
www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net C++ 이분탐색 지금까지 풀었던 이분탐색 문제랑 비슷한 문젠데 난이도가 조금 높은건 기준정하는 함수에 필요한 계산이 좀 많아서 때문인 것 같다. 접근방법 간격을 1부터 가장 좌표값이 큰 값을 범위로 이분탐색한다. 집 좌표값 배열은 정렬해둔다. 간격이 mid일때 공유기를 설치할 수 있는 개수가 C개 이상이면 더 큰 간격에서 이분탐색 C개 미만이면 더 좁은 간격에..
www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net C++ 정수론 및 조합론 양아치 같지만 정수론 및 조합론에 문제가 추가돼있어서.. 공유기설치하다가 넘어왔습니다.. 접근방법 유클리드 호제법으로 풀이한 최소공배수 - 유클리드 호제법 : A에는 B를 대입하고, B에는 A%B를 대입하면서 A%B가 0이 될때 B의 값이 최대공약수이다. - 최소 공배수 = 두수의 곱 / 최대공약수 이 두가지를 적용해서 푼 코드 소스코드 #include using n..
www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 www.acmicpc.net 이분탐색 C++ 오늘도 이분탐색으로 최댓값을 구하는 스킬을 사용하는 문제 그래서 저번 랜선자르기 코드 거의 그대로 씀 접근방법 H의 길이를 0부터 가장 높은 나무길이 범위내에서 이분탐색하여 최댓값을 구한다. 오답노트 자른 나무의 길이 합과 M이랑 비교하는 함수에서 합 계산할때 음수도 같이 더하는걸로 해버려서 오류났었다. 양수일때만 더하는걸로 고치고 통과 소스코드 #incl..
www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이분 탐색 C++ 문제 보고 어디에 이분탐색을 써야하는지 고민했던 문제 힌트로 parametric search 라고 돼있어서 개념 찾아봤는데 별 도움은 안됐음.. 1부터 max 길이 까지를 범위로 두고 그 안에서 랜선 길이를 이분 탐색하면서 찾아가는 거였다. 처음엔 랜선 개수를 계산하는게 시간이 오래걸릴 것 같아서 그걸 이분 탐색으로 대체해야하나 싶었는데 그 부분은 그냥 계산돌려도 ..
www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분탐색 C++ 입력받은 숫자배열에 또 다른 배열에 주어진 숫자들이 몇개씩 포함되어있는지 출력하는 문제 (이과생의 글솜씨 ㅈㅅ) 숫자를 찾은 후에 숫자 개수를 하나씩 세어나가면 안된다. 이유는 모두 같은 수 일때는 결국 전체탐색을 하게 되기 때문. 그래서 lower_bound랑 upper_bound를 구해서 풀어야 하는 문젠데 구현 다 했는데 계속 시간초과 나서 찾아보니까 ST..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 동적계획법 C++ 2020 하계 방학 알고리즘 스터디의 마지막을 장식할 DP 문제 knapsack 문제다!!! 문제는 설명하기 입아프니 위 사진을 참고하도록 하시고 이번 여름방학 스터디 마지막 문제로 knapsack 문제를 정석으로 코드를 짜보려고 이 문제를 골랐다. 접근방법 상향식 접근, 최적의 원리 등의 접근으로 풀이하는 대표적..
https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 동적계획법 C++ 오르막수 구하기 문제 접근 방법 자리수 별로 오르막수를 저장하는 배열을 사용한다. 소스코드 #include using namespace std; int main(){ int n; cin >> n; int dp[1000][10]={0}; for(int i = 0 ; i < 10 ; i++) dp[0][i] = 1; for(int i = 1 ; ..
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 동적계획법 C++ 가장 긴 바이토닉 부분 수열 문제 접근 방법 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열이 중첩된 문제 0부터 i 까지의 가장 긴 증가하는 부분 수열을 구하고, i 부터 n까지 감소하는 부분 수열을 구하여 합한 값으로 구한다. 증가하는 부분 수열은 차이가 없지만, 감소하는 부분 수열은 원래는 i까지 감소하는 부분수열을 구했었는데 여기선 i부터 n까지 감소하는 부분 수열을 구한다는 점이..
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 동적계획법 C++ n이 1,2,3의 합으로 구성되는 경우의 수를 구하는 문제 (조합아님) 접근 방법 n을 1,2,3의 합으로 나타내는 경우의 수는 ( n-1의 경우 + n-2의 경우 + n-3의 경우) 이다. 순서가 상관있는 문제기때문에 n-1의 경우에 +1 을 한 경우들, n-2의 경우에 +2를 한 경우들, n-3의 경우에 ..
- Total
- Today
- Yesterday
- 투포인터
- 자바
- 스택
- 최단경로
- c++
- 브루트포스
- 우선순위큐
- 정렬
- 가장 큰 수 프로그래머스
- dfs
- 백트래킹
- 알고리즘
- 그리디알고리즘
- 가장 큰 수 Swift
- 백준
- 최소힙
- 이분탐색
- Swift
- 다이나믹프로그래밍
- BFS
- 웹크롤링
- 최대힙
- 수학
- 트리
- 프로그래머스
- 파이썬
- dp
- 게임이론
- 토마토
- 동적계획법
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |