전체 글 (45) 썸네일형 리스트형 백준 1463 - 1로 만들기 본문제의 요구사항은 다음과 같다 1. 어떤 수 N 에서 정해진 연산을 통해 1로 만드는 최소횟수를 구한다. 2. 연산은 나누기3 , 나누기2 , 뻬기 1중 하나를 선택할수 있다. 단 나누기 연산은 나누어 떨어질 때에만 가능하다. 본 문제를 풀기위해서는 가능한 모든 경우의 수를 따져바야 하는데 DFS ( 깊이 우선 탐색 ) 를 이용하면 된다. 예를 들어 N 이 12 라고 생각해보면 N 은 3으로도 나누어떨어지고 , 2로도 나누어 떨어진다. 즉 F(12) = min ( F(12/2) , min ( F(12/3) , F(12-1))) + 1 로 계산할수 있다. 좀더 풀이를 나아가보면 .. F(6) = min( F(6/2) , min(F(6/3), F(6-1))) + 1 F(4) = min(F(4/2) , F(.. 백준 1158 - 조세퍼스 문제 본문제는 K 값에 해당 한만큼 점프를 하면서 N 개의 배열을 탐색하는데 매 점프마다 만나는 배열의 Index 를 순서대로 출력해 주면 된다. 물론 한번 만나는 index 위치는 다음 순회때에는 계산되지 않도록 한다. 특별한 알고리즘 없이 배열과 배열의 탐색으로 본 문제를 해결할수 있다. 한가지 주의할 사항은 K 값을 최소화 해줄 필요가 있다는 점이다. 만약 방문하지 않은 남은 index 들이 5이고 k 가 7 이라면 7번을 점프할 필요가 없다. 즉 임의의 지점에서 자신의 위치로 다시 돌아오는 횟수만큼을 제할 수 있다. 아래 그림과 같이 start 지점에서 7번 점프하는것과 2번 점프하는 것과 동일하다. 즉 다음 점프의 횟수는 남은 index 개수로 나눈 나머지와 같다. 이러한 착안들을 기초로 작성된 코드.. 백준 1065 - 한수 본문제의 요구사항은 주어진 값보다 작은 한수(각자리수가 등차수열을 이룸)의 갯수 를 구하는 것이다. 본 문제를 풀기위해서는 두가지 아이디어가 필요하다. 1. 99 이하의 숫자들은 무조건 한수이다. 2. 세자리 숫자 값 을 각 자리별 값을 구하기 위해서 modulation 연산을 이용한다. 간단하게 코드를 살펴보면 아래와 같다. #include #include using namespace std; bool isSameDiffNum(int n) { vector arr; int nClone = n; // 숫자의 각 자리별 값을 vector 로 변환한다. while (n) { arr.push_back(n % 10); n /= 10; } int firstDiff; // 각 자리별 차이값이 등차 여부를 확인한다. .. 백준 - 11375 열혈강호 본 문제를 풀수 있는 방법은 여러가지가 있을 수 있겠지만 그중 한가지 방법은 본 문제를 네트워크 유량의 구조로 모델링을 잘 하는데 있다. 네트워크 유량 이량 그래프에서 source 와 sink 의 weight 가 주어졌을때 임의의 두 노드 사이에 흐를 수 있는 weight 의 최대치를 계산하는 알고리즘이다. 사실 네트워크 플로우의 최대 유량을 계산하는 알고리즘을 이해하는 것은 만만치 않은 일이기 때문에 본 폐이지에서는 대표적인 최대 유량 알고리즘 인 에드몬드-카프 알고리즘을 구현한 C++ Class 를 도입하고 이를 활용하여 답을 찾는데 주안점을 둘 것이다. 해당 클래스의 사용법을 이해하고 재활용하면 여러가지 다양한 최대유량 알고리즘을 손쉽게 풀수 있을 것이다. 문제로 돌아가서 본 문제의 네트워크 플로우.. 백준-15954 인형들 본 문제의 요구사항은 K 개 이상의 연속된 인형들에 대한 고객들의 선호도 값의 표준 편차가 최소가 되는 값을 찾는 것 이다. 본 문제를 해결 하기 위해 크게 두가지 해결해야 할 과제가 있는데 아래와 같다. 1. 각 인형의 K 이상의 Range 에대한 분산 및 표준 편차를 O1 시간에 계산해야 한다. 따라서 주어진 수식에 맞게 분산( 표준편차는 분산의 제곱근이므로 분산 먼저 계산 ) 을 계산하려고 하면 시간 초과가 발생하며, 좀더 간략한 수식으로 바꾸어 주어야 한다. 주어진 분산 계산식을 풀어보면 이해할수 있겠지만 말로 표현 하자면 아래와 같이 표현할 수 있다. 분산 = (모든 원소의 제곱의 합 - 2 * 평균 * 모든 원소의 합 + N * 평균의 제곱) / N 여기서 N 은 물론 원소의 개수를 의미한다... 이전 1 ··· 3 4 5 6 다음
