PS(Problem Solving)/BOJ244

• 

  [백준/BOJ] 13305번: 주유소 문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 해설 각 도시마다의 기름값이 나와있고, 기름 1L 당 1KM를 갈 수 있다. 우선 첫번째 도시에선 기름값이 얼마든지간에 기름을 넣어야 한다. 즉, 총 기름값을 저장할 변수를 total이라 했을 때, total의 초기값은 (첫 번째 도시의 기름값 + 첫 번째 도로의 길이)가 된다. 또한 맨 마지막 도시에선 더 갈 도로가 없으므로 기름값을 신경쓸 필요가 없다. 이는 반복문을 할 때.. PS(Problem Solving)/BOJ 2022. 9. 15.

• 

  [백준/BOJ] 20040번: 사이클 게임 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 해설 사이클을 구하는 문제이므로 union - find를 이용하여 문제를 풀었다. union-find는 사이클을 찾는 알고리즘으로 크루스칼 알고리즘을 구현하는데 쓰인다. https://jjunsu.tistory.com/221 [알고리즘] 크루스칼 알고리즘(Kruscal Algorithm) 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 그리디 알고리즘(Greedy.. PS(Problem Solving)/BOJ 2022. 9. 14.

• 

  [백준/BOJ] 1005번: ACM Craft 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 해설 선행 순서가 정해져 있고, 이를 특정 건물을 짓기까지 얼마나 오랜 시간이 걸릴지 구해야 한다. 선행 순서가 있는 문제에서 전체적인 순서를 구할 때 위상 정렬을 사용한다. 문제의 예제 2번을 보며 풀이를 해보자. 우선 차수가 0인 1번 정점부터 시작을 한다. 위상 정렬을 진행하므로 1번 정점을 큐에 넣고, 이와 연결된 간선들을 모두 제거한다. 이제 차수가 0인 것은 2번과 3번이다... PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 2473번: 세 용액 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 해설 두 용액 문제를 응용하여 해결할 수 있는 문제이다. 두 포인터 알고리즘을 사용하는 문제인데, 두 포인터를 사용하면 두 개의 값만을 알 수 있다. 따라서 한개의 값을 더 정해야 하는데, 이는 고정적인 값을 하나 정한 후 두 포인터 알고리즘을 수행하는 것으로 해결하였다. 문제의 예시로 풀이를 해보자. {-2, 4, -99, -1, 98}이 있다. 이를 정렬하면 {-99.. PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 12015번: 가장 긴 증가하는 부분 수열 2 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 해설 문제의 예시를 가지고 문제를 풀어보자. 10 20 10 30 20 50이 있다. 여기서 가장 긴 증가하는 부분 수열(LIS)은 {10, 20, 30, 50}이 된다. 이를 구하는 방법으론 dp를 사용하는 것이 가장 먼저 떠오를 것이다. 하지만 dp를 사용하게 되면 범위가 너무 커 시간 초과가 발생한다. 이를 이분 탐색을 통해 해결할 수 있다. 우선 makeLis라는 배열을 선언해놓겠다... PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 1766번: 문제집 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 해설 문제들의 선행 순서를 입력으로 받고, 이를 이용하여 순서를 짜야한다. 또한 문제의 난이도는 1번 문제가 가장 쉽고 N번 문제가 가장 어려우며, 가능한 쉬운 문제부터 문제를 풀어야 한다. 이러한 유형의 문제는 위상 정렬을 이용하여 해결할 수 있다. 위상 정렬을 이용하나, 이 문제에서는 문제의 난이도까지 고려해야하고, 이는 문제의 번호가 낮을수록 쉽우므로 우선.. PS(Problem Solving)/BOJ 2022. 9. 13.

• 

  [백준/BOJ] 9252번: LCS 2 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 해설 문제의 예시를 보자. ACAYKP, CAPCAK 두 문장이 있다. 여기서 부분 수열이 되는 수열 중 가장 긴 것은 ACAK이다. 이를 찾아가는 과정을 보자. 우선 2차원 배열을 선언할 것이다. dp라는 이름을 가진 배열이라 하자. 각 인덱스의 값을 정할 때, str1[i] == str2[j]라면 부분 수열이 되는 값이 하나 늘은 것이므로 .. PS(Problem Solving)/BOJ 2022. 9. 12.

• 

  [백준/BOJ] 2623번: 음악프로그램 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 해설 보조 PD 3명이 담당한 가수들의 순서를 정한다. 이때 한 가수를 여러 보조 PD가 담당할 수 있다. 이렇듯 이미 순서가 정해져 있고, 선행 순서를 위배하지 않으면서 순서를 정하는 것은 위상 정렬(topological sort) 알고리즘을 사용하면 된다. 위상 정렬은 여러 가지 답이 나올 수 있으므로, 코드를 어떻게 짜냐에 따라 답이 달라질 수 있다. 코드 impor.. PS(Problem Solving)/BOJ 2022. 9. 10.

• 

  [백준/BOJ] 2467번: 용액 문제 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 해설 두 용액을 합쳐 0에 가장 가깝게 만들어야 한다. 모든 용액을 입력받은 후, 투 포인터 알고리즘을 통해 문제를 해결하면 된다. 다음과 같이 양 끝점을 변수로 하나씩 잡아 더해준다. 여기서는 -99 + 98이므로 -1이 된다. 값이 -이므로 왼쪽 포인터를 한 칸 옮겨 -2 + 98을 해본다. 이 값이 기존의 합보다 0에 가깝다면 과정을 계속 반복해주면 된다. 코드 import jav.. PS(Problem Solving)/BOJ 2022. 9. 9.

• 

  [백준/BOJ] 13904번: 과제 문제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 해설 우선순위 큐를 이용한 그리디 알고리즘으로 문제를 풀었다. 문제의 예시를 보자. 다음과 같이 점수가 더 큰 문제부터 차례대로 정렬을 해놓았다. 우선 점수가 가장 큰 60점짜리 문제는 4일이 마감 기간이므로 4일에 문제를 풀도록 하자. 이제 다음으로 점수가 높은 50점짜리 문제를 보자. 이 문제 또한 2일째에 아직 아무 계획이 없으므로 2일째에 끝내도록 하자. 다음으로 40점짜리 문제이다. 이 문제의 마감기한은 4일이지만, 이미 4일.. PS(Problem Solving)/BOJ 2022. 9. 9.

• 

  [백준/BOJ] 5972번: 택배 배송 문제 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 해설 전형적인 다익스트라 알고리즘 문제이다. 다익스트라 알고리즘을 통해 1번 헛간에서 시작하여 마지막 헛간에 도착했을 때의 최소 비용을 구해 출력하면 된다. 다익스트라 알고리즘을 잘 모른다면 이 글을 읽어보는 것을 추천한다. 코드 import java.util.* import kotlin.collections.ArrayList private lateinit var graph: Array private.. PS(Problem Solving)/BOJ 2022. 9. 7.

• 

  [백준/BOJ] 13424번: 비밀 모임 문제 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 해설 각 방 사이 비밀 통로를 이용하는 비용이 나와있다. 플로이드 와샬 알고리즘을 이용하여 각 방 사이를 오가는데 필요한 최소 거리를 구해놓은 후, 현재 친구들이 있는 방에서 각 방까지 가장 작은 비용으로 갈 수 있는 방을 찾으면 된다. 코드 import java.util.* import kotlin.collections.ArrayList import kotlin.math.min privat.. PS(Problem Solving)/BOJ 2022. 9. 7.