본문 바로가기

분류 전체보기

(143)
(골드 3, c++) 백준 1516: 게임개발 문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다.게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다.편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다고 가정하자..
(골드 4, C++) 백준 10942: 팰린드롬? 문제명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.S = 3, E = 3인 경우 1은 팰린드롬이다.S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.자연수 N개와 질문 M개가 모두 주어졌을 때,..
(골드 4, C++) 백준 2056: 작업 문제수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.입력첫째 줄..
알고리즘: 위상정렬 (Kahn's Algorithm) 위상 정렬이란?방향 비순환 그래프(DAG)에서 정점들의 순서를 나열하는 알고리즘이다.이는 어떤 작업을 수행할 순서를 결정할 때 사용된다.간선 (A → B)는 "A를 먼저 하고, 그다음 B를 해라"라는 의미이다. 위 그래프의 경우 위상정렬을 하면(1 -> 2 -> 4 -> 5 -> 3)(4 -> 1 -> 5 -> 2 -> 3)(1 -> 4 -> 5 -> 2 -> 3)등 다양한 순서가 가능하다.여러 정답이 존재하는 것 역시 위상정렬의 특징 중 하나이다. 위상 정렬 알고리즘 (BFS, Kahn's Algorithm)indegree배열을 통해 특정 노드로 들어오는 간선의 수를 카운트한다.반복문으로 indegree가 0인 노드를 찾아 큐에 push한다.큐에 들어있는 노드에서 다른 노드로 향한 노드의 indegre..
알고리즘: MST 구현 (Prim, Kruskal) MST란?: https://qktjwl123.tistory.com/142 자료구조: 최소 신장 트리(MST, Minimum Spanning Tree, 최소 스패닝 트리)Spanning Tree (신장 트리)Spanning Tree란 그래프 내의 모든 정점을 포함하는 최소 연결 부분 그래프를 뜻한다. (신장 트리라고도 한다)n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, 모든qktjwl123.tistory.com크루스칼 알고리즘 (Kruskal’s Algorithm)핵심 아이디어:간선을 가중치 기준으로 오름차순 정렬한 후, 싸이클이 생기지 않도록 차례대로 간선을 선택. 동작 과정:모든 간선을 가중치 기준으로 정렬작은 가중치부터 간선을 하나씩 선택선택된 간선이 사이클을 만들지 않으면 MST..
자료구조: 최소 신장 트리(MST, Minimum Spanning Tree, 최소 스패닝 트리) Spanning Tree (신장 트리)Spanning Tree란 그래프 내의 모든 정점을 포함하는 최소 연결 부분 그래프를 뜻한다. (신장 트리라고도 한다)n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, 모든 정점이 (n-1)개의 간선으로 연결되어 있으면 Spanning Tree가 된다.특징1. DFS, BFS등 탐색 기법을 사용하면 그래프에서 특정 신장 트리를 찾을 수 있다.2. 하나의 그래프에는 여러 신장 트리가 존재할 수 있다.3. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.4. Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다.MST(Minimum Spanning Tree, ..
자료구조: c++의 STL 모음 Iterator:https://eehoeskrap.tistory.com/263 참고STL에서 지원하는 자료구조를 라이브러리의 방식대로 자료구조를 액세스 할 수 있게 해준다.일종의 포인터와 비슷한 객체라고 할 수 있다. Operator Overloading(연산자 오버로딩):https://edykim.com/ko/post/c-operator-overloading-guidelines/ 참고클래스 내에서 +, - 등의 연산자의 기능을 재정의 할 수 있다.양식: 함수반환타입 operator연산자(비교객체타입 &변수) cosnt {~}VECTOR:https://hwan-shell.tistory.com/119 참고Deque:양방향 큐, 워낙 많이 써본거라 설명은 생략이 밑으로는 전부 sequence containe..
(알고리즘) 트리의 지름 구하기 입력: 하나의 트리출력: 두 정점 (u,v)의 거리의 최댓값 Brute Force: O(n^2) ~ O(n^3)BFS로 가능한 (u, v)의 모든 조합을 다 해본다.가장 간선의 갯수가 많은 두 점이 정점이다.시간복잡도: O(n^3)*시간복잡도: O(n^2) (점 하나를 고정한 상태에서 BFS 할 경우) O(n) 알고리즘점 하나를 지정한 상태에서 BFS로 가장 먼 지점 u를 찾는다.그 점에서 BFS로 가장 먼 지점 v를 찾는다.*간선의 갯수가 가장 많은 경우가 n개라고 했을때, n개의 간선의 갖는 점이 여러개인 것이 아니라면 자명하다.