Lee 코딩 Lee 코딩

위상 정렬이란? : 정렬 알고리즘의 일종으로 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 ex) 선수과목을 고려한 학습 순서 결정 *진입 차수 : 특정한 노드로 들어오는 간선의 개수 위상 정렬 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐가 빌 때까지 다음 과정을 반복한다 - 큐에서 노드를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다 - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다 모든 노드를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 가능하다.(보통 사이클이 발생하지 않는다고 문제에서 주어짐) 위 과정을 수행하는 동안 큐에서 빠져나간 노드를 순서대로 출력하면 위상 정렬의 결과값이다. 따라서 큐에 들어가는 원소의 순서에 따라 답이 여러가지 존..

A → B 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 22531 9440 7561 40.492% 문제 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. 출력 A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 예제 입력 1 복사 2 162 예제 출력 1 복사 5 2 → 4 → 8 → 81 → 162 예제 입력 2 복사 4 42 예제 출력 2 복사 -1 예제 입력 3 복사 100 40021 예제 출력 3 복사 5 try { i..

운동 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 192 MB 13180 5320 3979 42.303% 문제 V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자. 당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다. 도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주..

전기가 부족해 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 1839 1271 955 70.636% 문제 세계에서 GDP가 가장 높은 서강 나라는 소프트웨어와 하드웨어 기술이 모두 최고라서 IT강국이라 불리고, 2015년부터 세상에서 가장 살기 좋은 나라 1등으로 꼽히고 있다. 살기 좋은 나라 1등으로 꼽힌 이후 외국인 방문객들이 많아졌고, 그에 따라 전기 소비율이 증가하여 전기가 많이 부족한 상황이 되었다. 따라서 서강 나라의 대통령은 최근 개발이 완료된 YNY발전소 프로젝트를 진행 하기로 하였다. 발전소를 만들 때 중요한 것은 발전소 건물과 도시로 전기를 공급해 줄 케이블이다. 발전소는 이미 특정 도시에 건설되어 있고, 따라서 추가적으로 드는 비용은 케이블을 설치할 때 드는 ..

저울 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 6512 4068 3296 64.844% 문제 무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.) [1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5] 우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, ..

경로 찾기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 34225 19887 14433 57.711% 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0..

다익스트라 알고리즘과 같이 한 노선에서 다른 노선으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이라면 플로이드 워셜 알고리즘은 모든 노드쌍들의 최단 거리를 구하는 알고리즘이다. ** 플로이드 워셜 알고리즘은 음의 간선이 있는 경우에도 사용 가능하다. for (int k = 0; k < n; k++) { //모든 노드를 한 번씩 중간 노드로 놓고 거리를 갱신 for(int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]); } } } k는 경유지, i는 시작, j 는 도착지이다. 예..

파티 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 27893 13684 9036 47.245% 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구..