https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 얼마전에 풀었던 '가장 먼 노드' 문제(https://programmingiraffe.tistory.com/30)와 비슷하다고 생각해서 bfs로 풀었다. 그런데 채점을 돌리면 50%의 테스트케이스만 통과한다. '가장 먼 노드' 문제에서는 모든 노드의 가중치가 1이었는데, 이 문제에서는 가중치가 달라 거쳐가는 경우 최소값을 갱신해줘야하는데..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어제 같은 태그인 다익스트라 문제를 풀고 다익스트라 복습겸 풀었다. 한 도착 지점의 최소비용만 구하면 되는거라 더 간단했다. 손으로 직접 다 치면서 알고리즘이 머릿속에 들어가고 손에 익게 했다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제의 제목에서 알 수 있듯이 플로이드-와샬 알고리즘을 쓰는 문제이다. 골드4라는데 다른 골드 문제에 비하면 덜 까다로운 편이였다. 플로이드-와샬 알고리즘을 잘 알고 문제의 조건만 잘 처리를 하면 되기 때문에 같은 그래프 탐색의 DFS&BFS 문제보다 상대적으로 쉽게 느껴진다. 문제의 조건들을 꼼꼼히 읽어야 한다. "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다", "만약, i에서..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 분할정복&재귀 문제이다. 지금까지 풀었던 분할정복 문제 중에서는 쉬운 축에 속하는 것 같다. 재귀에 약해서 쫄았는데 생각보다 금방 풀렸다. 종이의 시작점의 행 번호, 열 번호, 종이의 크기를 매개변수로 보내 종이가 같은 수로 이루어져 있는지 확인한다. 종이가 같은 수로 이루어져 있으면, 해당 수의 카운터를 올리고 종료한다. 같은 수로 이루어져 있지 않으면, 재귀를 통해 크기를 1/3로 ..

https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 1단계에 해당하는 문제로 확실히 2단계 이상의 문제보다는 쉽게 금방 풀었다. 1. 0을 제외하고(알아볼 수 없는 번호) 일치하는 번호의 수를 구한다. 그리고 동시에 0의 개수를 구한다. 2. 0의 개수를 토대로 맞을 수 있는 번호의 최대 개수와 최저 개수를 구한다. (최대 개수는 0인 수를 모두 맞았을 경우이고, 최..

https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 이분탐색 문제이다. 처음에 이게 왜 이분탐색 알고리즘 문제인지 감이 안 잡혔지만.. 1씩 더해가면서 승률이 바뀌는지 안바뀌는지 확인을 한다면, X Y가 클 경우 많은 시간이 걸릴 것이라는 생각이 들었다. 이분탐색 알고리즘을 사용하여 반씩 범위들을 좁혀가며 찾으면 효율적일 것이다. 탐색하는 수를 '게임을 몇 판 더 해야하는지'로 둔다. 그리고 그 수로 승률(Z)를 구한다. Z가 바뀌지않았으면..