박카스러버

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 전형적인 다익스트라 문제이다. 저는 다익스트라를 통해 최소 값을 알아냈고, route라는 경로 배열을 통해 이전 최소값의 경로들을 저장하였습니다. 또한, Stack은 Vector로 구현되어 있어 동기화 기능이 내재되어 있어 효율적이지 않은 것으로 알고 있습니다. 그래서 deque를 통해 stack을 사용하였습니다. package BOJ; import java.io...

https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 해당 문제는 DFS방법으로 풀었습니다. 뎁스가 깊어질수록 cnt를 늘려주고 더 이상 갈 곳이 없다면(리프노트) cnt의 값을 결과값에 더해주었습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import jav..

https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 저는 플루이드-워샬 알고리즘을 활용하여 2-칭구를 찾았습니다. 플루이드-워샬은 n^3방법으로 비효율적일 수 있지만 코드가 간결하고 입력값이 50이라 시간초과가 나지 않을 것이라 판단하여 사용하였습니다. 마지막으로 각 행에 대한 Y를 찾고 이 수가 가장 큰 값을 결과로 출력하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputSt..

https://www.acmicpc.net/problem/9656 9656번: 돌 게임 2 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net dp로 문제 해결 true : SK 승리 false : CY 승리 현재 1개 가져가거나 3개 가져갔을 때 둘 다 이긴다면 이긴다. 라도 판단하였습니다. 그래서 dp[i-1]과 dp[i-3] 둘 다 false라면dp[i]를 true로 하였습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.function.Function; publi..

https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net bfs + 비트마스킹 문제이다. 각각의 Node들은 현재 좌표와 비트마스크한 키를 가진다. 방문 체크 배열은 좌표롸 키값을 가지고 방문체크를 한다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util..

https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 처음에는 이분탐색으로 생각하지 못 했습니다. 브루스 포스로 하는 경우 n log(n)이 최대이기 때문에 시간초과 또는 메모리 초과가 나오게 된다. 문제의 배열의 각 원소의 값이 i*j이기 때문에 각 행에서 mid 값보다 작은 값의 개수를 구하기 위해서는 mid / 행을 하면 된다. 이를 통해 mid값이 몇번째 index에 존재하지는 확인할 수 있다. package B..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 저는 DP코드를 작성할 때 for문 보다는 재귀적인 방법을 선호합니다. 이 문제는 DP문제이지만, 경로 또한 알아야하는 상황입니다. 이를 저는 next 배열을 만들어 해결하였습니다. next배열은 다음 경로 값을 가지게 하여 이를 통해 1이 나올때 까지 확인하여 경로를 확인할 수 있습니다. package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import j..

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 전형적인 LIS 문제입니다. 하지만 N의 크기가 1,000,000 이기 때문에 이중for문으로 작성하면 시간초과가 날 것이라 생각합니다. 저는 DP 배열을 만들어binary search를 통해 해당 원소가 DP배열에 어디에 들어가야하는지 판단하여 위치가 DP에 들어있는 원소보다 크다면 size를 하나 늘려 최장 증가 수열의 길이를 찾았습니다. package BOJ; import java.io.Bu..