⭐️ 난이도 Silver 2 ⭐️ 문제 https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net ⭐️ Idea flow 문제를 간단하게 정리해보자. 1. 징검다리는 1번부터 n번까지 있다. 2. 현재 칸에서 각 징검 다리에 쓰여 있는 숫자의 배수만큼 떨어진 곳에만 갈 수 있다. 3. a번 다리에서 b번 다리로 이동하려고 할 때, 최소 이동 횟수는 몇 번인지 구하시오. 시작점과 도착점이 주어지고, 시작점에서 도착점까지 이동하는 최소 이동 횟수..
C++
⭐️ 난이도 Silver 2 ⭐️ 문제 https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net ⭐️ Idea flow 문제를 간단하게 정리해보자. 자연수 x가 주어졌을 때, x의 약수들을 모두 더한 값을 f(x)라고 하자. 자연수 n이 주어졌을 때, n보다 작거나 같은 모든 자연수들의 f(n)의 합을 g(n)이라고 하자. g(n)을 구하라. [시간 초과난 알고리즘] 처음에는 1부터 n까지 fo..
⭐️ 난이도 Gold 5 ⭐️ 문제 https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net ⭐️ Idea flow 이 문제의 내용을 정리해보자. 사칙연산만을 최소한으로 이용해서 s를 t로 바꾸려고 한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력하라. (사칙연산의 사전 순은 다음과 같다. * + - /) s == t라면 0을, s를 t로 바꿀 수 없다면 -1을 출력하라. 연산할 수 있는 방법이 4가지로 정해져 있는데, 이를 최..
저번 게시글에서는 이분 탐색(Binary Search)에 대해서 알아보았다. (https://m42-orion.tistory.com/69) 이번 게시글에서는 전에 이야기 했던 것처럼 매개 변수 탐색(Parametric search)에 대해 알아보고자 한다. ⭐️ 매개 변수 탐색(Parametric Search) 이란? - 이진 탐색(Binary search)와 상당히 유사한 알고리즘 - Nimrod Megido에 의해 발명되었으며, 최적화 문제를 "결정 문제"로 풀 수 있는 알고리즘 - 시간 복잡도(Time complexity): O(log N) ⭐️ 매개 변수 탐색(Parametric Search)을 사용하는 시기 1. 결정 문제로 풀면 쉽게 문제를 풀 수 있을 때 2-1. 어떤 시점까지는 조건을 만족..
⭐️ 이분 탐색(Binary search)이란? - 정렬된 리스트(배열)에서 원하는 값(target)의 존재 여부(존재 위치)를 찾는 알고리즘. - 반드시 리스트(배열)를 정렬해서 사용해야 한다는 단점이 있다. - 탐색할 때마다 검사 범위가 절반으로 줄어든다. - 재귀적인 방법, 반복문, STL를 이용하여 이분 탐색(Binary Search)을 실행할 수 있다. - Time Complexity : O(log N) ⭐️ 변수 설명 1. int low & int high 검사 범위의 시작점, 끝점의 인덱스를 가리키기 위한 변수. left는 시작점을, right를 끝점의 인덱스를 가리킨다. // nums에 수들이 들어가있다고 가정 vector nums; int low = 0; // 초기 세팅: 제일 앞 인덱스..
이전 포스팅에서 C++의 value category(https://m42-orion.tistory.com/67)에 대해 알아보았다. 짧게 정리를 해보자. C++ 11 이후의 value category를 구분하는 기준에는 identity와 move 두 가지가 있다. identity는 두 객체(entity)의 주소(address)를 비교하여 두 객체가 같은지 확인할 수 있는지를 나타낸다. move는 어떤 값이 다른 값으로 이동될 수 있음을 이야기한다. 구분 기준에 따라서 Mixed category(복합 카테고리)와 Primary category(기본 카테고리)로 나눌 수 있다. 먼저 Mixed category는 gl-value(i)과 r-value(m)로 나눌 수 있으며, Primary category는 x..
