기록공간

보통 문자열 입력을 받을때 입력 받는 문자열이 무엇인지를 띄워쓰기로 구분하였다. #include #include using namespace std; int main() { string a, b; cin >> a >> b; cout

처음 내가 접근했던 방법은 다음과 같다. 수업 시작 시간을 기준으로 오름차순하여 정렬한다. 강의실을 담을 벡터 컨테이너를 선언한다. (벡터에 들어가는 값은 수업이 끝나는 시간이다.) 첫 번째 수업이 끝나는 시간을 벡터에 담는다. 이때 강의실은 1개이다. 벡터에서 강의실 수업이 끝나는 시간이 두 번째 수업 시작시간 보다 크거나 같은 경우 해당 강의실의 수업 종료 시간을 두 번째 수업 종료 시간으로 갱신한다. 만약 벡터에서 만족하는 강의실을 찾지 못한 경우, 강의실을 추가하고 해당 수업 종료 시간을 값으로 넣는다. 4 ~ 5 작업을 마지막 수업까지 반복한다. 벡터의 사이즈를 출력한다 코드는 다음과 같다. #include #include #include using namespace std; int main()..

DFS, BFS를 잘 알고 있다면 어렵지 않은 문제였다. 너비 우선 탐색 (BFS) 너비 우선 탐색 (Breadth Firest Search : BFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 모든 간선을 우선적으로 검사하며, 그 중 방문하지 �� lipcoder.tistory.com 깊이 우선 탐색 (DFS) 깊이 우선 탐색 (Depth First Search : DFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 �� lipcoder.tistory.com DFS, BFS 둘 중 무엇을 사용하더라도 정답이 도출되기 때문에 더 잘되는 것을 사용하..

역시 그리디 알고리즘 관련 문제였다. 예전에 풀었던 섬 연결하기 문제와 비슷한 줄 알았지만, 도시들이 서로 다른 도시를 가는 길이가 최소가 나오도록 도로를 깔아야 했다. 이 문제를 풀기 위해서는 플로이드 워셜 알고리즘이 필요하다. 이 알고리즘은 모든 위치에서의 최단 경로길이를 찾게해주는 알고리즘이다. 자세한 내용은 다음 링크를 참고하자. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 처음 반�� lipcoder.tistory.com 문제에서는 이미 최단 경로를 입력 예제로 주어진..

그리디 알고리즘을 사용하는 문제였다. 처음 접근 방법은 가방의 무게는 오름차순으로, 보석은 가격의 내림차순으로 정렬한 후 가격이 비싼 보석부터 가방에 넣도록하였다. 넣은 보석은 컨테이너에서 제거하였다. 이렇게 해서 올바른 정답이 나왔다. 하지만 컨테이너에서 erase(iterator)로 제거하는 방식은 O(n)이다. 여기에 보석들을 순회 돌기 위한 첫번째 반복문, 넣을 수 있는 가방을 찾기위한 두번째 반복문이 있기 때문에 총 O(n^3)의 시간 복잡도가 된다. 결국 시간 초과로 오답이 났다. 그래서 연산 시간을 좀 더 줄이고자 erase(iterator)를 제거하기 위해 Heap을 사용하였다. Heap에 가방에 담을 수 있는 만큼의 무게의 보석들을 담아놓는다. 이때 Heap은 가격 기준의 최대 힙으로 설..

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 처음 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 시간 복잡도는 3중 반복문으로 O(n^3)이다. 코드는 다음과 같다. 이외로 간단하다. for(int k = 0; k d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j]; } } } 선행 조건으로 배열에는 두 정점 간..

간단하게 풀어봤지만 역시 예상대로 대다수 케이스가 실패로 떴다. 푼 방법은 비용 순서로 오름차순 정렬하여, 순서대로 다리를 설치하면서 방문하는 섬을 기록해 놓는다. 다리를 설치할 위치의 두 섬이 이미 모두 다리가 있는 경우에는 설치하지 않는다. 그렇게 모든 섬을 방문할 때까지 반복한다. 하지만 이 방법이 잘못된 이유는 다음 같은 케이스 때문이다. 다음과 같이 5개의 섬이 있고 [[0,1,1],[0,2,2],[1,2,5],[2,3,8],[3,4,1]] 인 경우를 생각해보자. 우선 비용으로 오름차순을 하면 [[0,1,1],[3,4,1],[0,2,2],[1,2,5],[2,3,8]]이 된다. 내가 했던 방식으로 순서대로 3번째까지 다리를 이어보면 다음과 같이 된다. 이렇게 모든 섬을 방문했다고 판단하고 다리 설..

그리디 알고리즘을 사용하는 문제였다. 차들이 공통적으로 사용할 수 있는 카메라의 수를 부분적으로 찾아야 한다. 그러기 위해서는 우선 차량의 진입 지점을 오름차순으로 정렬해줘야 한다. 어떠한 경우더라도 단속 카메라는 1개 이상은 설치되어야 하므로 answer는 1부터 시작한다. 정렬한 상태에서 자동차들의 진입 진출 범위는 다음과 같다. 처음 진입하는 차량은 15까지 진출을 하기 때문에 적어도 15에는 카메라가 배치되어야 한다. (이 카메라는 최초로 배치해야 할 카메라이다. 즉, answer의 1에 대한 카메라를 배치하는 과정인 것이다.) 하지만 다음 차량이 -13까지 진출하기 때문에 최소의 카메라 배치를 만족하기 위해 카메라의 위치는 -13에 위치하게 된다. 이렇게 하면 첫번째, 두 번째 차량이 진입 진출..