이우의 개발일지

백준 10814번 나이순 정렬  이 문제는 시간 초과를 염두해야해서 이중 for문은 불가하다.그러면 sort함수를 사용하여 시간복잡도가 O(nlogn)으로 내려가게 만들어줘야한다. 하지만, 여기서 문제의 조건 중 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 만들어야한다. 따라서, 순서를 기억하는 방법과 stable_sort를 사용하는 방법이 있다.  bool compare(pair a, pair b){ return a.first  stable _sort의 사용 방법은 위 처럼 vector의 시작점과 끝점을 넣어주고 조건을 달아주면 끝이다.compare 조건문 안에서 a가 b보다 작으면 True, 크면 false를 해주면 된다.   이 함수는 stable_sort 함수가 벡..

백준 1260번 BFS와 DFS BFS와 DFS 풀이이 문제는 생각보다 까다로울 수 있는데, 일반적인 BFS와 DFS 구현에서 추가로 조건이 다음과 같이 붙는다. 조건 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.조건 2. DFS와 BFS 동시에 구현하기 조건 3. 들어간 순서대로 출력하기 BFSvoid Bfs(int start) { Q.push(start); vis_b[start] = 1; cout  먼저, BFS를 보면 일반적인 구현방식과 동일한데 중간에 sort 함수가 보일 것이다. 간선의 개수가 최대 10,000개까지 가능해서 처음에 이중 for문을 시도했다가 시간초과가 뜨는 쓴 맛을 봤다... ㅋㅋ 이중 for문에 시간복잡도는 O(n^2) 이고 내가 현재..

백준 11725번 트리의 부모 찾기   11725번 풀이이 문제도 일반적인 BFS 형식의 확정 문제이다. 결국에는 '각 노드의 부모 노드가 무엇이냐' 를 찾는 문제인데, 트리 구조를 바탕으로 하지만 트리의 층 순서대로 주는 것이 아닌 뒤죽박죽 형식으로 주기 때문에 결국에는 한번에 다 받은 다음에 BFS 구조로 찾는 방법으로 다가갔다.  for (int i = 0; i > a >> b; if (a == 1) { parent[b] = 1; Q.push(b); vist[b] = 1; } else if (b == 1) { parent[a] = 1; Q.push(a); vist[a] = 1; } vec[a].push_back(b); vec[b].push_back(a);}1층의 노드는 무조건 1이라는 조..