Lee 코딩 Lee 코딩

택배 배송 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 1819 1120 943 63.587% 문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다. 농부 현서에게는 지도가 있습니다. N (1

숨바꼭질 3 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 46202 13556 8588 25.727% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이..

최소비용 구하기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 128 MB 54175 16519 10739 32.117% 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 ..

특정 거리의 도시 찾기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 24043 7214 4585 28.603% 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가..

2022.06.27 - [분류 전체보기] - 최단 경로 - 다익스트라 알고리즘 최단 경로 - 다익스트라 알고리즘 다익스트라 알고리즘 : 특정 노드에서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘(음의 간선이 없을 때 제대로 동작) 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화 한다 3. leeeehhjj.tistory.com 최단 경로를 구하는 알고리즘 중 다익스트라 알고리즘을 위의 링크처럼 간단히 구현하면 O(V^2)의 시간 복잡도가 나오기 때문에 노드 개수가 10000개가 넘어가면 위의 코드로는 구현하기가 힘들다. 따라서 매번 최단 거리 테이블을 선형적으로 탐색하는 것이 아니라 우선순위 큐를 활용하여 찾게 되면 O(ElogV)의 시간 복잡도로 구현할 수 있다. 개선된 다익스트라..

다익스트라 알고리즘 : 특정 노드에서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘(음의 간선이 없을 때 제대로 동작) 1. 출발 노드를 설정한다 2. 최단 거리 테이블을 초기화 한다 3. 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신한다 5. 3과 4번을 반복한다 -출발 노드는 1일 때 노드 번호 1 2 3 4 5 6 거리 0 무한 무한 무한 무한 무한 -1번 노드에서 갈 수 있는 노드는 2,3,4이므로 이 노드들의 최단 거리 테이블을 갱신 노드 번호 1 2 3 4 5 6 거리 0 2 5 1 무한 무한 -4번 노드가 가장 가까우므로 4번 노드를 거쳐 가는 거리 확인 -> 3번, 5번으로 가는 거리의 최단..

로봇 청소기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 39062 21354 14181 53.740% 문제 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸은 (r, c)로 나타낼 수 있다. 로봇 청소기는 다음과 같이 작동한다. 현재 위치를 청소한다. 현재 위치에서 다음을 반복하면서 인접한 칸을 탐색한다. 현재 위치의 바로 왼쪽에 아직 청소하지 않은 빈 공간이..

스타트링크 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 32235 10132 7667 33.339% 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에..