개인사

리뷰 트라이와 해시맵을 사용하여 푸는 문제, 2트라이, 1트라이 1해시맵, 2해시맵 모두 풀리는 것 같다.https://www.acmicpc.net/problem/19585 전역 변수c, n, q : 색상 정보의 개수 c, 팀 정보의 개수 n, 쿼리의 개수 qteams : 팀 정보를 저장할 해시맵 key : 문자열, value : 정수형으로 초기화 한다.Trie : 트라이를 통해 색상 정보를 저장할 구조체 소문자에 대한 정보를 트리형태로 저장한다. 함수1. insertvoid insert(Trie* node, const string& str) 트라이를 통해 트리 구조에 문자를 삽입하는 함수매개변수로 Trie 타입의 현재 노드의 포인터와 입력할 문자열인 str를 받아준다.문자열을 탐색하면서 관련 노드가 존..

리뷰 트리에서의 다이나믹 프로그래밍을 활용하여 얼리어답터의 최소 갯수를 구하는 문제https://www.acmicpc.net/problem/2533 전역 변수n : 노드의 개수lst : 인접 리스트를 통해 노드간 양방향 간선 정보를 저장할 2차원 정수형 벡터dp : 각 노드가 얼리어답터일때와 아닐때의 정보를 저장할 배열v : dfs탐색 시 노드의 방문 정보를 저장할 배열 함수1. dfsvoid dfs(int cn) 깊이 우선 탐색을 통해 얼리어답터의 개수를 재귀적으로 구해줄 함수현재 노드를 매개변수를 통해 전달받고, 각 인접리스트의 노드를 매개변수로 전달해 준다.함수 실행 시 현재 노드가 얼리어답터일때는 1, 아닐때는 0으로 초기값을 세팅해 준다.인접리스트를 순회하고 자식 노드가 방문하지 않았을 경우 우..

리뷰 문자열을 트리 형태로 관리하여 효율적으로 저장, 출력하기 위한 트라이의 기본이 되는 문제https://www.acmicpc.net/problem/14725 전역 변수Trie : 문자열을 트리 형태로 저장하는 구조체, 맵을 통해 문자열을 key로, 하위 트라이를 value로 가진다. 함수1. insertvoid insert(Trie* node, const vector& foods) 문자열 트리의 현재 노드에 하위 노드를 삽입하는 함수현재 노드 정보와 추가해야할 음식들을 문자열 타입 벡터 매개변수로 받는다.우선 루트 노드 정보를 cur이라는 변수에 포인터를 참조하여 값을 별도로 저장해 준다.추가할 음식들을 탐색하면서 현재 루트 로드에 해당 음식이 존재하지 않으면 새로운 자식을 추가해 준다.만약 루트 로..

리뷰 세그먼트 트리의 기초가 되는 문제인듯 싶다, 구간 업데이트 쿼리가 아닌 리프 노드까지 도달해야 하는 문제수열과 쿼리 시리즈 부터 풀다보니 이런 기초 세그를 응용하는 문제가 약해서 생각의 폭을 넓혀야 겠다 ㅠhttps://www.acmicpc.net/problem/2243 전역 변수tree : 세그먼트 트리 정보를 저장할 정수형 배열, 사탕의 맛 개수가 최대 100만이므로 400만 이상의 크기로 세팅한다. 함수1. updatevoid update(int node, int start, int end, int idx, int val) 매개변수 idx의 맛을 가진 사탕의 개수를 val만큼 더해준다.val에는 음수가 올 수 있으나 문제에 없는 사탕을 꺼내는 경우와 같은 잘못된 입력은 주어지지 않는다. 라고 ..

리뷰 앨범이나 사진이 중복될 경우 출력하는 문자열이 잘못되어서 계속 틀렸다... 문제를 잘 읽자 ㅠLinked List를 사용한다면 시간을 더 줄일 수 있을 것 같은데 아무래도 해시맵의 키를 경로의 합인 문자열을 사용하다 보니 해시 충돌이 나서 더 이상 시간을 줄이기엔 무리가 있는 것 같다.해시맵을 통해 절대 경로를 key로 사용하는 방식으로 문제를 풀었다.https://www.acmicpc.net/problem/20541 전역 변수Data : 앨범 정보를 저장할 구조체, 부모 앨범명, 현재 앨범명, 현재 앨범에 존재하는 앨범 및 사진 집합이 저장된다.dic : 맵 구조를 나타낼 해시맵, 앨범 이름을 키로 받고, 해당 폴더 정보 Data 구조체를 값으로 저장한다.del_album, del_photo : ..

