Algorithm

[JAVA] 백준 11657 : 타임머신

문제 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 해결 방법 벨만-포드 알고리즘을 사용해야 하는 문제이다. 한 정점에서 다른 모든 정점의 최단 경로를 탐색해야 하는데 Cost가 음인 경우 사용 가능하다. 최단 경로를 나타내는 배열을 최댓값으로 초기화 해준 다음 배열을 사용해서 탐색을 진행한다. 정점의 수 - 1 만큼 반복문을 통해 최단 경로를 탐색해주고, 한 번 더 탐색하였을 때 또 최단 경로가 바뀐다고 하면 음의 사이클이 존재한다는 뜻이다. 여기..

[JAVA] 행렬 테두리 회전하기

문제 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 해결 방법 어려운 문제인가 했는데, 글에 적힌대로 구현하니 작동이 되었다. 그래서 구현은 문제에서 제시한 가로, 세로 크기만큼 배열을 생성한 뒤에 숫자를 입력해주고, 그림의 1, 2, 3, 4번 순서대로 회전하게끔 반복문을 통해 구현했다. 그리고 최솟값을 찾을 수 있게 min 변수를 게속 체크하면서 확인하였다. 1번은 y값을 증가시켜 y2와 일치하면 멈춰주고, 2번은 x값을 증가시켜 x2와 일치하면 멈춰주었다. 3번은 y값을 감소시켜 y1..

[JAVA] 광고 삽입

문제 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 해결 방법 처음에는 3차원 배열을 사용해서 play_num[시간][분][초] 에 해당하는 시간에 시청 중인 사람의 수를 기록하려고 했는데, 시분초를 계속 변환해줘야해서 상당히 귀찮았다. 그래서 초로 통합을 해서 값을 구하기로 하였다. 문제에서 시간은 hh:mm:ss 로 되어있어 :을 기준으로 split을 사용하여 나누어 주었고, logs 같은 경우는 hh:mm:ss-hh:mm:ss 로 ..

[JAVA] 합승 택시 요금

문제 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 해결 방법 요즘 코딩 테스트를 볼 때 프로그래머스를 많이 이용하기에, 적응을 위해 프로그래머스 문제를 조금 풀어보고 있다. 집까지 가는 최소 비용의 길을 찾는 문제인데, 도착 지점..

[JAVA] 백준 1240 : 노드사이의 거리

문제 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 해결 방법 가중치가 있는 트리의 탐색 문제의 기본이다. class를 이용해서 다음 방문할 위치와 거리를 입력해두고 탐색하면서 거리를 계속 더 해주면 된다. 탐색은 BFS를 사용했다. 간선을 입력할 때 양쪽으로 이동이 가능하게끔 쌍방향으로 리스트에 넣어주어야 한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java..