INFO난이도 : SILVER3문제유형 : DataStructure Dequehttps://www.acmicpc.net/problem/18115SOLVE앞 뒤가 모두 뚫려있는 Deque 자료구조를 사용해 문제를 풀이했다. 예제 입력2를 예시로 문제에서 제시해주는 값을 정리해보면 다음과 같다. 초기 상태 : 알 수 없음 기술 사용 순서 : 2 3 3 2 1최종 상태 : 5 4 3 2 1 즉, 기술을 거꾸로 사용하며 반대로 적용시키면 초기 상태를 구할 수 있다. n개의 명령을 저장할 n크기의 cmd 벡터를 정의한 뒤 명령을 입력받는다. int n; cin >> n; vector cmd(n); for(int i = 0; i > cmd[i]; } 명령을 뒤에서부터 반대로 ..
INFO난이도 : SILVER2문제유형 : Two Pointerhttps://www.acmicpc.net/problem/30804SOLVE단순 브루트포스 방식으로는 O(N^2) 만큼의 시간복잡도가 소요되기에, 시간초과가 발생한다. 따라서 2개의 포인터를 두고 모든 경우의수를 탐색하는 투포인터 알고리즘 (Two Pointer Algorithm) 을 사용해서 문제를 풀이했다. 탕후루 정보를 저장할 v 벡터와 각 과일의 번호 개수를 저장할 fruits 벡터를 저장한다. 문제 조건에서 총 1부터 9까지 번호가 붙어있다고 제시하였으니 fruits 벡터의 크기는 10으로 고정하고 Two Pointer 로직 내부에서 현재 탕후루 배열의 과일의 종류 개수를 판별하는 로직에서 활용한다. vector v(n, 0..
INFO난이도 : GOLD4유형 : Graph Folyd Warshallhttps://www.acmicpc.net/problem/11404SOLVE플로이드 와샬 알고리즘을 사용해 특정 정점으로부터 모든 정점 사이의 거리의 가중치를 구해주면 되는 간단한 문제이다.n의 최대 크기는 100이며, Floyd Warshall은 O(N^3) 만큼의 TimeComplexity를 소모하기에 1초 안에 충분히 로직을 수행 가능하다. 정점 사이의 간선이 존재하지 않는 경우를 인접행렬에 저장하기 위해 별도의 INF 상수를 정의한다. dist 배열에는 정점 사이의 간선 가중치를 저장한다. const int INF = 10001000;int dist[101][101]; 정점의 수 n (도시의 개수) 과 간선의 개수 m (버스의..
INFO난이도 : SILVER2유형 : Graph DFShttps://www.acmicpc.net/problem/24479SOLVE문제에서 주어진 조건대로 각 노드를 오름차순으로 DFS 탐색을 해주면 되는 간단한 그래프 문제이다. 단 cin, cout 속도를 최적화해 주는 코드를 반드시 명시해 주어야 한다. 그렇지 않으면 시간초과가 발생한다. cin.tie(0); ios_base::sync_with_stdio(0); 인접 리스트 방식으로 간선 정보를 입력받는다. vector adj_list[200001]; for (int i = 1; i > node1 >> node2; adj_list[node1].push_back(node2); adj_list[node2].pu..
Info난이도 : GOLD3유형 : DataStructurehttps://www.acmicpc.net/problem/17299소스코드 : https://github.com/novvvv/PS/blob/main/BOJ/2025/C++/17299.cppSolve문제분석F(Ai) - Ai가 수열A에서 등장한 횟수. Ai의 오등큰수 - 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중 가장 왼쪽에 있는 수. 그러한 수가 없으면 오등큰수는 -1 a[] : 크기가 n인 수열freq[] : ai가 몇 번 등장했는지 빈도를 저장할 수열ngf[] : 각 원소의 오등큰수 정보를 저장할 수열 int a[max_val], freq[max_val], ngf[max_val]; 수열의 정보를 입력함과 동시에 해당..