Doby's Lab

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net Solved By: Map map에서는 find() 메서드를 썼을 때, 해당 key값이 없다면 m.end() iterator를 반환하는 것을 알고 있다면 쉽게 구현할 수 있습니다. #include #include using namespace std; map m; int n, m2; int main(){ cin >> n >> m2; for(int i = 0; i < ..

insert() -> 원소를 추가합니다. map은 pair형이기 때문에 key, value를 pair형태로 타입에 맞게끔 넣어줍니다. -> key 값이 중복되면 런타임 오류가 일어납니다. erase() -> 해당 key값 원소를 지웁니다. 범위를 설정(iterator)해서 특정 범위만 지울 수 있습니다. clear() -> map의 모든 원소를 지웁니다. Map Operator: [] []을 통해 map을 배열처럼 사용할 수 있습니다.

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net Solved By: C++ STL 이제 string도 다루어야 하고, map에 대한 지식을 쌓고자 문제를 풀어보았습니다. 이번 문제에서 깨달은 건 배열과 다른 index와 key의 차이입니다. 특정 index의 value를 다루려면, 그 index만큼 배열이 선언되어있어야 하는데 key는 타입도 상관없고, 그만한 크기도 상관이 없습니다. (map은 트리 구조입니다. 삽입 혹은 삭제를 할 때..

https://www.acmicpc.net/problem/15783 15783번: 세진 바이러스 입력의 첫째 줄에 시설의 수 N(1 ≤ N ≤ 100000), 파이프의 수 M(1 ≤ M ≤ 100000)이 주어진다. 이후 두 번째 줄부터 M+1번째 줄 까지 연결된 정수 시설 A(0 ≤ A ≤ N-1), B(0 ≤ B ≤ N-1) 가 주어진다. www.acmicpc.net Solved By: SCC(Tarjan Algorithm) 저번처럼 쓸데없는 메모리는 잡아먹지 않기 위해 필요한 배열들만 선언하여 사용하였습니다. (https://draw-code-boy.tistory.com/295) 기본적인 SCC문제였으며 indegree가 0인 node들을 찾아주면 됩니다. #include #include #incl..

https://www.acmicpc.net/problem/8012 8012번: 한동이는 영업사원! 한동이는 경상도내를 돌아다니면서 열심히 일하는 영업사원이다. 예전에는 자기가 원하는 도시만 골라서 다닐 수 있었지만 시대가 바뀌어서 이제 그렇게는 하지 못하게 되었다. 시대가 바뀜에 www.acmicpc.net Solved By: LCA Floyd-Warshall 같은 최단 경로 알고리즘이 떠오르기도 하지만 시간 복잡도가 O(N^3)인 걸 생각하면 다른 방법을 떠올려야 합니다. 문제를 읽어보면, '사이클이 없다', 'edge가 n - 1개다.', 'Undirected다.'이런 것을 보면 트리가 떠오릅니다. 그리고, 무조건 1번 노드에서 시작하니 1을 Root Node로 둔 트리입니다. 경로 값이 전부 1이기..

https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net Solved By: Sparse Table 함수 f가 주어졌을 때, {5, 4, 3, 2, 1}이라고 치면 f(1)은 1번 인덱스로 이동하라는 소리입니다. 허나, n은 500,000까지 주어질 수 있고, 쿼리의 수는 200,000까지 주어질 수 있습니다. 즉, ..

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net Solved By: LCA, Sparse Table vertex가 100,000개이고, 쿼리의 수가 100,000개라서 기본적으로 알고 있는 LCA로 다음 문제를 풀었을 때는 O(NM) 시간 초과가 납니다. Sparse Table을 통해 O(MlogN)으로 줄여서 해당 문제를 풀 수 있습니다. #include #include #define MAX 100001 #define LOG_MAX ..

LCA를 공부하다가 LCA를 더 빠르게 구현할 수 있는 것을 알아내고, 이에 필요한 테크닉이 Sparse Table임을 알아냈습니다. 공부한 곳 (https://blog.naver.com/kks227/220793361738) BOJ 17435 (https://www.acmicpc.net/problem/17435) 22.05.01 연구일지 ✔️ Sparse Table이 필요한 이유 다음과 같이 같이 K개의 간선으로 이루어진 Directed Graph가 있다고 했을 때, 1부터 K + 1번 vertex까지 가려면 O(K)가 걸립니다. vertex는 인접해있는, 즉 한 번 이동했을 때, 어떤 vertex로 가는지 알고 있습니다. K가 적당한 숫자라면 괜찮지만 엄청나게 큰 수라면 Time Complexity면에..