Cpp STL의 2차원 벡터를 생성하는 방법에 대해 정리한 문서입니다.개인적인 공부 내용을 정리하는 용도로 작성한 글이기에 잘못된 내용을 포함하고 있을 수 있습니다. 2차원 벡터를 선언하는 방법은 크게 2가지로 구분됩니다.Case1. 벡터 내부에 벡터를 선언하여 2차원 벡터를 생성하는 방식Case2. 1차원 벡터 배열을 사용해 2차원 벡터처럼 사용하는 방식 1번째 케이스는 Row, Column이 모두 동적인 벡터로 벡터 안에 백터가 들어가 있는 형태입니다. 반면 2번째 케이스는 Row는 정적이지만 Column은 동적인 벡터로 1차원 벡터를 배열 형태로 선언하여실제로는 1차원 벡터이지만 2차원 벡터와 같이 사용 가능합니다. 주로 그래프 관련 알고리즘 문제를 풀이할때 인접리스트를 정의할때 2번 방식을 자주 ..
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 (버스의..
