Problem Solving
-
[Algorithm] 최소 신장 트리 (MST, Minimum Spanning Tree)Problem Solving/Algorithm 2020. 3. 8. 19:39
신장 트리 (Spanning Tree) 란? - 그래프 내의 모든 정점을 포함하는 트리 - 사이클이 형성되지 않도록 모든 정점이 연결된 트리 - 최소 연결 부분 그래프로 N개의 정점, N-1개의 간선을 가진다. [예시] 해당 그래프에서 다음과 같은 신장 트리를 구할 수 있다. 최소 신장 트리 (Minimum Spanning Tree) 란? - 주어진 그래프에서 최소한의 비용으로 만든 트리 - 간선 가중치의 합이 최소인 스패닝 트리 - 통신망, 도로망, 유통망 구축 비용 등에 활용 MST 구현 방법 - 크루스칼 알고리즘 (Kruskal's Algorithm) - 프림 알고리즘 (Prim's Algorithm) # 크루스칼 알고리즘 (Kruskal's Algorithm) - 탐욕적 방법을 이용하여 최적의 해..
-
[SWEA] #4008 _ 숫자 만들기Problem Solving/SWEA 2019. 10. 29. 19:29
[숫자 만들기] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 가능한 모든 경우의 연산자 순서를 고려하여 숫자를 얻을 수 있다. dfs를 이용하여 조합을 구해 해당 문제를 풀 수 있다. 나는 next_permutation을 이용하여 간단히 구현하였다. next_permutation을 사용할 때 벡터의 초기 값은 작은 숫자에서 큰 숫자로 정렬되어 있어야 한다. 따라서, sort함수를 이용하여 연산자를 오름차순으로 정렬해주었다. [ 소스 코드 ] #include #include #include #def..
-
[SWEA] #2477 _ 차량 정비소Problem Solving/SWEA 2019. 10. 29. 19:14
[차량 정비소] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com tk는 도착한 시간을 저장하는 큐로 손님의 수만큼 값을 저장한다. v_a, v_b는 a창구와 b창구 이용하는 손님을 가지는 벡터이다. checkPossible() 함수는 사용 가능한 창구 번호를 반환해준다. tk가 현재 시간인 time보다 작거나 같아지면, 손님이 도착한 것이기 때문에 wait 큐에 넣어준다. (이때, wait은 우선순위 큐를 이용하여 손님의 우선 순위대로 pop 되도록 구현하였다.) 시간이 흐르다 사용 가능한 b창구가 ..
-
[SWEA] #2383 _ 점심 식사시간Problem Solving/SWEA 2019. 10. 29. 18:57
[점심 식사시간] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 사람이 1번 계단을 이용하는 경우와 2번 계단을 이용하는 경우 두 가지의 경우를 고려할 수 있다. 이는 chk 배열을 이용하여 구현하였다. s_1과 s_2는 1번 계단과 2번 계단을 이용하는 사람을 저장하는 벡터이고, val은 계단과 사람의 거리이다. (거리가 짧을 수록 먼저 도착하기 때문) 계단을 이용할 수 있는 모든 방법의 시간을 계산하여 최소 시간을 구하였다. [ 소스 코드 ] #include #include #include #i..
-
[SWEA] #2382 _ 미생물 격리Problem Solving/SWEA 2019. 10. 29. 18:05
[미생물 격리] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 시뮬레이션 문제이다. k_info라는 구조체를 선언하여 미생물의 군집의 정보를 저장하였다. map은 군집의 위치에 미생물의 수를 나타내고 있다. 군집이 이동하기 전 해당 위치의 map 값을 0으로 만들어 주고 모든 군집의 이동이 끝난 후 map에 각 군집의 미생물 수를 해당 좌표에 뿌려주었다. 이를 구현하기 위해 tmp 벡터를 사용하였다. 예를 들어, A군집이 이동하고자하는 자리에 이동하지 않은 B군집이 있는 경우에는 합쳐지면 안된다. ..