문제 링크 https://www.acmicpc.net/problem/2271 문제 요약 자연수로 이루어진 크기 \(N\)인 배열 \(A\)가 주어진다. 이 때 \(1\leq P\ \lt\ Q\ \lt\ R\ \lt\ S\ \leq\ N\)을 만족하는 \(P\), \(Q\), \(R\), \(S\)에 대해 아래 두가지 수식이 만족하는 경우가 있는지 찾는 문제다. 1. \(A[Q]\ \lt\ A[S]\ \lt\ A[P]\ \lt\ A[R]\) 2. \(A[Q]\ \gt\ A[S]\ \gt\ A[P]\ \gt\ A[R]\) 문제 풀이 우선 2번 경우는 생각하지 말고 1번 경우만 생각해 보도록 하자. \(i\lt j\) 인 임의의 \(i\), \(j\)를 선택했다고 하자. 만약 \(A[i] \lt A[j]\)를..
Data Structure
여기를 클릭해 주세요. 문제 링크 https://www.acmicpc.net/problem/3136 문제 요약 문제에서 주어진 방향대로 선을 그어나갔을 때 생기는 평면의 개수를 출력하는 문제. 문제 풀이 이 문제를 처음 본다면 당황할 수 있다. 언제 공간이 생기는지 아는것도 힘들 뿐더러 그걸 알았다고 하더라도 공간을 어떻게 세어야 할지 막막하기 때문이다. 하지만 정수 좌표를 버텍스라고 생각하고, 선들을 엣지라고 생각한다면 그래프에서의 평면의 개수를 찾는 문제로 치환이 된다. 일반적으로 그래프에서 평면의 개수를 찾는것은 어렵지만 선을 그어서 생기는 그래프는 평면그래프 라는것을 깨닫는 순간 문제는 매우 쉬워진다. 평면그래프에는 아래와 같은 공식이 있다. \(V\ -\ E\ +\ F\ =\ 2\) \(V\)은..
여기를 클릭해주세요. 문제 링크 https://www.acmicpc.net/problem/10546 문제 요약 \(N\)개의 이름이 차례대로 주어진다. 그 뒤 \(N\)개의 이름 중 \(N - 1\)개가 차례대로 다시 주어진다. 이 때 다시 주어지지 않은 이름 한개를 찾는 문제다 문제 풀이 \(N\)이 최대 \(10^5\)이긴 하지만 한 이름의 길이가 최대 20밖에 안되기 때문에 \(map\)을 사용해 쉽게 해결할 수 있다. 한가지 주의할 점은 이름이 같은 사람이 존재하기 때문에 동일한 이름의 수를 세어주어야 한다. 소스 코드 더보기 #include #include #include using namespace std; map cnt; int n; char str[22]; int main() { scanf..
