분류 전체보기

https://www.acmicpc.net/problem/11060문제 접근(문제 정리)현재 내가 있는 위치의 숫자에 대해, 이 수 이하만큼 앞으로 전진할 수 있다. (문제 접근)나의 위치를 정점으로, 전진할 수 있는 경우들을 간선으로 생각하면,그래프에서 최단거리를 구하는 문제가된다. BFS를 이용하여 최단거리를 구하자구현#define _CRT_SECURE_NO_WARNINGS#include #include using namespace std;int n;int maze[1001];bool discovered[1001];int minDist[1001];void input(){ scanf("%d", &n); for (int i = 0; i q = queue(); q.push(0); minDist[0] = ..

https://www.acmicpc.net/problem/10826문제 접근문제에 주어진 점화식으로 DP를 사용하여 접근하였다.n이 10000이하 이므로 long long형, unsigned long long형을 사용하여 구현해 보았지만, 오버플로우가 발생하였다. 이에 숫자를 문자열로 대체하는 방법을 사용하였다 (문자열 덧셈)기본적인 방법으로 뒷자리부터 한자리씩 계산을 하고,그 합이 10이 넘으면 그 다음 결과값에 1을 더해주는 방식을 사용하였다구현(문자열 덧셈)우선 뒷자리부터 계산을 하기위해 더해지는 두 문자열을 뒤집었다문자열에 접근을 할때 index를 이용하여 접근을 할건데, index가 문자열의 길이를 넘어가면 안되므로 3번에 거쳐 덧셈을 진행하였다. (두 문자열 a, b가 있고 a a문자열의 길이..

https://www.acmicpc.net/problem/2470문제 접근(문제 요약)특성값의 합이 0에 가장 가까운 두 용액을 선택하자  (접근 방법)Brute Force로 List에서 두 용액을 선택한다면 O(nC2)이기 때문에 불가능할 것이다.따라서 Two Pointer를 이용하여 두 용액을 선택하여 O(n)으로 해결하고자한다. Two Pointer를 이용하기 전에, 포인터를 이동시킬 근거를 만들어주기 위해 용액들을 정렬한다. 양쪽 끝에서 포인터를 출발시켜 모든 용액을 탐색하는 방식으로 하고자 한다.용액을 가리키는 포인터를 이동시킨다는 것은 특성값의 절대값이 더 작은 용액을 선택한다는 의미이다. 따라서 특성값이 작은 용액을 이동시키면 두 용액의 특성값의 합은 0에서 더욱 멀어지므로, 특성값이 큰 용..

https://www.acmicpc.net/problem/21870문제 접근문제 요약1. 배열을 좌 우로 나눈다2. 좌우 중 하나를 선택하여 원소들의 GCD를 구한다3. 나머지 하나는 1번부터 반복한다=> 구한 GCD의 합의 최대값을 구하자접근 방법분할 정복으로 접근하자 (문제부터 분할정복을 유도하고 있다)선택한 배열을 처리하는 함수 getGCD와 이외의 배열을 처리하는 getBeauty를 이용하여 좌측을 선택한 경우와 우측을 선택한 경우의 최대값을 구하자구현getGCD() 함수주어진 배열을 순회하며, GCD를 구한다// 해당하는 원소들의 GCD를 구하는 함수int getGcd(int sidx, int eidx){ int ret = arr[sidx]; for (int i = sidx; i  getBeau..

https://www.acmicpc.net/problem/1963문제 접근(문제 정리) 두 소수 A, B가 주어졌을때, A->B로 변환 시 필요한 최소 횟수를 구하자변환) 1. 숫자는 한번에 한자리만 변경가능         2. 첫번째 자리 수는 0이 될 수 없다         3. 변환된 수는 '소수'여야 한다 (접근 방법)1. 소수 구하기 => 에라토스테네스의 체2. 변환하는 최소 횟수 구하기 => BFS (최단 거리) (시간 복잡도)에라토스테네스의 체의 시간복잡도는 O(Nlog(logN))이다BFS의 시간복잡도는 O(V + E)이다한 정점에서의 간선개수는 한 숫자에서 다른 숫자로 변환 가능한 경우의 수이다 ( = 8+9+9+9 = 35)정점의 개수는 8999개이다 (1000~9999까지 가능하므로)..

