코테 (4) 썸네일형 리스트형 백준 2110 번 - 공유기설치 (C++/이분탐색/ 추후 다시풀어보기) 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 접근법 그리디 알고리즘인줄 알고 접근했지만, 비교횟수가 너무 많아 이분탐색으로 풀어야 한 문제다. 정해진 공유기 개수로, 공유기의 간격을 최대로 하고싶다는것은, 공유기를 최대한 공평하게 설치하고 싶.. 백준 1707 - 이분그래프(C++/DFS/BFS/그래프) https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 .. 백준 1463번 - 1로 만들기 (C++/ DP - 동적계획법) 문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 접근법실버3이라 무시했는데 생각보다 방법이 안 떠올랐다.. 반복문을 끝도 없이 사용하면.. 뭐 풀수야 있겠지만 이 문제의 제한시간은 0.15초 이다. 수는 1,000,000 까지 들어오는 마당에 모든 경우의수를 무작정 테스트해보기엔 코드도 비효율적이고, 시간도 오래걸린다. 막막할때는 일단 경우의 수부터 적어보자20구한다 가정3일때 -> 3으로 나눈다 -> 끝4일때 -> 1을 뺀다-> 3으로 나눈다 -> 끝 ( 3.. 백준 1991번 - 트리 순회 (C++ / 트리 순회) https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 간단한 트리 순회 문제이다. 트리 구조 짜는것은 각자 편한 방법으로 짜면 될것이고, 여기서 중요한것은 전위,중위,후위 순회를 하는 방법인것 같다. 간단하게 재귀호출을 할때 cou.. 이전 1 다음
