BOJ/C++ (202) 썸네일형 리스트형 [BOJ] 키 순서 [문제] https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 www.acmicpc.net [풀이] 2458 맞았습니다!! 2968 132 C++14 / 수정 1316 1분 전 1) 플로이드 와샬 알고리즘 사용 (줄 세우기.. [BOJ] lca2 [문제] https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. www.acmicpc.net [풀이] 11438 맞았습니다!! 16192 104 C++14 / 수정 2028 45초 전 1) 최소 공통 조상에 대한 개념은 crocus 님의 블로그 글을 참조함 (https://www.crocus.co.kr/660) 2) 최소 공통 조상을 구현할 때 가장 중요하게 생각해야 할 부분은 depth가 다르면 먼저 올려주고 비교 해야 한다는 것이다. depth가 같.. [BOJ] 네트워크 연결 [문제] https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net [풀이] 1922 맞았습니다!! 4424 36 C++14 / 수정 1760 26초 전 1) 최소신장트리(MST) 사용 (그리디 탐색 방법 사용) 2) 비용을 기준으로 오름차순 정렬 3) union_find를 사용해서 부모가 같지 않는 요소들을 합해가면서 최소 신장 트리를 완성한다. 4) same_parent는 부모가 같은가 아닌가를 판단한다. 트리이기 때문에 사이클이 형성되지 않기 위해 검사한다. 5) 비용 누적합을 출력 1 2 3 4 5 6 7 8 9 10 11 12 13 1.. [BOJ] 줄세우기 [문제] https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net [풀이] 2252 맞았습니다!! 3920 28 C++14 / 수정 1085 4초 전 1) 위상정렬 큐 사용 2) larger[MAX_N] => 다른 사람과 비교하여 인덱스의 주인공이 큰 횟수를 저장 larger[] == 0 이 되면 다른 사람보다 크지 않다 라는 의미이기 때문에 큐에서 꺼내준다. 3) indegree .. [BOJ] 집합의 표현 [문제] https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net [풀이] 1717 맞았습니다!! 5896 44 C++14 / 수정 853 6초 전 1) union-find를 사용하여 해결한.. [BOJ] 트리인가? [문제] https://www.acmicpc.net/problem/6416 6416번: 트리인가? 문제 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. 이때, 노드 u에서 노드 v로 가는 간선이 존재하면 간선을 u에 대해서는 '나가는 간선', v에 대해서는 '들어오는 간선'이라고 하자. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다. 루트 노드를 제외한 모든 노드 www.acmicpc.net [풀이] 6416 맞았습니다!! 1992 0 C++14 / 수정 822 45초 전 1) 트리의 성질 노드의 개수 = 간선의 개.. [BOJ] 이진검색 트리 [문제] https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, www.acmicpc.net [풀이] 5639 맞았습니다!! 2572 96 C++14 / 수정 1235 36초 전 1 2 3 4 5 6 7 8 9 1.. [BOJ] 트리순회 [문제] https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다. www.acmicpc.net [풀이] 1991 맞았습니다!! 1988 0 C++14 / 수정 1183 9초 전 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42.. 이전 1 ··· 19 20 21 22 23 24 25 26 다음