[백준/Gold IV] 최단경로 - 1753
·
코딩 테스트 정복기/백준
[Gold IV] 최단경로 - 1753문제 링크성능 요약메모리: 124632 KB, 시간: 768 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2024년 11월 19일 02:54:46문제 설명방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 ..
[백준/Gold IV] 거짓말 - 1043
·
코딩 테스트 정복기/백준
[Gold IV] 거짓말 - 1043문제 링크성능 요약메모리: 18832 KB, 시간: 196 ms분류자료 구조, 분리 집합, 그래프 이론, 그래프 탐색제출 일자2024년 11월 16일 04:39:32문제 설명지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히,..
[프로그래머스/level 2] 미로 탈출 - 159993
·
코딩 테스트 정복기/프로그래머스
[level 2] 미로 탈출 - 159993문제 링크성능 요약메모리: 79.6 MB, 시간: 14.16 ms구분코딩테스트 연습 > 연습문제채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 11월 21일 22:13:10문제 설명1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니..
[프로그래머스/level 2] 게임 맵 최단거리 - 1844
·
코딩 테스트 정복기/프로그래머스
[level 2] 게임 맵 최단거리 - 1844문제 링크성능 요약메모리: 54.6 MB, 시간: 19.49 ms구분코딩테스트 연습 > 깊이/너비 우선 탐색(DFS/BFS)채점결과정확성: 69.9효율성: 30.1합계: 100.0 / 100.0제출 일자2024년 11월 20일 04:08:25문제 설명ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.위 그림에서 검은색 부분은 벽..
[백준/Silver II] 알고리즘 수업 - 깊이 우선 탐색 1 - 24479
·
코딩 테스트 정복기/백준
[Silver II] 알고리즘 수업 - 깊이 우선 탐색 1 - 24479문제 링크성능 요약메모리: 168284 KB, 시간: 1148 ms분류깊이 우선 탐색, 그래프 이론, 그래프 탐색, 정렬제출 일자2024년 11월 14일 20:40:17문제 설명오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.df..
[백준/Silver II] 알고리즘 수업 - 너비 우선 탐색 1 - 24444
·
코딩 테스트 정복기/백준
[Silver II] 알고리즘 수업 - 너비 우선 탐색 1 - 24444문제 링크성능 요약메모리: 172676 KB, 시간: 1188 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색, 정렬제출 일자2024년 11월 14일 20:55:56문제 설명오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.bf..
[백준/Gold IV] 여행 가자 - 1976
·
코딩 테스트 정복기/백준
[Gold IV] 여행 가자 - 1976문제 링크성능 요약메모리: 22312 KB, 시간: 248 ms분류자료 구조, 분리 집합, 그래프 이론, 그래프 탐색제출 일자2024년 11월 14일 04:14:09문제 설명동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.도시들의 개수와 도시들 간의 연..
[백준/Gold IV] 수들의 합 4 - 2015
·
코딩 테스트 정복기/백준
[Gold IV] 수들의 합 4 - 2015문제 링크성능 요약메모리: 40288 KB, 시간: 420 ms분류자료 구조, 해시를 사용한 집합과 맵, 누적 합, 트리를 사용한 집합과 맵제출 일자2024년 11월 14일 03:51:00문제 설명A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.입력첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N..
[프로그래머스/level 3] 섬 연결하기 - 42861
·
코딩 테스트 정복기/프로그래머스
[level 3] 섬 연결하기 - 42861문제 링크성능 요약메모리: 72.3 MB, 시간: 0.76 ms구분코딩테스트 연습 > 탐욕법(Greedy)채점결과정확성: 100.0합계: 100.0 / 100.0제출 일자2024년 11월 14일 02:17:48문제 설명n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.제한사항섬의 개수 n은 1 이상 100 이하입니다.costs의..