전체 글

1106 - 호텔https://www.acmicpc.net/problem/1106문제홍보할 수 있는 도시가 주어지고 각 도시별로 홍보하는데 드는 비용/ 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보ex. 어떤 도시에서 9원 들여서 홍보 -> 3명 고객 늘어남 => 돈에 정수배만큼 투자할 수 있음9원 -> 3명, 18원 -> 6명, 27원 -> 9명 (O) / 3원 -> 1명, 12원 -> 4명 (X)=> 호텔 고객 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값입력첫째 줄: C (둘째 줄 ~ N개 줄: 도시에서 홍보할 때 대는 비용, 그 비용으로 얻을 수 있는 고객 수 (출력: 문제의 정답풀이배낭 문제(Knapsack Problem)제한된 무게/비용 안에서 가치/이익을 최대화해서 조합 찾는 문제..

1707 - 이분 그래프https://www.acmicpc.net/problem/1707문제이분 그래프(Bipartite Graph): 그래프의 정점의 집합을 둘로 분할해 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할한 그래프입력첫째 줄: 테스트 케이스 개수 K각 테스트 케이스 첫째 줄: 그래프 정점의 개수 V, 간선의 개수 E (각 정점에는 1부터 V까지 차례로 번호)둘째 줄 ~ E개 줄: 인접한 두 정점의 번호 u, v (u != v, 간선의 대한 정보)출력: 이분 그래프 O -> YES / X -> NO 순서대로 출력풀이이분 그래프그래프의 모든 정점을 두 그룹(A, B)로 나눴을 때 인접한 두 정점이 같은 그룹 속하지 않게 나눌 수 있어야 함 = 인접한 정점은 항상 반대편 그룹이어야 함 시작..

14502 - 연구소https://www.acmicpc.net/problem/14502문제바이러스 확산을 막기 위해 연구소 벽을 세우려 함연구소 크기 NxM 직사각형, 직사각형은 1x1 정사각형으로 나눠져 있음/ 빈 칸, 벽으로 이뤄져 있으며 벽은 칸 하나를 가득 차지/ 일부 칸은 바이러스 존재, 상하좌우로 인접한 빈 칸 모두 퍼져나갈 수 있음/ 세울 수 있는 벽의 개수 3개고 꼭 세워야 함=> 연구소 지도가 주어졌을 때 얻을 수 있는 안전 영역의 크기의 최댓값입력첫째 줄: 지도의 세로 크기 N, 가로 크기 M (3 둘째 줄 ~ N개의 줄: 지도 모양 (0 빈 칸, 1 벽, 2 바이러스) (2 출력: 얻을 수 있는 안전 영역의 최대 크기풀이DFS(백트래킹)벽 세우기 벽 3개 세우면 바이러스 퍼트리기(`b..

1504 - 특정한 최단 경로https://www.acmicpc.net/problem/1504문제방향성 X 그래프/ 1 ~ N번 정점으로 최단 거리 이동 (임의로 주어진 두 정점 반드시 통과)한번 이동했던 정점, 간선 다시 이동 O입력첫째 줄: 정점의 개수 N (2 둘째 줄 ~ E개의 줄: a, b, c (1 다음 줄: 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1, v2 (v1 != v2, v1 != N, v2 != N)(임의의 두 정점 u, v 사이에 간선 최대 1개 존재)출력: 두 개의 정점 지나는 최단 경로 길이 / 없으면 -1풀이Dijkstra(다익스트라) 알고리즘한 정점으로부터 다른 모든 정점까지의 최단 거리(최소 비용)가장 가까운 노드부터 탐색하면서 주변 노드의 거리 하나씩 갱신현재..

1647 - 도시 분할 계획https://www.acmicpc.net/problem/1647문제마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이뤄짐길은 어느 방향으로든지 다닐 수 있고 길을 유지하는데 드는 유지비 있음마을을 2개의 분리된 마을로 분할할 계획 -> 분할 시 각 분리된 마을 안에 집들이 서로 연결 = 각 분리된 마을 안에 있는 임의의 두 집 사이 경로 항상 존재/ 마을에 집이 하나 이상 있어야 함, 분리된 마을 사이 있는 길 없앨 수 있음=> 길 모두 없애고 나머지 길의 유지비 합 최소입력첫째 줄: 집의 개수 N (2 다음 줄 ~ M줄: 길의 정보 A B C (1 (임의의 두 집 사이에 경로가 항상 존재하는 입력만 주어짐)출력: 없애고 남은 길 유지비의 합의 최솟값풀이Kruskal 알고..

2252 - 줄 세우기https://www.acmicpc.net/problem/2252문제N명의 학생 키 순서대로 줄 세움두 학생의 키를 비교하는 방법 사용 (모든 학생 다 비교 X 일부 O)=> 일부 학생들의 키 비교한 결과 주어졌을 때 줄 세우는 프로그램입력첫째 줄: N (1 다음 M개의 줄: 키를 비교한 두 학생의 번호 A, B (A가 B 앞에 서야 함)(학생들의 번호 1 ~ N번)출력: 학생들을 앞에서부터 줄을 세운 결과(답 여러 가지인 경우 아무거나 출력)풀이위상정렬(Topological Sort)방향이 있는 비순환 그래프(DAG; Directed Acyclic Graph)에서 모든 간선의 방향 지키며 정점 나열하는 것모든 정점의 진입차수(in-degree) 계산 -> 들어오는 간선 개수진입 차..