본문 바로가기

Algorithm

 (51)
백준 1774번 우주신과의 교감 (c++) 모든 우주신들을 연결하는데, 연결하는 통로의 길이를 최소로하는 문제이다. 모든 우주신들을 각각 vertex로 보고, 모든 우주신들을 연결하는 Edge를 만들면, Minimun Spanning Tree를 찾는 문제로 해석할 수 있다. MST는 Union and Find를 이용한 크루스칼 알고리즘을 이용하여 해결할 수 있다. 크루스칼 알고리즘의 시간 복잡도는 O(elog(e)) 인데, 우리는 모든 우주신들이 연결되어 있다고 가정하므로 e = (n -1)n / 2 이 된다. n의 범위는 n x = x; this->y = y; this->dis = dis; } }; struct cmp { bool operator()(Edge &t, Edge &u) { return t.dis > u.dis; } }; double..
백준 2638번 치즈 (c++) 외부 공기와 2칸이상 접속한 치즈는 다음 시간에 사라지게 된다. 내부 공기와 외부공기를 구분하는 코드를 짜주어야한다. 문제의 조건에서 모눈종이의 맨 가장자리에는 치즈가 놓이지 않는다고 주어졌다. 이 말은 외부의 공기는 가장자리를 시작으로 모두 연결되어 있다고 생각할 수 있다. 그래서 (0,0)에서 DFS를 실행하여, 외부 공기를 모두 방문하고 이를 구분할 수 있는 값으로 바꿔준다. 그런 후에 모든 치즈를 확인하면서 외부 공기와 맞닿아 있는 치즈를 지워주면 된다. 현재의 모눈종이 상태를 map[110][110] 에 저장하여 관리하고, 다음 모눈종이의 상태를 nMap[110][110]에 저장하여 계속 업데이트 하는 과정을 치즈가 없어질 때까지 반복한 후에 얼마나 시간이 걸렸는지 출력하면 된다. #includ..
백준 1967번 트리의 지름 (c++) 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제이다. 다익스트라를 2번 사용하면 지름을 구할 수 있다. #include #include using namespace std; #define MAX_NODE 10010 #define MAX_NUM 10000000 int dist[MAX_NODE]; vector node[MAX_NODE]; int n; void dij(int start) { priority_queue pq; pq.push({0, start}); for (int i = 0; i < MAX_NODE; i++) { dist[i] = MAX_NUM; } dist[start] = 0; while (!pq.empty()) { pair top = pq.top(); pq.pop(); int cost = -t..
백준 1030번 프렉탈 평면 (JavaScript) 1초마다 가로세로가 N배씩 커지고 가운데 K*K개는 검은색으로 칠해진다. 이를 0초일 때부터 차곡차곡 블럭을 붙이면서 만들게 되면, O(N^s) 만큼의 시간복잡도와 공간복잡도를 가지게 된다. N는 최대 8이고 s는 최대 10이다. (2^3)^10 = 2^30 = 10^9 인데, 0,1을 1byte로 저장한다면 1GB의 공간이 필요하게 된다. 그래서 전부다 계산하는 것은 비효율적이고 문제의 128MB메모리 제한에 걸리게 된다. 그래서 역으로 x,y 좌표의 프렉탈 평면의 값이 무엇일지를 계산한다. find함수 내에서 하는 것이 바로 그 일이다. 먼저 복사 되기 이전의 가로길이(beforeWidth)를 구하고, n과 k를 이용해 x,y가 검은색으로 칠해지는 범위에 있는 값인지 확인한다. 만약 범위 안이라면 1..
백준 15678번 연세워터파크 (JavaScript) 1번째 징검다리부터 N번째 징검다리를 순차적으로 확인하면서, 현재징검다리보다 d개 전까지의 징검다리중 최대 값과 현재의 징검다리의 값을 비교하여 최대값을 현재 징검다리 값으로 업데이트한다. d개전의 징검다리의 최대값을 그냥 구한다면 O(d)가 걸리겠지만, 세그먼트 트리를 구성하여 구한다면 O(log(d))가 된다. 따라서 이 문제를 O(nlog(n))으로 풀 수 있게 된다. 아래는 JavaScript 풀이 코드이다. const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let input = []; rl.on('line', function..
백준 11724번 연결 요소의 개수 (c++) 1부터 n까지 방문하지 않은 노드를 확인할 때마다, 해당 노드와 연결된 노드들 전부를 방문하고 정답에 +1을 해준다. 연결된 노드를 방문하는 방식은 BFS를 이용하면 된다. #include #include #include using namespace std; vector node[1010]; int visited[1010]; int main() { int n, m; cin >> n >> m; for (int i = 1; i > l >> r; node[l].push_back(r); node[r].push_back(l); } int answer = 0; for (int i = 1; i
백준 1764번 듣보잡 (c++) 듣도 못한 사람을 map에 저장한 뒤에, 보도 못한 사람을 해당 map에서 찾는다. map에서 결과가 있을 경우 이사람은 듣보잡이다. 이사람들을 모은 뒤에, 정렬하고 출력해주면 된다. #include #include #include #include #include using namespace std; unordered_map kiku; vector answer; int main() { int n, m; cin >> n >> m; string s; for (int i = 0; i > s; kiku.insert(make_pair(s, 0)); } unordered_map::iterator iter; for (int i = 0; i > s; iter..
백준 1697번 숨바꼭질 (c++) +1, -1, *2 로 탐색하는 경우에 대해서 BFS로 문제를 풀어주면 된다. Queue에는 해당 위치와 몇번만에 도착했는지를 pair로 저장해서 넣어주고, 목적지에 도달했을 때, pair에 저장되어 있는 값을 확인해주면 된다. #include #include using namespace std; bool visited[100010]; int main() { for (int i = 0; i > n >> k; queue q; pair start = make_pair(n, 0); q.push(start); visited[n] = true; int answer = 0; while (!q.empty()) { pair..

티스토리툴바