리뷰 알고리즘 분류에 다이나믹 프로그래밍이 있어 혼란이 왔었는데 DFS로도 충분히 AC가 가능한 문제였다.https://www.acmicpc.net/problem/15681 문제 풀이전역 변수n, r, q : 노드의 개수 n, 루트 노드 r, 쿼리의 개수qdp : 각 노드가 루트인 서브트리에서의 하위 노드의 개수(자신을 포함한다.)v : DFS 내부에서 사용할 방문처리 배열, 최대 노드의 개수보다 크게 설정해 준다.path : 인접 리스트를 저장할 정수형 벡터 배열, 최대 노드의 개수보다 크게 설정해 준다. n, r, q를 각각 입력 받아주고, dp를 n + 1크기로, 기본값은 자기 자신을 포함하기 위해 1로 세팅해 준다.n - 1개의 간선 정보를 입력 받아 양방향 인접 리스트를 생성해 준다.루트를 방문..

리뷰 두 노드에서 출발해 LCA에 달할때 까지 도로 중 가장 짧은 거리와 가장 긴 거리를 구하는 문제https://www.acmicpc.net/problem/3176 문제 풀이도시의 최대 개수는 10만이므로 MAX_N을 10만 1로, LOG를 MAX_N을 LOG2를 취한 값 보다 크게 20으로 설정한다.도시의 개수 n과 쿼리의 개수 k를 전역 변수로 설정한다.부모 도시를 담을 배열par, 짧은 거리 및 긴 거리를 저장할 배열 mn, mx을 MAX_N * LOG 크기로 설정한다.깊이를 담을 배열dep, 유니온 파인드용 배열 nodes를 MAX_N크기로 설저어한다.인접 리스트 정보를 담을 구조체 Link를 만들어 주고 Link타입 벡터 links를 MAX_N크기로 설정한다.n값을 입력 받고 1~n 도시를 각..

리뷰 그래프의 정보가 주어지고 두 노드간의 거리를 구하는 문제, 루트 노드가 1이 고정이 아니여서 직접 구해주어야 한다.LCA는 개념만 잘 잡는다면 응용 문제에 적용하는 방법이 어렵지 않은 것 같다.https://www.acmicpc.net/problem/1761 문제 풀이main 함수에 init, ds, pre_process, query 네개의 함수를 순차적으로 실행시켜 문제를 풀었다.init 함수에서 n값을 받고 n - 1개의 간선 정보를 tree 벡터 배열에 저장한 뒤 Union 작업을 수행해 준다.1부터 n까지의 노드를 탐색 한 후 자기 자신을 value로 갖는 노드를 찾아 root로 저장한다.root 부터 dfs 함수를 통해 각 노드의 깊이와, 루트 노드로 부터의 거리, 자기 자신의 바로 윗 조..

리뷰 치열한 전투의 흔적이 보이십니까?LCA의 기본기가 있다면 쉽게 풀 수 있을 거라 생각했는데, 문제가 친절하지 않아 고생한 문제https://www.acmicpc.net/problem/13511 문제 풀이input 함수에서 n값을 받고, 각 노드간의 간선 n - 1개를 입력 받는다.solution함수에서 dfs 함수와 pre_process 함수를 돌려주어 각 노드의 부모, 깊이, 비용값을 구해주었다.dfs 함수에서는 각 함수의 깊이 및 루트 노드로부터의 비용, 자신의 바로 위 부모를 구해 각 배열에 저장해줬다.pre_process 함수에서는 각 노드의 2^i 번째 상위 부모를 찾아 부모 배열을 마저 초기화 해주었다.query 함수에서 m값을 받고, 입력된 m개의 쿼리를 처리해 주었다.쿼리의 인덱스가 ..

리뷰 LCA 문제의 상위 호환버전, 노드의 개수가 2배로 많아졌고, 쿼리의 개수도 증가하였다.시간을 좀 아껴보려고 LOG의 크기를 줄여주었더니 OutofBounds 에러가 출력되었다, LOG값을 높혀주니 AChttps://www.acmicpc.net/problem/11438 문제 풀이n값을 입력 받고, n - 1개의 간선을 tree 벡터 배열에 양방향 간선으로 저장해 준다.루트 노드는 항상 1이기에 1부터 dfs 함수를 통해 모든 노드에 자기 자신의 깊이와 바로 윗 조상을 초기화 해준다.pre_process 함수를 통해 각 노드에 변수 LOG의 값 즉 2^20개의 부모 노드를 탐색하여 저장해 준다. (메모제이션)m개의 쿼리를 받고, 각 쿼리마다 두 노드의 최소 공통 조상을 lca 함수를 통해 찾아준 뒤 ..