Problem_Solving
-
boj11505 구간 곱구하기Problem_Solving 2018. 10. 25. 16:49
boj11505 구간 곱 구하기 문제 풀이 문제원본 문제 설명 N개의 숫자가 주어지고 두가지 쿼리 입력된다.첫번째는 구간의 곱을 구하는 쿼리두번째는 특정 노드의 수를 변경 하는 쿼리 문제 풀이 기본적인 Segment Tree문제이다Segment Tree는 각 구간에서 최소 또는 최대 부분합 등을 빠르게 구할 수 있는 자료구조이다 소스 코드 사용 알고리즘GOC++Segment Tree(재귀호출)40524kb/432ms (input에서 string으로 받음)33235kb/380ms
-
boj 1953 팀배분Problem_Solving 2018. 10. 25. 16:37
boj 1953 팀배분 문제 원본 문제 설명 학생을 청팀과 백팀으로 두팀으로 나누는데 각각의 학생은 싫어하는 학생이 있다.각 팀에는 서로 싫어 하는 학생이 존재 하면 안된다. 문제 풀이 1 step그래프를 생성할 때 싫어 하는 사람끼리 간선으로 연결 한다. 2 stepBFS로 탐색하면서 부모랑 다른 팀에 배정 시킨다. 3. step각 학생을 순회하면서 2 step에서 구한 팀을 이용해 팀을 나누어 출력한다. 소스 코드 결과 사용 알고리즘GOC++BFS(List를 이용한 queue)3212kb/4ms (input에서 string으로 받음)1992kb/0ms 참고로 GO를 이용할 때 queue라이브러리가 존재하지만 List로 구현 하였습니다.두개에 대한 차이는 차후 포스팅 할 예정입니다.^^
-
BOJ13911 집구하기Problem_Solving 2018. 10. 25. 16:23
BOJ 13911 집구하기 문제 원본 문제 설명 집을 구하려고 하는데 맥도날드와 스타벅스 까지 거리의 합이 최소인 거리를 구하는 문제 문제 풀이 1 Step 모든 맥도날드 위치에서 각 정점 까지 최단 거리(dijkstra)를 구한다. 2 Step 모든 스타벅스 위치에서 각 정점 까지 최단 거리((dijkstra)를 구한다. 3 Step 1번과 2번에서 구한 값을 이용해 맥도날드와 스타벅스 까지 거리합이 최소인 값을 구한다. 해설우선순위 큐를 이용한 dijkstra는의 시간복잡도를 가진다 E는 간선 개수 V는 정점 개수 따라서 이 문제의 해법은 dijkstra의 시간복잡도와 일치한다. 소스코드 소스코드는 GO언어와 C++코드 둘을 첨부합니다.GO언어의 input 받는 부분을 관심있게 보시면 GO언어로 문제..