문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)LAN1000ms65536kb1198444 (37%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일부 건물들만이 서로 근거리 네트워크로 연결되어 있었는데, 이번에 캠퍼스 정보화 사업의 일환으로 모든 건물을 모두 연결하려고 합니다. 모든 건물이 서로 연결되어 있다는 것은 건물 사이의 케이블을 이용해 모든 건물 간에 서로 직접/간접적으로 데이터를 주고받을 수 있다는 것을 의미합니다. 문제를 단순화하기 위해, 모든 건물들은 2차원 평면 위에 있는 점이라고 가정..

문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)EDITORWARS4000ms65536kb1348266 (19%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제에디터 전쟁은 가장 유명한 자유 소프트웨어 텍스트 편집기인 vi와 Emacs 중 어느 쪽이 더 우월한가를 놓고 인터넷에서 자주 벌어지는 논쟁을 말합니다. 이 논쟁에 참여하는 사람들은 서로 자신이 사용하는 편집기의 장점을 찬양하고 (“vi는 동작도 빠르고, 빠른 편집을 가능하게 한다고”, “Emacs는 LISP을 통해 확장 가능하다고”) 다른 편집기를 헐뜯곤 (“vi-vi-vi는 666이잖아! vi는 악마의 편집기야”, “Emacs는 좋은 운영 체제지. 좋은 편집기가 없는 것만 빼면 완벽해”) 합니다.모든 회원들이 vi 혹은..

문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)PROMISES4000ms65536kb99588 (8%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국의 주요 도시들을 잇는 대형 고속도로를 건설하겠다는 공약을 내걸었습니다. 재야 경제 연구가인 의권이는 이들의 공약을 훑어보다가 이들이 아무 생각 없이 공약을 내걸었다는 결정적인 증거를 발견했습니다. 이들 중 일부 고속도로는 건설하는 의미가 거의 없다는 것입니다.어떤 고속도로를 새로 건설할 당위성이 있기 위해서는 기존에 고속도로를 통해 오갈 수 없던 두 도시가 새로 연결되거나..

문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)GALLERY1000ms65536kb1403364 (25%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제 전세계의 유명한 인물화들을 모아 두는 미술관에 괴도 콩의 도전장이 날아들었습니다. 2022년 2월 2일을 기념하여, 미술관에 전시된 인물화 중 하나의 얼굴을 모 프로게이머의 얼굴로 합성하겠다는 것입니다. 미술관의 관장을 맡고 있는 재하는 이와 같은 사태를 방지하기 위해 감시 카메라를 설치하기로 마음먹었습니다. 미술관은 여러 개의 갤러리와 이들을 연결하는 복도로 구성되어 있으며, 한 갤러리에 감시 카메라를 설치하면 이 갤러리와, 복도로 직접 연결된 갤러리들을 감시할 수 있습니다. 모든 갤러리를 감시하기 위해 필요한 최소 감시 카..

문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)SORTGAME2000ms65536kb1578447 (28%)출제자출처분류JongMan연습문제보기문제중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 이상의 방식으로 정렬할 수 있다. 예를 들어 3 4 1 2 는, 3 4 와 1 2 를 각각 뒤집어 4 3 2 1 을 만든 뒤, 전체를 뒤집어 정렬할 수도 있지만, 4 1 2 를 먼저 뒤집고, 3 2 1 을 다시 뒤집으면 두 번만의 연산으로 정렬할 수도 있다.정렬을 위해 뒤집기 연산을 최소 몇 번 해야 하는지를 계산하는 프로그램을 작성하라.입력입력의..

# 벨만-포드 최단 경로 알고리즘다익스트라 알고리즘과 같은 단일 시작점 최단 경로 알고리즘이지만, 음수 간선이 있는 그래프에 대해서도 최단 경로를 찾을 수 있으며 그래프에 음수 사이클이 있어 최단거리가 제대로 정의되지 않은 경우도 찾을 수 있다.수행 과정에서 각 정점까지의 최단 거리 상한을 담은 배열 upper[]를 유지한다. 이 값은 알고리즘이 진행됨에 따라 점점 감소하고, 최종적으로 각 정점까지의 최단거리를 담게 된다.# 동작 과정알고리즘이 시작할 때 알 수 있는 사실은 시작점 -> 시작점까지의 최단거리가 0이라는 것 뿐이다. 따라서 upper[s] = 0 으로 초기화하고, 나머지 원소들은 아주 큰 수(무한으로 상정되는) 로 초기화 한다.이 예측 값을 실제 최단 거리에 더 가깝게 갱신하기 위해 아래와..