박카스러버

https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 저는 해당 문제를 투포인터를 활용하여 문제를 해결하였습니다. 시작지점과 끝지점을 가리키고 이 사이에 라이언 인형이 몇개 존재하는지를 확인하고, 이것이 k랑 같을 때의 ei와si의 차이가 가장 작은 것을 리턴하였습니다. 시간복잡도 : O(n) package BOJ; import java.io.BufferedReader; import java.io.InputStreamReader; import ..

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 저는 해당 문제를 prim 알고리즘을 통해 문제를 해결하였습니다. prim을 통해 MST로 만들었을 때의 가중치를 구하고 이를 전체 가중치에서 빼주었습니다. 처음에 저는 배열을 통해 prim을 구현하여 시간복잡도 O(n^2)로 하였을 때 시간초과가 나왔습니다. 그래서 저는 우..

https://programmers.co.kr/learn/courses/30/lessons/87946 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr 저는 순열을 통해 해당 문제를 해결하였습니다. dungeons의 개수가 8이하여서 순열로 풀어도 8!이므로 1초안에 들어갈 것이라 생각하였습니다. package Programmers.ETC; public class 피로도 { public int solution(int k, int[][] dungeons) { int answer = -1; boolean[]..

https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 저는 Map과 Set을 통해서 문제를 해결하였습니다. Map을 통해서 해당 번호가 몇번째 인덱스에 있는지를 확인하고 0 ~ index까지 터널에서 나왔는지를 확인합니다. 나오지 않은 것이 있다면 추월한 것이기 때문에 result를 늘려주었습니다. package BOJ.ETC; import java.io.BufferedReader; import java.io.InputStreamRe..

https://programmers.co.kr/learn/courses/30/lessons/81304 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr https://tech.kakao.com/2021/07/08/2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%9D%B8%ED%84%B4%EC%8B%AD-for-tech-developers-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%B4%EC%84%A4/ 2021 카카오 인턴십 for Tech developers 코딩 테스트 해설 2021년 카카오의 여름 인턴십의 첫 번째 관문인 코딩 테..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 저는 해당 문제를 DP를 이용해 문제를 해결하였습니다. DP[depth][시작 지점]으로 하여 depth는 입력 edge의 인덱스이고 현재온 지점입니다. 해당 depth의 edge의 start가 시작 지점보다 edge가 m 이하라면 이 edge를 넣은 것과 안 넣은 것의 min값을 구하였습니다. package BOJ.MST; import java.io.BufferedReader; imp..

https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 저는 해당 문제를 순열을 통해 먼저할 연산자를 선택하고 해당 연산자를 먼저 수행하였습니다. depth가 3일때면 연산자를 모두 사용했기 때문에 숫자가 무조건 하나만 남아있을 것이고 이의 절대값을 리턴하였습니다. import java.util.*; import java.util.function.Function; class Solution { private sta..

https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 저는 해당 문제를 BFS를 이용해 문제를 해결하였습니다. 저는 각각의 작업 단계를 함수로 나누어서 구현하였습니다. 온풍기에서 바람이 나오는 것은 BFS를 통해 구현하였습니다. 저는 방향을 12시부터 시계 방향으로 표현하였습니다. (입력으로 들어온 것을 제가 편한 표현으로 매핑시켜 배열에 넣었습니다.) 이를 통해 대각선의 경우는 온풍기의 방향에서 +1과 -1을 통해 대각선의 방향을 구했습니다. 결국..

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 저는 LIS를 이진탐색으로 하여 문제를 해결하였습니다. nowIndex를 통해 현재 LIS의 값들에 대한 인덱스를 저장하였고, path를 통해 이전 인덱스를 저장해 path가 -1이 될때까지 타고 들어가 가장 긴 증가하는 부분 수열의 구성 숫자들을 구하였습니다. 시간복잡도(평균) : O(nlog(n)) package BOJ.DP; import java.io.Buffe..

https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 저는 해당 문제를 투포인트 개념을 이용하여 문제를 해결하였습니다. 저는 시작 인덱스와 끝 인덱스를 가리키는 포인터 두개를 가지고 시작하였습니다. 처음에는 둘 다 0으로 시작합니다. sum을 이용해 시작점과 끝점사이의 합을 구하였습니다. sum이 입력값보다 작다면 끝점을 늘리고 이 값을 sum에 더해주고 같거나 크다면 시작점을 늘리고 이 값을 sum에 빼줌으로써 sum으로 시작..