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난이도 : SILVER1유형 : DFS Graphhttps://www.acmicpc.net/problem/11403SOLVE문제에서 주어진 조건을 그대로 그래프 형태로 구현하면 되는 문제이다. 항상 이러한 그래프 구현 문제는 문제 조건을 잘 읽어야 한다. 11403 경로찾기 문제는 "가중치가 없는" "방향 그래프" 임에 유의하여 로직을 구현해야한다. 방향 그래프임에 유의하여 입력값이 1인 경우에만 인접 리스트에 노드를 추가한다. int line; for (int i = 0; i > line; if (line == 1) { adj_list[i].push_back(j); } } } 다음으로 노드의 개수(..
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..
