티스토리 뷰
A
- 출력해야 하는 문자열 규칙:
- $N$이 짝수인 경우:
문자열의 중앙에 두 개의 '=' 기호가 위치하며, 그 좌우에 '-' 기호가 배치됩니다.
전체 '-' 기호의 개수는 $N-2$개이며, 좌우에 균등하게 분배됩니다.
즉, 왼쪽에 $\frac{N-2}{2}$개의 '-'와 오른쪽에 $\frac{N-2}{2}$개의 '-'를 붙이고, 그 사이에 "=="를 넣습니다. - $N$이 홀수인 경우:
문자열의 중앙에 한 개의 '=' 기호가 위치하며, 그 좌우에 '-' 기호가 배치됩니다.
전체 '-' 기호의 개수는 $N-1$개이며, 좌우에 균등하게 분배됩니다.
즉, 왼쪽에 $\frac{N-1}{2}$개의 '-'와 오른쪽에 $\frac{N-1}{2}$개의 '-'를 붙이고, 그 사이에 "="를 넣습니다.
- $N$이 짝수인 경우:
- 문제:
정수 $N$이 주어졌을 때, 아래 규칙에 따라 문자열을 출력하는 문제입니다.
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
if(n%2 == 0){
int c = (n-2)/2;
cout << string(c,'-') + "==" + string(c,'-') << endl;
}else{
int c = (n-1)/2;
cout << string(c,'-') + "=" + string(c,'-') << endl;
}
}N = int(input())
if N % 2 == 0:
print('-' * (N // 2 - 1) + '=' * 2 + '-' * (N // 2 - 1))
else:
print('-' * (N // 2) + '=' + '-' * (N // 2))B
풀하우스 구성 조건
- 각 카드의 숫자 빈도수 계산
- 주어진 카드들에서 각 숫자가 몇 장씩 있는지 셉니다.
- 전체 하우스를 만들 수 있는 조건
전체 하우스는 오직 다음 두 조건을 동시에 만족할 때만 구성할 수 있습니다:- 세 장 이상의 같은 숫자:
카드 중 하나의 숫자 $x$가 적힌 카드가 최소 3장 이상 있어야 합니다. - 두 장 이상의 다른 숫자:
$x$와 다른 숫자 $y$가 적힌 카드가 최소 2장 이상 있어야 합니다.
- 세 장 이상의 같은 숫자:
- 빈도수 정렬로 검증하는 방법
- 각 숫자의 빈도수를 내림차순으로 정렬한 후,
- 가장 많이 등장한 숫자의 빈도가 3 이상이고,
- 두 번째로 많이 등장한 숫자의 빈도가 2 이상이면 전체 하우스를 만들 수 있습니다.
- 각 숫자의 빈도수를 내림차순으로 정렬한 후,
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int> bk(13,0);
for(int i=0;i<7;i++){
int x;
cin >> x;
bk[x-1]++;
}
sort(bk.rbegin(),bk.rend());
if(bk[0]>=3 && bk[1]>=2){cout << "Yes\n";}
else{cout << "No\n";}
return 0;
}저 같은 경우
0 ans 는 [3개 이상이 있는가?, 2개 이상이 있는가?] 으로 만들어 둡니다.
1 빈도수 저장 후 3개 이상인 카드를 찾고 ans[0] = True
2 2개 이상인데 3개 이상인걸 이미 찾았다면 3개 이상인지 볼 필요가 없겠죠. ans[1] = True
import sys
input = sys.stdin.readline
arr = list(map(int, input().split()))
cnt = [0] * 14
for e in arr:
cnt[e] += 1
ans = [False, False]
for i in range(14):
if cnt[i] >= 2:
if cnt[i] >= 3 and not ans[0]:
ans[0] = True
else:
ans[1] = True
if ans == [True, True]:
print("Yes")
else:
print("No")C
문제 요약
총 $N$명의 사람이 있으며, 각 사람은 $1$부터 $N$까지의 라벨을 갖습니다.
각 사람 $i$는 정수 $A_i$를 가지고 있습니다.
조건:
다른 $N-1$명의 사람들 중 어떤 사람도 자신의 정수 $A_i$와 같은 정수를 갖지 않는 사람들만을 고려합니다.
목표:
조건을 만족하는 사람들 중, 정수 값이 가장 큰 사람의 라벨을 출력합니다.
만약 조건을 만족하는 사람이 없다면, 그 사실을 출력합니다.
초기 구현에서는 각 사람마다 다른 사람들과 비교하여 같은 숫자가 있는지를 확인하므로, 전체 시간 복잡도가 $ \Theta(N^2) $가 되어 큰 입력에서는 TLE(시간 초과)가 발생합니다.
함수형 프로그래밍의 함수(filter, all 등)를 사용해도 내부적으로 이중 반복문과 같은 동작을 하므로 동일한 시간 복잡도를 갖게 됩니다.
대신, 각 정수에 대해 해당 정수를 가진 사람들의 인덱스를 저장하는 associative array(예: 딕셔너리)를 구성하는 방법을 사용할 수 있습니다.
주어진 배열을 한 번 순회하면서 각 정수에 해당하는 인덱스를 추가하는 과정은 $ O(N \log N) $의 시간에 처리할 수 있으며, 해시를 사용할 경우 평균 $ O(N) $의 시간에 처리할 수 있습니다.
이 associative array에서, 리스트의 크기가 $1$인 경우에만 해당 정수가 다른 사람들과 중복되지 않았음을 의미합니다.
따라서, 딕셔너리의 내용을 한 번 순회하여 원하는 조건을 만족하는 인덱스를 찾으면, 전체 알고리즘의 시간 복잡도는 $ O(N \log N) $ 내에 해결할 수 있습니다.
from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))
d=defaultdict(list)
for i,a in enumerate(A):
d[a].append(i)
for key in sorted(d, reverse=True):
if len(d[key])==1:
print(d[key][0]+1)
exit()
print(-1)
D
문제 요약
무한히 큰 2차원 격자에 캠프파이어가 위치한 $(0,0)$ 셀이 있으며, 시간 $t=0$에는 오직 $(0,0)$에만 연기가 존재합니다.
문자열 $S$가 주어지며, $S$는 길이 $N$의 문자열로 각 문자는 $N$, $W$, $S$, $E$ 중 하나입니다. 시간 $t=1,2,\dots,N$에 대해 다음과 같이 순차적으로 진행됩니다:
- 바람에 의한 연기의 이동:
- 만약 $S_t = N$이면, 모든 셀 $(r,c)$의 연기가 $(r-1,c)$로 이동합니다.
- 만약 $S_t = W$이면, 연기는 $(r,c-1)$로 이동합니다.
- 만약 $S_t = S$이면, 연기는 $(r+1,c)$로 이동합니다.
- 만약 $S_t = E$이면, 연기는 $(r,c+1)$로 이동합니다.
- 연기의 보충:
- 만약 이동 후 $(0,0)$ 셀에 연기가 없다면, $(0,0)$에 새로운 연기를 생성합니다.
다카하시는 셀 $(R,C)$에 위치해 있습니다.
목표:
각 시간 $t+0.5$ (즉, 시간 $t$ 후 연기의 이동 및 보충이 끝난 직후) 시점에 셀 $(R,C)$에 연기가 존재하는지 여부를 판별하여, 문제에서 요구하는 형식에 따라 결과를 출력하는 것입니다.
연기를 바람에 따라 직접 이동시키면, 매 시간 $t$마다 연기를 이동하는 데 $O(t)$의 시간이 소요되어 전체 시간 복잡도가 $O(N^2)$가 됩니다. 이는 실행 시간 제한을 초과할 수 있습니다.
이를 피하는 방법은 다음과 같습니다:
- 모든 연기는 바람에 따라 동일하게 움직이므로, 연기를 실제로 이동시키지 않고 연기가 생성되는 위치에 고정시킵니다.
- 대신, 불과 다카하시의 위치를 바람의 반대 방향으로 이동시키면 두 객체 간의 상대적 위치는 원래 문제와 동일하게 유지됩니다.
구체적인 단계는 다음과 같습니다:
- 셀 $(0,0)$에 연기를 생성합니다.
- 불의 위치와 다카하시의 위치를 각각 $(0,0)$과 $(R,C)$로 초기화합니다.
- 시간 $t=1,2,\dots,N$에 대해, 아래의 규칙에 따라 불과 다카하시의 위치를 이동시킵니다:
- 만약 $S_i = N$이면, 현재 위치 $(r, c)$에서 $(r+1, c)$로 이동합니다.
- 만약 $S_i = W$이면, $(r, c)$에서 $(r, c+1)$로 이동합니다.
- 만약 $S_i = S$이면, $(r, c)$에서 $(r-1, c)$로 이동합니다.
- 만약 $S_i = E$이면, $(r, c)$에서 $(r, c-1)$로 이동합니다.
- 이동 후, 불이 위치한 셀에 연기를 생성합니다.
- 다카하시의 현재 위치에 연기가 있는지 확인하여, 있으면 $1$, 없으면 $0$을 출력합니다.
자료구조 활용:
연기가 생성된 셀의 위치들을 $set$과 같은 자료구조에 저장하면, 다카하시의 위치가 연기 위치 집합에 포함되어 있는지 빠르게 확인할 수 있습니다. 이 경우, 각 확인 연산의 시간 복잡도는 $O(\log N)$가 되므로, 전체 알고리즘의 시간 복잡도는 약 $O(N \log N)$로 줄어듭니다.
즉, "연기를 바람에 따라 이동시키는 대신 불과 다카하시를 반대 방향으로 이동시키는" 방법을 사용하면 실행 시간 제한 내에 문제를 해결할 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
using pi=pair<int,int>;
int main(){
int n;
pi t;
string s;
cin >> n >> t.first >> t.second;
cin >> s;
pi f={0,0};
set<pi> st;
st.insert(f);
for(auto &nx : s){
if(nx=='N'){
t.first++;
f.first++;
}
else if(nx=='W'){
t.second++;
f.second++;
}
else if(nx=='S'){
t.first--;
f.first--;
}
else{
t.second--;
f.second--;
}
st.insert(f);
if(st.find(t)==st.end()){cout << "0";}
else{cout << "1";}
}cout << "\n";
return 0;
}import sys
input = sys.stdin.readline
N, R, C = map(int, input().split())
S = input().strip()
x, y = 0, 0
dx, dy = [+1, 0, -1, 0], [0, +1, 0, -1]
mp = {}
s = []
for e in S:
if e == 'N':
s.append(0)
elif e == 'W':
s.append(1)
elif e == 'S':
s.append(2)
else:
s.append(3)
for e in s:
if not ((x, y) in mp):
mp[(x, y)] = 1
x += dx[e]
y += dy[e]
R += dx[e]
C += dy[e]
if (R, C) in mp:
print(1, end='')
else:
print(0, end='')
# print(mp)
# print(R, C)E
홀수 사이클이 없는 그래프는 이분 그래프라고 하며, 이는 다음과 같이 설명할 수 있습니다:
- 정점들을 두 가지 색으로 칠할 때, 같은 색의 정점끼리 연결된 간선이 없으면 그 그래프는 이분 그래프입니다.
- 따라서, 정점 집합을 색상에 따라 두 개의 부분 집합(파티트 집합)으로 분할할 수 있습니다.
- 연결된 이분 그래프의 경우, 이 두 부분 집합은 DFS(깊이 우선 탐색)나 BFS(너비 우선 탐색)를 통해 임의의 정점에서 시작하여 구할 수 있으며, 유일하게 결정됩니다.
문제 해결 아이디어
문제에서는 트리가 주어지고, 트리는 이분 그래프임을 이용합니다.
만약 두 부분 집합의 크기가 각각 $A$와 $B$라면, 트리에는 이미 $N-1$개의 간선이 존재합니다.
추가로 연결할 수 있는 간선의 최대 개수는
AB−(N−1)AB - (N-1)
개가 됩니다.
간선을 추가하는 순서는 간선을 추가할 수 있는지 여부에 영향을 주지 않으므로,
이 게임은 결국 AB−(N−1)AB - (N-1)개의 선택지 중 번갈아 가며 한 가지씩 선택하는 것과 동일합니다.
따라서, 만약 AB−(N−1)AB - (N-1)이 홀수라면 선공이 승리하고, 짝수라면 후공이 승리하게 됩니다.
문제는 각 정점이 어떤 부분 집합에 속하는지를 먼저 결정한 후, 가능한 간선 선택지를 모두 열거하여 set과 같은 자료구조에 저장하는 방식으로 해결할 수 있습니다.
추후 코드 추가
F
문제 요약
주어진 문자열 $S$를 접두사로 갖는 가장 짧은 팰린드롬을 하나 구하는 문제입니다.
입력 조건:
- $S$는 길이가 $1$ 이상 $500,000$ 이하인 문자열입니다.
- 문자열은 대문자 영어 알파벳으로 구성됩니다.
출력:
- $S$를 접두사로 갖는 가장 짧은 팰린드롬 문자열을 출력합니다.
문자열 $S$와 그 역순 문자열의 연결은 당연히 팰린드롬이므로, 구하려는 문자열의 길이는 최대 $2 \times |S|$가 됩니다.
팰린드롬의 성질을 살펴보면, 길이가 $|S|+k$인 팰린드롬(여기서 $0 \le k \le |S|$)의 접두사가 $S$인 경우, 이를
S1S2…S∣S∣T1T2…TkS_1 S_2 \dots S_{|S|} T_1 T_2 \dots T_k
라고 나타낼 수 있습니다. 팰린드롬의 정의에 따라 아래와 같은 식들이 성립합니다.
S1=Tk,S2=Tk−1, ⋮Sk=T1,Sk+1=S∣S∣, ⋮S⌊(∣S∣+k+1)/2⌋=S⌊(∣S∣+k+2)/2⌋.\begin{aligned} S_1 &= T_k, \\ S_2 &= T_{k-1}, \\ &\;\;\vdots \\ S_k &= T_1, \\ S_{k+1} &= S_{|S|}, \\ &\;\;\vdots \\ S_{\lfloor(|S|+k+1)/2\rfloor} &= S_{\lfloor(|S|+k+2)/2\rfloor}. \end{aligned}
즉, $S$의 마지막 $(|S|-k)$개의 문자가 팰린드롬을 이루어야 하며, $T_1, T_2, \dots, T_k$는 $S$에 의해 유일하게 결정됩니다.
따라서, 문제는 $S$의 가장 긴 접미사가 팰린드롬인지 찾는 문제로 귀결됩니다.
이를 해결하는 직접적인 방법 중 하나가 바로 Manacher의 알고리즘으로, 이 알고리즘을 사용하면 문제를 $O(N)$ 시간에 해결할 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
vector<int> manacher(string &S){
vector<int> R(S.size());
int i = 0, j = 0;
while (i < S.size()) {
while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
R[i] = j;
int k = 1;
while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
i += k; j -= k;
}
return R;
}
int main(){
string s;
cin >> s;
string ms="$";
for(auto &nx : s){
ms.push_back(nx);
ms.push_back('$');
}
auto r=manacher(ms);
int k=0;
for(int i=s.size();;i++){
if(r[i]>=s.size()-k){break;}
k++;
}
cout << s;
for(int i=0;i<k;i++){
cout << s[k-1-i];
}cout << "\n";
return 0;
}G
문제 요약
문제:
$N$개의 정점과 $M$개의 간선을 가진 단순 무방향 그래프 $G$가 주어집니다. 정점은 $1$부터 $N$까지, 간선은 $1$부터 $M$까지의 번호를 가지며, $i$번째 간선은 정점 $U_i$와 $V_i$를 연결합니다. 처음 주어진 그래프 $G$는 홀수 사이클을 포함하지 않으므로 이분 그래프입니다.
게임 규칙:
아오키와 다카하시는 그래프 $G$를 사용하여 게임을 진행합니다. 아오키가 먼저 시작하며, 두 플레이어는 번갈아 가며 다음의 연산을 수행합니다.
- 정수 쌍 $(i,j)$ ($1 \le i < j \le N$)를 선택합니다. 이때 다음 두 조건을 모두 만족해야 합니다.
- 현재 $G$에는 정점 $i$와 $j$를 잇는 간선이 존재하지 않아야 합니다.
- 정점 $i$와 $j$를 잇는 간선을 추가해도 홀수 사이클이 생성되지 않아야 합니다.
- 조건을 만족하는 $(i,j)$를 선택한 후, 정점 $i$와 $j$를 잇는 간선을 $G$에 추가합니다.
연산을 수행할 수 없는 플레이어가 패배하며, 상대 플레이어가 승리합니다.
문제 목표:
양 플레이어가 최적의 전략으로 플레이할 때, 승리하는 플레이어가 누구인지를 결정하는 것입니다.
제약 조건:
- $1 \le N \le 2 \times 10^5$
- $0 \le M \le 2 \times 10^5$
- $1 \le U_i < V_i \le N$
- 주어진 그래프 $G$는 홀수 사이클을 포함하지 않으며, 다중 간선은 존재하지 않습니다.
- 모든 입력 값은 정수입니다.
주어진 그래프 $G$는 홀수 사이클이 없으므로, 각 연결 요소는 이분 그래프입니다. 이를 바탕으로 다음 다섯 가지 특성 값을 정의합니다.
- $x$: 연결성을 유지하면서 이분성을 보존할 수 있도록 추가 가능한 간선의 수
- $ee$: 양쪽 파트의 정점 수가 모두 짝수인 연결 요소의 수
- $oo$: 양쪽 파트의 정점 수가 모두 홀수인 연결 요소의 수
- $eo$: 두 개 이상의 정점을 가진 연결 요소 중 한 파트는 짝수, 다른 파트는 홀수인 경우의 수
- $iso$: 정점이 $1$개인 연결 요소의 수
이제 승자는 다음과 같이 결정됩니다.
- $N$이 홀수인 경우:
- 첫 번째 플레이어는 $oo+x$가 홀수일 때 승리하고, 짝수이면 두 번째 플레이어가 승리합니다.
- $N$이 짝수이고 $eo=0$인 경우:
- 이 경우 $iso$는 반드시 짝수입니다.
- 첫 번째 플레이어는 $\frac{iso}{2}+x$가 홀수일 때 승리하고, 짝수이면 두 번째 플레이어가 승리합니다.
- $N$이 짝수이고 $1\le eo\le 2$인 경우:
- 첫 번째 플레이어가 항상 승리합니다.
- $N$이 짝수이고 $eo\ge3$인 경우:
- 첫 번째 플레이어는 $oo+x$가 홀수일 때 승리하고, 짝수이면 두 번째 플레이어가 승리합니다.
증명의 아이디어
- 게임에서 각 이동은 간선의 수를 $1$씩 증가시키므로, 최종 그래프의 간선 수의 패리티(홀수/짝수)가 중요합니다.
- $N$이 홀수인 경우:
최종 이분 그래프에서 한 파트의 정점 수는 홀수, 다른 파트는 짝수가 되어 최종 간선 수는 항상 짝수가 됩니다. 따라서, 승패는 현재 그래프의 간선 수의 패리티, 즉 $oo+x$의 홀짝성에 따라 결정됩니다. - $N$이 짝수인 경우:
최종 간선 수의 패리티는 두 파트의 정점 수가 모두 홀수인지 혹은 모두 짝수인지에 따라 달라집니다.
특히, $eo$와 $iso$로 대표되는 연결 요소들의 병합 과정에 따라 최종 패리티가 결정되므로, 이 과정을 적절히 처리하는 것이 승패를 좌우합니다.
이와 같이, 위의 다섯 가지 특성 값을 활용하여 게임의 승리 조건을 분석하면, 각 경우에 대해 최적의 전략을 구분할 수 있습니다.