정영주

문제 출처 : BOJ 23327 - 리그전 오브 레전드 https://www.acmicpc.net/problem/23327 23327번: 리그전 오브 레전드 첫 번째 줄에 참가를 원하는 팀의 수 $N$($2 \le N \le 100 \, 000$), 후보 디비전의 개수 $Q$($1 \le Q \le 200 \, 000$)가 주어진다. 두 번째 줄에 정수 $a_1, a_2, \dots, a_N$이 주어진다. $a_i$는 $i$번째로 잘하는 www.acmicpc.net 아주아주 오랜만에 백준 문제를 풀었더니 너무 낯설었다. 이번 방학동안 다시 열심히 불태워봐야겠다. 처음에 이 문제를 봤을 때 2차원 배열로 풀어야 할 것만 같아서 2차원 배열로 풀었는데 (당연하게도) 메모리 초과가 났다. 그렇게 간단한 문제였..

문제 출처 : BOJ 15658 - 연산자 끼워넣기 (2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 백트래킹과 브루트포스를 아주 잘 이해할 수 있는 문제이다. 문제를 요약하자면 N개의 수로 된 수열이 주어졌을 때, 연산자 N-1개를 이용하여 만든 수식의 결과의 최댓값과 최솟값을 구하는 문제이다. 사용할 수 있는 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수는 한정되어 있다. 최종 코..

문제 출처 : BOJ 1199 - 오일러 회로 https://www.acmicpc.net/problem/1199 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 사이에 간선이 여러 www.acmicpc.net 정점의 수와 인접행렬의 정보가 주어지면, 오일러 회로 경로를 출력하는 문제이다. 3시간동안 시간 초과의 늪에 빠져있다가 드디어 빠져나왔다. 아래에 있는 코드가 내가 처음 짠 코드이다. 시간 초과인데 큰 걸 고칠 생각은 안하고 찔끔찔끔 고치다가 위같은 결과물이 나왔다. #include #include using namespace std;..

문제 출처: BOJ 10830 - 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 크기가 N*N인 행렬 A가 주어졌을 때, A의 B제곱을 구하는 문제이다. 그런데 B의 범위가.. 9 이상 100,000,000,000 이하이다. 이렇게 어마무시한 숫자를 보니까 예전에 풀었던 분할정복을 이용한 거듭제곱 문제가 생각나서, 그때 계산했던 방법에 행렬의 곱셈을 계산해주는 함수만 추가해줬더니 맞았다. 참고로 분할정복을 이용한 거듭제곱 문제는 C^n = C^(..

문제 출처 : BOJ 3584 - 가장 가까운 공통 조상 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 두 노드의 가장 가까운 공통 조상을 구하는 문제다. parent 배열을 만들어서 해당 번호의 노드의 부모 노드 번호를 저장했다. 문제에서 주어진 두 노드 f, s부터 루트 노드까지 거슬러 올라면서, 스택 st1, st2에 각각 경로를 저장한다. 스택 st1, st2에서 루트 노드부터의 노드..

문제 출처 : BOJ 1780 - 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 내가 아주 어려워하는 분할 정복 문제이다. N*N 크기의 행렬에서 종이가 모두 같은 수로 되어 있다면 그대로 놔두고, 다른 수가 하나라도 있으면 종이를 9개로 자르는 것을 계속 반복하는 것이다. 이 문제는 재귀함수만 잘 작성한다면 분할 정복 문제 중에서는 그나마 쉽게 풀 수 있는 문제 같다. 최종 코드 #include #include #de..

문제 출처 : BOJ 1058 - 친구 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 이 문제는 2-친구 수가 제일 많은 사람의 2-친구 수를 구하는 문제이다. 2-친구는 친구이거나 친구의 친구이면 된다. 깊이 우선 탐색으로 깊이가 2인 노드들까지만 방문하여 2-친구의 수를 계산해주면 되는 간단한 문제였다. 최종 코드 #include #include #include using namespace std; vector v[51]; int visit[..

문제 출처: BOJ 1120 - 문자열 https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 길이가 다른 두 문자열 A, B가 주어질 때 (A의 길이 < B의 길이) 문자열 A의 앞 또는 뒤에 아무 알파벳이나 추가하여 두 문자열 A, B의 차이를 최소로 하는 프로그램을 작성하는 문제이다. 처음에 브루트포스로 풀려고 아래처럼 코드를 짰다. #include #include using namespace std; in..

문제 출처 : BOJ 1699 - 제곱수의 합 www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 처음에는 단순하게 아래처럼 가장 큰 제곱수를 빼는 식으로 문제를 풀었다. #include using namespace std; int nums[100001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, ans = 0; ..

문제 출처 : BOJ 2230 - 수 고르기 www.acmicpc.net/problem/2230 마지막으로 투 포인터를 연습해보는 문제이다. 주어진 수열에서 두 수의 차이가 m 이상인 것 중 최솟값을 구하는 문제이다. 최종 코드 #include #include using namespace std; #define MAX 100001 #define MAX_GAP 2000000000 int arr[MAX]; bool f(int a, int b) { return a > b; } int main() { int n, m, l = 0, r = 0, gap = 0, min = MAX_GAP; cin >> n >> m; for (int i = 0; i > arr[i]; sort(arr, arr..