19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 이번 문제는 그래프 문제나 bfs 탐색 문제를 많이 풀어보셨다면, 단순해 보일 수 있는 문제입니다. 하지만, 단순하지 않을 수 있습니다. 꼼꼼함과 예외처리가 요구되는 문제입니다. 요약하면 다음과 같습니다. 모든 승객들을 태워서 목적지에 데려다줄 때 소모되고 남은 연료량이 정답이 됩니다. 택시의 위치로 부터 가장 가까운 승객부터 태우게 되는데, 가까운 승객이 여러 명이라면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 ..

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 요약하면 다음과 같습니다. 하루 간격 물과 접촉한 빙판이 녹습니다. 얼음에 막혀 서로 만나지 못하는 백조 두 마리가 만나기 위해 며칠이 지나야 하는지 출력하면 됩니다. 아이디어 탐구. 단순히 생각했을 때 얼음을 하루 녹이고, 백조가 서로 만날 수 있는지 탐색하는 과정을 반복하면 정답을 찾을 수 있습니다. 하지만 호수의 행, 열이 1 ≤ R, C ≤ 1500로 넓기 때문에 매일마다 이전의 과정을 반복하면 시간 초과를 예상할 수 있습니다..

코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 그래프 문제가 풀고싶던 와중에 문제 제목만 봐도 그래프 문제 느낌이 나서 오늘은 "지형 이동" 문제를 풀어 보겠습니다. 문제 속에 핵심찾기. 문제를 보면 아무 칸에서 출발하여 모든 칸을 방문할 때 비용의 최솟값을 return하는 문제입니다. 따라서 모든 칸을 최소 비용의 간선으로 잇는 점을 보아 크루스칼 알고리즘을 떠올릴 수 있습니다. 문제의 예시에서 또 하나의 아이디어를 주고 있는것 같습니..

4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이. 별자리들의 좌표가 주어졌을 때 최소 비용으로 모든 별자리를 잇는 최소 스패닝 트리 문제입니다. union-find개념과 더불어 크루스칼 알고리즘을 공부하면 쉽게 풀 수 있는 문제입니다. union-find의 개념은 여기서 쉽게 배울 수 있습니다. 크루스칼 알고리즘은 여기서 쉽게 배울 수 있습니다. 1. 모든 별자리를 입력받고 모든 경우의 별자리 사이의 거리를 queue 변수에 담아줍니다. 2. 비용을 기준하여 오름차순 정렬해줍니다. 3. 무한 루프가 생기지..

1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 이번에 풀어 볼 문제는 벨만포드 문제입니다. 문제 속에 핵심찾기. 문제를 읽어보면 어떤 경로를 갔을 때 금품을 갈취당하거나, 획득하게 됩니다. 따라서 비용이 음수인 간선과 양수인 간선이 존재하며, 금품의 양은 음수가 될 수 있다는것으로 보아 벨만포드 알고리즘을 적용하기에 적합하다는 것을 알 수 있습니다. 정답은 민승이네 집(1번 노드)에서 코레스코 콘도(N번 노드)로 금품의 양이 최대가 되는 경로를 출력하면 됩니다. ∴ 주의 할 점. 경우..

2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 이번에 풀어 볼 문제는 스택 문제입니다. 풀이 스택을 이용한 풀이 과정을 간단히 한다면 다음과 같습니다. 반복문을 통해 탑(tops) 중에 왼쪽부터 시작하여 오른쪽으로 탐색하겠습니다. 탐색하는 동안 스택에는 이전에 탐색했던 탑들 중 현재 탑보다 높은 탑들과 현재 탑만 존재할 수 있도록 합니다. ∴ 따라서 if(다음 탑의 높이 > 현재탑의 높이) => 스택에 있는 높은 탑들 중 가장 근접한 탑부터 순차적으로 다음 탑과 비교 해 봅니다. 만약 스택에서 다음 탑보다..