시뮬레이션만 하면 되고, 조건도 그다지 복잡하지 않아서 그냥 주어진 조건을 잘 읽고 풀면 수월한 문제였습니다.문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17678?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 방법 1. timetable 벡터 정렬sort(timetable.begin(),timetable.end());timetable 벡터가 정렬되지 않은 상태로 주어져 있기 때문에 timetable 벡터를 정렬합니다. 2. 초기값 지정int bus=540, amount=0, temp=1;int ans..
코딩테스트/문제풀이
문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 방법 그래프 알고리즘 스터디에서 풀어봤던 문제로, 그래프로 분류되어있긴 하지만 n이 8 이하이므로 그래프 알고리즘을 사용한다기보다는 완전탐색 구현 문제였다. 깊이 우선 탐색(DFS)를 활용해서 완전탐색으로 풀었다. 벽 3개를 세울 수 있는 가능한 모든 조합에 대해서 dfs를 수행했고, 가장 바이러스가 적게 퍼진 경우를 출력해주도록 했다. 완전탐색이므로 n이 커진다면 시간복잡도에서 불리할 수 ..
문제 링크 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 풀이 방법 원래는 위상 정렬을 활용해서 풀어볼까? 했지만 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s가 최대 50000개이기 때문에 최악의 경우 위상정렬을 50000번 돌려야한다는 문제가 있었다. 출력할 때 걸리는 시간이 O(1)이어야겠다는 생각이 들었고, 플로이드 워셜 알고리즘을 활용해서 모든 정점들 간의 관계를 마킹해두고 출력 단에서 한번에 출력해줄 수 있도록 했다. 플로..
문제 링크 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 방법 알고리즘 스터디 그래프 파트하면서 나왔던 문제고, 접근 방법 발상이 조금 힘들었던 문제였다. 일정 점으로부터 트리의 끝까지 탐색하는 것은 깊이 우선 탐색(DFS)를 활용하면 쉽지만, 트리의 끝과 끝은 어떻게 파악해야 할까? 임의의 점에서 트리의 끝까지 가는 DFS를 한 번 돌리고, 그 끝에서 반대쪽 끝으로 가는 DFS를 한번 더 돌려서 길이를 파악하면 된다. ..