https://www.acmicpc.net/problem/17103문제 접근소수에 대한 리스트를 구하고, 해당 리스트의 값들을 조합하여 N을 만들자(소수 구하기) 에라토스테네스의 체 알고리즘을 이용 (N을 표현할 수 있는 두 소수를 구하자)1. Brute Force    O(N)의 크기를 가지는 소수 리스트에서 2개의 소수를 선택하는 경우의 수는 nC2, 약 10^12이므로 부적절한 방법이다.2. Two Pointer    양쪽 끝에서 부터 시작하여 포인터를 점차 중앙으로 이동시키면서 경우의 수를 찾는다    두 포인터의 상대적인 위치가 역전되지 않을때까지 반복하므로 O(N)의 시간복잡도를 가진다    구현Two Pointer를 사용하여 구현하였다(좌측 포인터 : sidx, 우측 포인터 : eidx)현재..

https://www.acmicpc.net/problem/2023문제 접근1. 에라토스테네스의 체 사용최대 8자리 정수이므로 약 1억개의 int형 변수들을 저장해야하는데, 메모리 제한에 걸린다2. 그러면 저장하지 말고 모든 N자리 정수에 대해 신기한 소수인지 확인하는 방법은?최대 8자리 정수이고, 좌측부터 1~8자리가 소수인지 확인해야한다소수를 판별하는 방법N = A*B, A8자리 정수에 대해 신기한 소수를 구하면 연산횟수는 아래와 같이 된다8자리 : 10^4, 7자리 : 10^3.5, ... 2자리 : 10^1총 약 10^4번 연산해야한다모든 8자리 정수에 대해 위 연산을 수행해야한다. 총 연산 횟수는 10^8 * 10^4으로 시간 제한에 걸린다3. 그렇다면 모든 수를 하나씩 검사하면서 찾는 것이 아니..

https://www.acmicpc.net/problem/1644문제 접근1. N보다 작은 정수들이 소수인지 여부를 저장한다 (에라토스테네스의 체 사용) => O(Nlog(logN))2. 투포인터를 이용해 구간합을 구한다 => O(N)구현#define _CRT_SECURE_NO_WARNINGS#include #include using namespace std;int N;vector primeNum;bool visited[4000001];void input(){ scanf("%d", &N);}void GetPrimeNumber(){ for (int i = 2; i 마무리하며실제 문제를 풀면서 작성한 메모

https://www.acmicpc.net/problem/1987문제 접근경로에 따라 간선이 변하는 문제이다.인접 간선을 구할때, 일반적인 탐색에 더해 조건을 추가한다구현기존 dfs를 구현할 때 사용하는 visited에 더해 알파벳을 방문한 적이 있는지를 저장하는 visitedMap을 추가하였다.인접 간선을 구할때, visitedMap을 통해서 해당 알파벳에 방문한 적이 있는지 확인한다. 또한 dfs에서 깊이를 반환하게 하여 최대 깊이를 구할 수 있도록 코드를 작성했다#define _CRT_SECURE_NO_WARNINGS#include #include #include using namespace std;int R, C;char graph[28][28];bool visited[28][28];map vis..

https://www.acmicpc.net/problem/2668문제 접근(문제 요약)첫번째 줄에는 1~N까지의 숫자가 순서대로 있고, 두번째 줄에 숫자가 주어진다"첫째줄에서 뽑은 숫자의 집합 = 이에 상응하는 둘째줄의 숫자 집합"이 되는 숫자집합 중에서 개수가 최대인 집합을 구해라1. 모든 숫자 조합에 대해 뽑아보기N은 최대 100이므로 부적절한 방법이다 2. 순서대로 진행하기숫자를 정점으로, 표를 간선으로 생각하면 그래프가 된다. 그래프로 문제를 다시 표현해보자.첫번째 줄의 숫자의 집합과 두번째 줄의 숫자의 집합이 동일해야한다는 말을 그래프의 측면에서 본다면, A에서 B로 향하는 경로가 있다면 B에서 A로 향하는 경로도 있어야 한다는 의미이고 이는 Cycle을 의미한다다시말해 이 문제는 "Cycle을..