백준56 [백준 11659] 알고리즘 62일차 : 구간 합 구하기4 www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net C++ 누적합 문제 처음 보면 엥 이게 왜 실버3이지 싶은데 풀고나면 아ㅇㅇ 그냥 수배열 주고 일정 구간 수의 합 구하는건데 시간복잡도 때문에 그냥 합하는 식으로 구하면 시간초과나고 누적합.. 아 이 문제 분류가 누적합이구나.. 입력받을때 누적합을 같이 구해서 구간 합 구할때는 sum[end] - sum[start] (단, start != 1) 로 구해야 함 근데도 시간초과 나서 sync.. 2021. 1. 11. [백준 2512] 알고리즘 61일차 : 예산 www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net C++ 이분탐색 연초에 시기적절한 문제인 것 같아서 풀어봤다(변명) 이분탐색은 진짜 한번 풀면 계속 풀 수 있을 것 같다(그러면서 왜 골드는 안푸는데요) 아무튼. 접근방법 지방의 예산요청액 입력받을때 합이랑 최댓값 같이 구해놓고 합이 전체 국가 예산보다 작으면 최댓값 출력하고 끝. 아니면 이분탐색 함수 부를때 (1,최댓값)으로 범위설정해서 보내고 이분탐색 기준 함수는 지방 예산요청액 배열 다 돌면서 상한액.. 2021. 1. 8. [백준 12865] 알고리즘 53일차 : 평범한 배낭 (C++, Swift) 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 문제를 정석으로 코드를 짜보려고이 문제를 골랐다. 접근방법상향식 접근, 최적의 원리 등의 접근으로 풀이하는 대표적인 DP문제 중.. 2020. 8. 28. [백준 4949] 알고리즘 38일차 : 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단 www.acmicpc.net 스택 C++ (2011 ICPC japan) 괄호가 섞인 문자열이 주어지고 괄호가 균형이 맞는지 조사하는 문제 (, [ 가 입력되면 stack에 push하고 ), ]가 입력되면 stack에서 pop한 값이 짝이 맞는지 검사한다. 이때 짝이 맞지 않으면 균형잡힌 문자열이 아닌걸로 판단하고 결과를 출력하고 또 마지막에 stack이 비어있지 않으면 균형잡힌 문자열이 아닌걸로 판단하고 출력한다. 소스코드.. 2020. 8. 6. [백준 10773] 알고리즘 36일차 : 제로 https://www.acmicpc.net/problem/10773 10773번: 제로 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 �� www.acmicpc.net 스택 C++ 숫자를 입력받아 스택에 쌓다가 0을 입력받으면 pop하고 마지막에 스택에 쌓여있는 수의 합을 구하는 문제 스택 문제가 대체로 평이한 것 같다. 소스코드 #include using namespace std; class Stack{ public: int size; int* stack; Stack(int maxSize){ size = 0; stack = new int[maxSize]; } void .. 2020. 8. 3. [백준 11051] 알고리즘 35일차 : 이항 계수 2 https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 수학3, 동적계획법 C++ 이항계수를 동적계획법으로 푸는 문제 (간략) 작년 알고리즘 수업에서 배우고 또 비슷한 손코딩 문제가 시험에도 나왔었던 문제 이항계수였는지는 기억안남 DP에서 피보나치와 함께 배운 기억이 난다. 두 문제 모두 재귀를 배울때 나오는 개념들이지만 사실 시간복잡도면에서 보면 배열을 사용해서 반복문을 쓰는게 훨씬 효율적이다. (이걸 동적계획법 부분에서 배움 매번 이런식이지 비효율적인거 실컷 가르쳐놓고 효율적인 방법 나중에 알려주기 교수님 : 하지만 .. 2020. 7. 31. [백준 1312] 알고리즘 33일차 : 소수 https://www.acmicpc.net/problem/1312 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 수학 C++ 정수를 나눈 결과의 소숫점 백만자리까지 출력할 수 있어야 한다. double, float자료형 모두 백만자리까지의 소수점을 저장하지는 않으므로 나눗셈을 반복문으로 구현해서 값을 출력해야한다. 접근방법은 정수의 나눗셈을 반복문을 이용해서 구현하는 것 A/B라면 A를 B로 나눈 나머지에 10을 곱한다. 그 과정을 N만큼 반복한 뒤 마지막에 A를 B로 나눈 값을 출력하면 끝 소스코드 #.. 2020. 7. 29. [백준 3036] 알고리즘 32일차 : 링 https://www.acmicpc.net/problem/3036 3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 수학3 C++ 풀다가 느낀건데 수학으로 분류되는 문제는 지금의 나보다 고3의 내가 더 잘풀 것 같다. 첫번째 링을 한 바퀴 돌렸을 때 인접한 링이 도는 횟수는 첫번째 링의 둘레/인접한 링의 둘레이다. 결국 그냥 반지름의 비이다. R1/R2 구하는거라 뭐지 왜 실버3이지 했는데 문제가 의도한건 약분이었다. 약분은 두 수의 최대 공약수로 두 수를 나눈 값을 출력하는 방법으로 구현했다. 접근 방법 요약 인접하는 .. 2020. 7. 28. [백준 14888] 알고리즘 20일차 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 백트래킹 C++ 삼성 SW 역량 테스트 기출 문제 1 문제 순서가 정해진 피연산자들이 주어지고 +,-,x,÷ 의 개수가 입력된다. 그럼 연산자들의 순서를 바꿔가며 계산한 값의 최댓값과 최솟값을 출력하는 문제이다. 접근방법 순서가 다르게 연산자들을 나열한다. N과 M(1)의 코드를 재사용했다. 그 결과 연산자들의 순서가 다른 모든 경우의 .. 2020. 7. 10. 이전 1 ··· 3 4 5 6 7 다음
